Utkarsh.25dec's blog

Invitation to CodeChef January Starters 23(Rated for Div-3 only) — 26th January
By Utkarsh.25dec, 3 years ago, In English

We invite you to participate in CodeChef’s Starters 23, this Wednesday, 26th January, rated only for Div 3 Coders.

Time: 8 PM — 11 PM IST

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

  • Vote: I like it
  • +62
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

There is error in timing, it is written "Time: 8 PM — 10:30 PM IST", but contest page says for 3 hours.

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why is this not rated for Div-2 on Codechef?

Majority of audience lies in Div-2 on Codechef !

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    It was hard to find too many good problems to make it rated for div2. Div2 participants can still participate and I think they would find last two problems interesting and educational. Next starter is currently planned to be div2 rated.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +30 Vote: I do not like it

I have a funny, non-constructive solution for nonzero subarray xor.

Suppose we already constructed some prefix $$$a_1, ..., a_i$$$. Each suffix of this prefix "bans" at most one value of $$$a_{i+1}$$$, for a total of $$$i \le 2 \cdot 10^5$$$ banned values. However, there are $$$10^6$$$ possible choices for $$$a_{i+1}$$$. It follows, that if we take a random candidate for $$$a_{i+1}$$$ then it will work with a probability of $$$\ge 1 - 2 \cdot 10^5 / 10^6 = 4/5$$$. Hence we will make an expected $$$O(n)$$$ tries overall, which is fast enough if we can check if a candidate is good quickly.

This transforms a problem into keeping a set of suffix xors, which is well-known. Implementation. Essentially each suffix xor is a xor of the complement prefix xor and the xor of the entire array, hence we only need to keep track of xor of the entire array.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Bonus: Try the given problem for following constraints: n<=1e5, Ai<=n (instead of 1e6)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      My friend Immerser submitted this amazing solution

      Spoiler
      → Reply