A Sokoban week

Codeforces Round 889 opened the competitive programming weekend (problems, results, top 5 on the left, analysis). Radewoosh was the fastest to solve the first six problems, and even though the last one did not budge, it was enough for the first place. He was also able to hack his own, tourist's and one of the reference solutions for D after the round, further demonstrating his great understanding of the problems. Congratulations!

I liked the problemset a lot, because it felt like a problemset that I could have come up with myself :) The solutions for the harder problems involved a fair bit of experimentation, and more generally I did not get the (quite regular these days...) feeling of "how on Earth could one think of this setting for a problem or this solution idea", both the problem settings and the solution ideas seemed pretty approachable. Kudos to TheScrasse and dario2994!

I ended up in place 42 instead of place 10 because of an off-by-one error in B: I used bitset<200001> instead of bitset<200002>. I'm actually curious why this out-of-bounds access (querying element 200001 of bitset<200001>) causes a runtime error. Doesn't the implementation use an integer number of bytes, and therefore the actual number of bits has to be at least 200008?

The reason I could not go higher was my inability to solve problem C, which caused me to focus on problem F which I could actually solve and was trying to code. I've implemented a bruteforce, and printed all points for which the distance differed from the one obtainable from the obvious bounds (has to have the same parity and the sum of coordinates less than the sum of all jumps). For example, here is the list of points I got which have distance 12 but just according to parity and the sum of coordinates would have had a smaller distance:

Looking at the list of points, I've noticed a pattern: the points can be split into groups where some coordinates are fixed small ones (for example the group starting with 2 2 ...), and the remaining coordinates take all possible combinations with a given sum or within a given range of sums. This makes sense, as essentially we're saying that achieving a certain combination of small coordinates potentially wastes some of the small moves and may also take away some flexibility from the remaining coordinates because the small moves are not available there. And it seems that the largest "small" coordinate to take into account is 6, based on the point 1 6 6 51.

So what I tried to do during the round is to find the smallest and largest sum of remaining coordinates for each possible set of small coordinates for the first 15 moves, assume that all possible combinations of large coordinates between those bounds are valid, and further assume that the bounds just move by (s+1)+(s+2)+(s+3)+(s+4) when going from s moves to s+4 moves. It seemed logical to assume the same structure between s and s+4 because of how the parities of s*(s+1)/2 change. I could not finish coding the part that counted the actual answer to the problem (taking the given parallelepiped into account).

When I did finish coding it after the contest, it turned out that there were also two flaws in the above hypotheses. First, not all combinations of large coordinates with the sum between the smallest and the largest sum are valid. It turns out that for each particular sum, either all combinations with this sum are valid, or all are not, and the invalid sums are always close to the boundaries. It makes sense in retrospect since if we have spent, say, 1 and 2 on the small coordinates, then there is no way to achieve the sum of all others minus 1 or minus 2 with the rest, but we can achieve minus 0 and minus 3. It also turns out that the lower and upper bounds do not shift by the same amount when going from s to s+4, instead the lower bound moves slower, because the segment expands. This also makes perfect sense in retrospect, as s*(s+1)/2 grows non-linearly. Overall, finishing the code, then finding and fixing those two flaws took me about an hour after the contest. So I was not that close to getting it accepted during the round, but at least I was moving in the right direction :)

Here is problem C, which I had no idea how to even approach during the round, but which has the most beautiful solution: you have a set S of integers between 1 and M (M<=500). In one operation, you pick an element of the set uniformly at random, and increment it by 1. If the incremented element coincides with another element of the set, we keep only one copy, so the size of the set decreases by 1. If the incremented element exceeds M, we discard it, so the size of the set also decreases by 1 in that case. We are given the starting set S, and need to find the expected number of steps before it becomes empty.

Wow, this may be the longest I have ever written about one contest, and I haven't even started talking about problem E which stirred some controversy. As I said before, I quite liked the round :)

AtCoder Grand Contest 063 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). Huge congratulations to zhoukangyang for solving five problems — so far I cannot imagine how this is possible :)

I've earned a respectable 345th place by solving two problems, and even that was not easy — I was stuck with a wrong (and more difficult to implement) approach in B for quite some time. I had no idea how to solve C after thinking about it for a long time, and I could not solve E or F after thinking about them for a bit. I solved D relatively quickly, but spent more than an hour implementing it. I had the solution for ready about 20 minutes before the end, but could not find all bugs in time.

Well, let's hope the bad results will all be spent during the regular AGCs and I will get to shine at the World Tour Finals in Tokyo in September :)

In following this post's tradition, here is problem C that I had no idea how to solve during the round: you are given N<=1000 pairs of integers (A_i,B_i), each integer between 0 and 10⁹. In one operation, you choose two integers x<y between 0 and 10¹⁸, and replace each A_i with (A_i+x) mod y (note that you apply the same x and y to all A_i). You need to make it so that A_i=B_i for all i after at most N operations, or report that it is impossible. 

