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:

Contest Admin: Utkarsh Utkarsh.25dec Gupta, Daanish Mahajan

Setters: Utkarsh Utkarsh.25dec Gupta, Jeevan Jyot JeevanJyot Singh

Testers: Manan mexomerf Grover

Statement Verifier: Nishank IceKnight1093 Suresh

Editorialist: Lavish lavish315 Gupta

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!

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

Thanks, updated!

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

Majority of audience lies in Div-2 on Codechef !

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.

Damn, it was a nice contest. But struggled with TLE on the last one.

I have a funny,

non-constructivesolution 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.

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

My friend Immerser submitted this amazing solution

Spoilera[i] = largest power of 2 dividing i.

1 2 1 4 1 2 1 8 ...