Блог пользователя Utkarsh.25dec

Автор Utkarsh.25dec, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +62
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

Majority of audience lies in Div-2 on Codechef !

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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.

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +30 Проголосовать: не нравится

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.