A directly opposite week

Code Festival 2017 onsite for university students and recent graduates ran by AtCoder was the biggest event of the Nov 20 - Nov 26 week. It consisted of multiple rounds, but the main and rated one was the Final (problems, results, top 5 on the left, parallel round results, analysis). The problemset has provided a lot of variety, and the people at the top had quite different sets of problems solved. tourist was quite a bit faster than others — big congratulations on the victory!

The Open Cup continued its weekly cadence with the Grand Prix of Europe on Sunday (problems, results, top 5 on the left, CERC results on the same problems). Team japan02 had 10 problems solved even before the last hour, but could not make further progress and allowed ITMO 1 to steal the victory with two minutes to go — congratulations to both teams solving 10 problems, and to the Warsaw team who got 10 at the onsite round, also with a last-minute accepted submission!

In my previous summary, I have mentioned an interactive Open Cup problem happening on the faces of a cube with each face divided into n times n cells (n<=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100n commands.

The solution that we got accepted looked like this: first, we try to move closer to the goal whenever we can, until we reach a cell from which all four moves don't give us a "closer" reply. This can be coded with a simple loop without the need to remember the coordinates or to even represent the sides of the cube, and will always converge in O(n) steps.

Then, we're either in the goal cell or in the cell directly opposite it on the opposite face. We don't know the size of the cube, but even without it in order to transition from one to the other we can walk forward while we're not seeing a "closer" answer, and then keep moving forward while we're seeing "closer" answer. If we were in the opposite cell, we will reach the goal. If we were in the goal, then we'll either be in the opposite cell, or in the goal again after making a full loop. To distinguish the cases, we can compare the number of moves in the "not closer" state to the number of moves in the "closer" state. In case the former is bigger than the latter, we started our forward walk in the goal, and we will undo all those moves to go back to the goal. In case the latter is bigger, we're done.

It takes some case studying and convincing oneself that this approach works in various corner cases as well, but after that the actual implementation is just a few lines.

Thanks for reading, and check back for more!