Simulating the process is fast enough.

Very simple greedy algorithm.

We focus on the first permutation and divide it in contiguous maximum length blocks that appear in that order in all other permutations, we can do this in O(nm) if we make the first permutation $$$1,2,3,\dots ,n$$$ and adjust all others accordingly. I didn't think of this and used map, it barely passed at 997ms

I liked this one! We use meet in the middle to calculate all possible sums $$$\pmod{m}$$$ of each half. Since our sums are between $$$0,m-1$$$ for any left sum $$$S_i$$$ the best we can choose in the right is the largest number $$$\le m-1-S_i$$$, or the largest right sum since the total is $$$<2m$$$. Thus, we do a binary search :)

Since the numbers are $$$\le 10^4$$$ it's faster to count how many we have in that range. We save all the numbers whose sum of digits in binary is $$$k$$$ beforehand, and for each $$$i < 10^4$$$ we xor it with all of them to calculate the numbers $$$j$$$ that are at distance $$$k$$$ from $$$i$$$. So at each step we add to the answer $$$am[i]*am[j]$$$. There are $$$\le \dbinom{14}{7} = 3432$$$ numbers at distance $$$k$$$ so this is fast enough.

When I first read A I thought I only needed to check that the number of plays, clears were non-decreasing. Fortunately during the implementation I realized I also needed plays-clears to be non-decreasing because each clear means one more time played. Took exactly 10 minutes because I double-checked after realizing I was missing a condition at first.

Then in B we can quickly see that if the average of the largest $$$m$$$ elements is $$$x$$$ we can do the desired. Say $$$k$$$ is the largest $$$k$$$ with this property, that is $$$\dfrac{a_1+\dots + a_k}{k} \ge x > \dfrac{a_1+\dots+a_k+a_{k+1}}{k+1}$$$ where the numbers $$$a_i$$$ are sorted in non-increasing order.

We can prove that the answer is $$$k$$$ since by showing any reform preserves that the sum of any $$$k+1$$$ elements is smaller than $$$x(k+1)$$$. The idea is thinking about the largest $$$k+1$$$ elements and checking how they change with a reform, all the numbers that change are replaced by this new average or numbers that weren't previously among the $$$k+1$$$ largest so we can check they have a smaller sum than before. I'll edit in the formal proof tomorrow.

The problem took around $$$10$$$ minutes as well. Fortunately there were no implementation mistakes in either.

As for C, I misread the problem as monsters exploding from both sides which I couldn't solve in the remaining time. The actual problem was monster $$$i$$$ just affecting $$$i+1$$$ so only one explosion damage $$$\min(b[i-1],a[i])$$$ is going to be wasted and we just minimize it.

This one went slightly better. The first two problems of A were very easy, we just needed to create a prefix/suffix and check that we didn't get any contradictions. The third part is not much harder, we ignore the asterisks other than the first and last and glue the insides together but I thought this wouldn't always fit in $$$10^4$$$ and thought I needed to combine the strings.

After a some time I decided to temporarily skip to B. Since the sums of rows of the Pascal triangle are powers of $$$2$$$ it was natural to consider the binary representation of the desired number, however since we need to advance through rows that we aren't interested in we may overcount by a little bit. For a while I was trying to fix this in the beginning of the number, until I eventually realized I could just fix it at the end by traveling through a bunch of $$$1$$$'s since we can overcount by at most 30. Formally I represented $$$N-31$$$ in binary, traveled through $$$1$$$'s until I found a row with sum $$$2^i$$$ appearing in the representation which I completely visited. At the end, if I went through $$$r$$$ rows that I didn't care about I just advance through $$$31-r$$$ $$$1$$$'s.

The implementation took me a lot of time, and I checked my math a lot of times to make sure I was using $$$\le 500$$$ steps. Fortunately everything passed the first time.

I went back to implement the easy parts of A, and since I was still thinking the last part was hard I decided to implement the brute force approach for $$$C$$$, unfortunately I finished a couple minutes after the contest ended.

Although I think I could've solved A on a better day, I ended up in position 2552 which is much better than I expected!

Apparently I attempted this at a contest one year ago and didn't solve. I still found it difficult today, I proved that we only needed to count the parity of the possible moves early on but had trouble representing it until I finally thought about using a stack and popping whenever a repeat appears.

It's not hard to see the sum is actually $$$a[n-1]-a[0]$$$ minus $$$k-1$$$ sums of consecutive differences $$$a[i]-a[i-1]$$$ so we only need to maximize those, we calculate them all, sort and pick the $$$k-1$$$ largest.

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.

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.

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.

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

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!

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.

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 :(

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$$$.

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.

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}$$$.

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.