Today I participated in the Div.2 Round 632 and solved all the 1200 level problems of sorting and binary search from my list. I will write the main takeaways for self reference.

**Div. 2 Round 632:**

**Contest experience**

I got confused and thought that a solution was only possible in A when both sides were odd, so I first submitted a chessboard coloring, this evidently failed the first test. I realized that I could just change the lower right corner to black when one of the sides was even, but this failed once more because it is already black when both sides are even. Finally realized this and sent a fixed solution after 14 minutes.

For the first couple minutes I didn't recall that the elements of $$$A$$$ were just $$${-1,0,1}$$$. After realizing this for each position I just need to know whether I need to make $$$a[i]$$$ it bigger or smaller, and for that we only need to check if there is a $$$1,-1$$$ before it (respectively). This one took 11 minutes total.

Finally for C I quickly realized that I could find the subarrays adding to $$$0$$$ after calculating $$$s_i = a_0+\dots + a_i$$$ for all $$$i$$$ because if $$$i<j$$$ have $$$s_i = s_j$$$ that means $$$a_{i+1} + \dots + a_j = 0$$$. So I stored $$$(s_i,i)$$$ for all $$$i$$$, sorted that and for all the values $$$i_1,i_2,\dots,i_k$$$ with the same sums stored the intervals $$$[i_1+1,i_2], \dots , [i_{k-1}+1,i_k]$$$ because any other $$$[i_j+1,i_k]$$$ with $$$k-j>1$$$ contains one of the previous ones.

From here calculating the number of good arrays is easy, we just iterate through every position $$$i$$$ in the array, and calculate the number of good arrays that start on that point, the end position can only fail if $$$[i,end]$$$ contains one of the forbidden intervals, so end can be all positions from i to one less than the ending of the 'closest' interval (closest to end) that starts on $$$i$$$ or after.

That is, we just sort the forbidden intervals from smallest ending coordinate to largest, a forbidden interval will no longer affect any position greater than $$$i$$$ if an array starting at $$$i$$$ can't include it, so we can keep advancing through the forbidden intervals until one $$$[x_l,y_l]$$$ starts after $$$i$$$ i.e $$$x_l \ge i$$$ and since they are sorted by the second position this one will have $$$y_l$$$ closest to $$$i$$$, meaning there are $$$y_l-i$$$ good arrays starting at $$$i$$$.

Unfortunately, the idea of calculating all subarrays that sum to $$$0$$$ with the cumulative sums isn't quite complete, because we don't have repeated values for the first/last sums that are $$$0$$$ starting at the first position. During the contest I noticed this for the first sum, but not for the last, because once I fixed the first sum I stopped checking this part so I couldn't fix my approach on time.

Rating change: -24. I become too careless when I try to go fast, it is completely worth it to spend a couple more minutes making sure everything is alright considering how high the penalty is. Also, if a part of the solution had a mistake I should make sure that it's completely correct instead of making a fix and moving on.

**Sorting:**

**Solution**

We can just sort the lantern positions and to minimize the radius, for any $$$l_i$$$ we can choose $$$\max\left(\frac{l_i-l_{i-1}}{2},\frac{l_{i+1}-l_i}{2}\right)$$$ for its radius. We also need to check the beginning and ending.

This took me around 12 minutes because I was calculating the best radius in a more complicated way.

519B - A and B and Compilation Errors

**Solution**

This is sorting the three list and comparing consecutive ones to find the missing elements.

Took me 10 minutes because I didn't realize they could coincide on all elements and the last one from the big list was the missing one.

**Solution**

We store pairs (price,quality) and sort them. Suppose the that $$$i<j$$$ have the smallest difference and satisfy $$$q_j < q_i$$$. If $$$j-i > 1$$$ we would have $$$q_j > q_{j-1} > q_{j-2} > \dots > q_{i}$$$, impossible. Thus if the computers Alex wants exists there are consecutive computers that satisfy those properties.

This one took 5:42

**Solution**

If we can go from $$$(a,b)$$$ to $$$(c,d)$$$ we need $$$c \ge a$$$ and $$$d \ge b$$$. Furthermore we just need to do $$$d-b$$$ steps up and $$$c-a$$$ to the right so we store the points as pairs, sort them and at each point check if the steps are both positive.

Only took 8 minutes!

**Solution**

We sort the sequence, there is a solution iff $$$a[k-1] \neq a[k]$$$ for $$$k>0$$$. If $$$k=0$$$ just check if the smallest element is $$$1$$$ or not.

Took $$$4$$$ minutes because I rushed too much and forgot about the $$$k=0$$$ case the first time I submitted.

**Binary Search:**

**Solution**

They only have to fight for the words they have in common. If there are $$$c$$$ then the first player gets to play $$$\frac{c+1}{2}$$$ of them, so PolandBall wins iff $$$a+\frac{c+1}{2} > b+\frac{c}{2}$$$ where $$$a,b$$$ are the number of words only $$$A,B$$$ know.

This was much easier to implement with a map. I took around 30 minutes because I sorted the sequence of words and iterated through both to find the words in common but increased the index of the wrong array :(

**Solution**

Obviously this doesn't require binary search because of the constraints on $$$n,a,b$$$ but we have to practice. It's easy to see $$$t$$$ works iff $$$n \le \left\lfloor \frac{a}{t} \right\rfloor+\left\lfloor \frac{b}{t} \right\rfloor$$$ and $$$t \le \min(a,b)$$$ so we can use up all slices of cake.

This took around 10 minutes because I didn't read all slices had to be used and so $$$t \le a,b$$$.

**Solution**

This problem had nothing to do with binary search :( Notice that $$$a+b \rightarrow a+b-3x$$$ so the sum stays invariant $$$\pmod{3}$$$, thus we need $$$3|a+b$$$. It's not hard to prove that we can do the desired if and only if $$$2\min(a,b) \ge \max(a,b)$$$.

A cool way to see that is that we can merge all moves of the first type into one, and likewise with the second so a position is solvable if and only if it's solvable in one move of each type and that's completely determined.

**Solution**

It's easy to prove that the sequence is just $$$1+v_2(i)$$$, that is one more than the largest power of $$$2$$$ dividing $$$i$$$. Alternatively we can check if $$$k$$$ is in the middle of the sequence of length $$$2^n-1$$$ meaning its value is $$$n$$$, otherwise there we can reduce this to the sequence of length $$$2^{n-1}-1$$$, if $$$k$$$ is in the right interval we subtract $$$2^{n-1}$$$.

**Solution**

I feel this problem actually taught me something. I first tried to calculate it in $$$\mathcal{O}(1)$$$ and then I did the binary search which only took 3:08, quite fast for my standards. So even if the first solution is not much harder, it required being a little more careful and for a 1200 problem there was a significant difference in time.