(I'm mildly surprised at no blog post on the front page about this, but here it goes!)

Translation: Oh look, free contribution!

GL&HF everyone.

Scoaboard link please!

Wow, nobody solved D-hard? damn

I wrote about 400 lines and I think I would need about a 100 more -_-

Can someone break my solution to C-large? I am not convinced that it works, nor have I thought very hard about its correctness.

First, if an edge can only work in one direction, force it in that direction (irrespective of whether it's useful or not).

Now, for all remaining edges that can go in either direction, randomly assign a direction.

Now, while we haven't yet constructed a valid arrangement, pick a random edge that, if we swapped the orientation for it, would connect two currently disconnected components. Swap the orientation for it. You may not swap an edge twice. Report IMPOSSIBLE if you've swapped every edge or if you've somehow gotten stuck.

Is there any Stack Memory Limit that I don't know about? I'm doing D&C in the second one and getting RE and can't see why

looking at the statement of the first problem

Damn, that was a tough contest. How to solve A,B,C and D?

Thanks to the problem authors!

Problem A reminded me of my own problem from an Opencup round on October 2014 (roughly a 2D version of this). The statement is basically this:

There is a rectangle (16x16 to 25x25) on a square grid. Two players put 2x2 squares in it. The player who can't make a move loses. The jury player moves randomly. How to win most of the time?

Here's a comment with the 2D version solution.

Today, I used a similar idea: As long as there are long segments present, try to make many segments with Grundy value 2. When there are only short segments left (Grundy values 1 and 2), pick a move to make the total Grundy value equal to 0. Or a random move if it is 0 already. Update: Code is here.

However, I'm sure there was some easier approach today, with the problem being open-ended.

I had a different solution to C. The implementation is a bit more difficult, but I think it's interesting.

First I checked the border for the case that makes it impossible, as in the official analysis. Now suppose there is at least one B on the border (if not, swap all A's and B's). Draw an edge between two adjacent cell corners if there is an A on exactly one side of the edge. Now find an Eulerian cycle of the edges, being careful not to cross over one's own path. The "inside" of this cycle is now all the A's, and diagonals should be connected up such that the cycle does not cross the diagonals.

I think my solution to B-large is even simpler than the second one from the editorial, although it is tricky.

We will count the sum of all heights of stacks among all possible non-empty pyramidized intervals — since the original sum can be easily subtracted, that is enough.

Consider the contribution of stacks that rise to $$$P[i]$$$ (WLOG heights are different). Let $$$next[i]$$$ be a smallest index greater than $$$i$$$ s. t. $$$P[i] \lt P[next[i]]$$$.

Then, if $$$R \ge next[i]$$$, $$$L$$$ must be between $$$prev[i]$$$ and $$$i$$$ and all stacks from $$$i$$$ to $$$next[i]$$$ rise to $$$P[i]$$$. Similarly for $$$L \le prev[i]$$$. If $$$prev[i] \lt L \le R \lt next[i]$$$, then only $$$P[i]$$$ rises to $$$P[i]$$$.

All in all, We have a nice $$$O(1)$$$ formula and from now on, the solution is straightforward.

Screencast

I just got my t-shirt yesterday (Friday 8/16/19)! PSA to be on the lookout for yours coming soon!