Permutation chef*

Yep that's almost it. But the iterating & merging part is a little tricky.

My solution had used most of these ideas.

I solved it by fixing the middle element of the last 3 remaining elements, then counting the ways to remove the left part and right part separately (later multiply by a single binomial coefficient to account for permutations among the left and right operations).

Counting the left and right parts themselves needed some DP and segment tree ideas.

Unfortunately, there were some issues in my implementation during contest, which I fixed later. Really liked the problem though.

My solution:

First, find the nearest $$$k$$$ such that $$$2^k\leq n$$$, and then start taking XORs of pairs of the form $$$(2^k,2^k-1), (2^k+1,2^k-2), ..., (2^k+len, 2^k-len-1)$$$, where $$$(2^k+len)$$$ is equal to $$$n$$$.

For each collection of $$$2*(len+1)$$$ pairs, the answer would be $$$2*[(2^{k+1}-1)*(len+1)]$$$. This would calculate the answer for pairings for values upto $$$(2^k-len-1)$$$, so we now calculate the answer for $$$n=(2^k-len-2)$$$ iteratively as long as $$$(n>0)$$$.

It may happen, that $$$(2^k-len-1)$$$ is $$$0$$$ (only when $$$n$$$ is odd), so the answer for this case would be $$$2*[(2^{k+1}-1)*(len+1)-1]$$$ for the last iteration to eliminate the pairs $$$(n,0)$$$ and $$$(0,n)$$$, and instead pair up $$$(n,n)$$$.

Link to my submission (I've tried to add explanations)

You are right, I am really sorry for that. Seems like all admins have to go over all IOI problems...

Instead of organizing 6-7 contests for div2/div3 users, you can reduce it to 4-5 div2/div3 contests and make one contest rated for div1 users.

Reducing the number of Div2/Div3s will likely do nothing to improve the availability of Medium / Medium-Hard problems required for Div1 rated rounds, propose good quality difficult problems (or get others to do so) if you want more Div1 rounds.

Also as far as I remember, the last time there were 3 rated rounds in a month was when Long Challenges were rated for Div1 and I don't believe the quality of those educational problems can be compared to Cookoff / Lunchtime problems.

Or even if it's not feasible then cook-off and lunchtime should have 15 days gap in between so that div1 users can have 1 contest in two weeks.

As far as I know the current layout is a remnant of the long challenges taking up the first two weekends of the month. With the two "mini challenges" currently being held on different weekends right now, swapping Cookoff to the 2nd weekend of the month would probably make stuff better.

My solution:

Let's first look at the solution worth $$$50$$$ points. Do the following $$$n$$$ times, to assign positions to numbers from $$$1$$$ to $$$n$$$: Find a zero in the array, which doesn't have any other zero among the $$$k$$$ places to its left. Assign the $$$i$$$th number to this position in the answer. Subtract the values at the $$$k$$$ places to its left by $$$1$$$ and set the value at this position to infinity. If at any point there are no zeroes in the array, then output $$$-1$$$. Otherwise, output the final answer array. Try to see why this works.

There are a few more observations needed to get $$$100$$$ points. Firstly, observe that if any value turns negative during the process, then there is clearly no answer as this value will never reach zero. So, zeroes, if they exist will have to be the minimum values in the array.

For a moment, ignore the fact that if there are multiple zeroes, then you have to give preference to the zero which doesn't have another zero in the $$$k$$$ values to its left. We will tackle that later. Say you just want to find a zero. Then, you can just find the index of minimum value in the array and check if that is a zero. Updating the preceding $$$k$$$ values can simply be thought of as one or two range updates.

This problem can be solved by using a min segment tree with lazy updates. Just build the segment tree over pairs $$$(\text{value}, \text{index})$$$ to retrieve the index of the minimum.

Now, to tackle the part about choosing a particular zero if there are multiple zeroes. This part needs a final observation, why do we have $$$n \leq 2k-1$$$? Say a index $$$i$$$ dominates index $$$j$$$ if $$$i$$$ is among the $$$k$$$ indices to the left of index $$$j$$$. The condition $$$n \leq 2k-1$$$ means that for any two indices $$$i$$$ and $$$j$$$, either $$$i$$$ dominates $$$j$$$ or $$$j$$$ dominates $$$i$$$ (or both). Also, note that among multiple zeroes, we always have to choose the zero which is not dominated by any index.

This can be achieved simply by tweaking the comparator of the pairs $$$(value, index)$$$. If the values are same, then compare the index which dominates the other index as lesser (if both dominate each other, then it doesn't matter). This comparator has the property that whenever a solution exists, the index returned by the segment tree would surely be a valid index.

PS: Pretty problem.