In my previous summary, I have mentioned an EGOI problem: you are given a HxW grid (H,W <= 50), where some unknown cell of the grid contains an obstacle: a box that cannot be moved. You can send a robot onto the grid in order to determine the location of the box. In one visit, you give the robot a program consisting of characters <, >, ^ and v. The robot starts the visit at the cell (0,0), and then executes your program (> corresponds to moving one cell right, and so on). If a certain move is not possible, either because it would cause the robot to move outside the grid, or because the robot would end up in the cell with the obstacle, the corresponding command is ignored and the execution of the rest of the program continues. You do not observe the robot's movements; instead, you only receive the final coordinates of the robot after executing all commands from the program given for the visit. In the next visit, the robot will start from the cell (0,0) again. To get the full score in this problem, you have to determine the location of the box in just 2 visits. Bonus points (not really) if the total number of commands used throughout all visits is H*W+O(H+W).

When I was thinking about this problem, the key idea to deal with the unknown location of the box was to find such a sequence of moves so that if we have already found the box, then we would stay in the same place, and if not, we would continue looking for it. For example, suppose the box is directly to the left of the robot, and the grid boundary is reasonably far away. Then after performing the sequence of moves v<^>^ the robot returns to the same place, since the ^ move in the middle is blocked by the box. However, if there is no box next to the robot, performing this sequence would result in the robot moving one cell up. We can construct similar sequences for moving one cell down, to the left and to the right, while keeping the property that if the box is directly to the left of the robot, the robot stays in place.

This allows us to go looking for the box, and if we approach it from the right, then we will stay next to it forever, which allows to determine the location of the box from the final location of the robot by just subtracting 1 from the column.

If we know that the box is not on the boundary of the grid, then we can actually determine its location in just one visit: first we go right W-1 times, then move down once, so that we are in the cell (1,W-1). If the box is in the cell (1,W-2), then we are already directly to the right of it, as we need for the above approach. So from this point on we move only using the special sequences mentioned above, to avoid losing the box if we have already found it. First we use the "down" sequence H-3 times, so that if the box is in the column W-2, we find it and stick to it. Then we use the "left" sequence once, then the "up" sequence H-3 times, then the "left" sequence once, and so on.

How do we deal with the boundary? Since the boundary has not so many cells, my approach was to try different ways of going through those cells, and to see if the final location will tell us enough information if one of those cells contained an obstacle. After a couple of experiments, the following approach bore fruit: during the first visit, we go right W-1 times, then down H-1 times, then left W-2 times.

If there was an obstacle in row 0, we hit it when going right, so we went right at most W-2 times, and therefore we end up in the cell (H-1,0). If there was an obstacle in cell (R,W-1) for any R>0, we hit it when going down, so we end up in the cell (R-1,1). If there was an obstacle in cell (H-1,C) for any 0<C<W-1, we hit it when going left, so we end up in the cell (H-1,C+1). Finally, if we did not hit any obstacles we end up in the cell (H-1,1).

It means that if the obstacle was on the right or bottom boundary, we already know its location, if it's on the top boundary, we know it's there but don't know the exact location, and if it's on the left boundary or inside the grid, we still do not know anything. Dealing with the top boundary is easy: during the second visit we just go right W-1 times and see where we stop.

Now we just need to deal with the case where the obstacle is inside the grid or on the left boundary. We have described the approach for the obstacle inside the grid above, but one can notice that it also works for the left boundary if we end up walking through column 1 using the "down" sequences. This happens automatically if W is even, and if W is odd, we can change the direction once to achieve this, for example we can start from (H-2,W-1) instead of (1,W-1) in the very beginning. Therefore we can find the box during the second visit in this case as well.

This solution uses about 5*H*W moves, because our sequences for "down" and "up" have 5 moves each. However, one can process the "down" and "up" moves in batches: to move up many times, one can do v<^^^...^^^>^, which brings the number of moves per cell of the grid to 1, notwithstanding a linear number of additional moves: H*W+O(H+W) (the number of moves during the first visit is linear, so it does not change anything). I like it because it's asymptotically optimal: it is not hard to prove that we must try to enter each cell except maybe one at least once, so we need at least H*W-2 moves in any solution.

A few days later, I've noticed a different way to look at my solution: if we forget about the boundaries of the grid for a second and assume it is infinite (but the box is still within the given rectangle), then under certain assumptions the problem is equivalent to the following: the box is actually movable (like in the Sokoban game), and we need to bring it to a concrete location no matter where it starts. To see this eqivalence, we can say that every time we try to move towards the box and can't, we can shift the coordinate system by 1 instead, which means that the immovable box has effectively moved :) And I think the solution is much easier to find in this equivalent formulation.

Note that the author's solution is completely different: it needs to divide the grid into two halves! However, it also has the property of using only H*W+O(H+W) moves in total. Did you end up using an approach that differs from both?

Thanks for reading, and check back next week!