EmeraldBlock's blog

By EmeraldBlock, history, 10 months ago, In English

IOI 2023 Robot Contest is a great task that reminds me of Turing machines and cellular automata.

If the task statement is too intimidating...

The model solution is in $$$Z^\star = 6$$$. Let's do it in $$$Z^\star = 5$$$!

Besides color $$$0$$$ ("blank") and color $$$1$$$ ("path"), colors $$$2,3,4,5$$$ will represent the cardinal directions. Call them "arrows".

In the first phase, we run a BFS which works as follows:

  • Invariant: The graph formed by following the arrows forms a tree that converges to two arrows pointing to each other, with Pulibot on one of these two arrows, or to a blank cell, with Pulibot on said cell.
  • To begin this phase, we have the special case that, if Pulibot is on a blank cell and there is out-of-bounds to the west and north of Pulibot, it will change its cell to a south arrow and move south, unless there is an obstacle there, in which case it will do the same thing but with east. (We make the first move immediately to avoid ambiguities with the second phase.)
  • If Pulibot is on an arrow, it rotates said arrow counterclockwise (a nonzero amount) until it points to either a blank cell or an arrow that points back. It then moves to this cell.
  • If Pulibot is on a blank cell, it finds the unique arrow pointing to it and moves to it, changing the current cell to an arrow pointing in the direction it moved.

This procedure traverses the tree and expands it one node whenever Pulibot encounters a blank cell. By transitioning based on rotating arrows, we guarantee that we visit each branch of the tree exactly once each traversal, so this is a BFS and the path along the tree between the corners is a shortest path. A fun fact, if we view the edge formed by the two arrows pointing to each other as being "selected", this is an Euler tour!

Once we reach the southeast corner, we begin the second phase, which deletes the tree and leaves behind the path.

  • Invariant: The graph formed by following the arrows forms a tree that points to east of the northeast corner, with Pulibot on any arrow. This lets Pulibot figure out that it is in the second phase by noticing that it is not on an empty cell and its cell points to a cell that is not an arrow pointing back.
  • To begin this phase, we have the special case that, if Pulibot is on a blank cell and there is out-of-bounds to the east and south of Pulibot, it will change its cell to an east arrow and stay in place.
  • If an arrow points to Pulibot's cell, it moves to it (not changing the cell it is on). If there are multiple such arrows, choosing any works.
  • If no arrow points to Pulibot's cell, it moves to where its cell is pointing, unless it is already at the southeast corner, in which case it terminates. It replaces its cell with path if it is at the northwest corner or there is path adjacent to it, and with blank otherwise.

This phase runs a DFS that deletes (but doesn't modify) the tree by "falling" down to the leaves and "pulling" them up. The path between the corners will clearly be replaced with path, but what about other nodes? Since this tree is a BFS tree when rooted at the northwest corner, for every cell not on the shortest path that is adjacent to the shortest path, following arrows until reaching the shortest path must lead to a shortest path cell no farther from the northwest corner than the shortest path cell adjacent to the cell (otherwise connecting the cell to the adjacent shortest path cell would be a shorter path to the northwest corner). Since the tree is deleted depth-first when rooted at the southeast corner, it will be deleted before the adjacent shortest path cell becomes path.

And that's it! The task's API requires you to set the move for each specific set of colors, but it's much easier to write a function that calculates the move given the set of colors and loop over all possibilities.

Code

The code was tested on oj.uz.

Some background for what led to this

first post :D

Full text and comments »

  • Vote: I like it
  • +194
  • Vote: I do not like it