Editorial for ICPC PACNW 2016 B - Buggy Robot - Olympiads Online Judge

Editorial for ICPC PACNW 2016 B - Buggy Robot

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First, to simplify implementation, note that we only need to consider additions (deletions can be transformed to additions). Consider a graph where nodes are $(\text{state}, \text{number of commands followed})$ $(state, number of commands followed)$ . There are $50^3$ $50^{3}$ nodes in this graph, and $50^3 \times 5$ $50^{3} \times 5$ edges ( $1$ $1$ edge for following the next valid command, $4$ $4$ edges for inserting an arbitrary command before).

Now, note the shortest path from the $(\text{robot square}, 0)$ $(robot square, 0)$ to some node $(\text{exit square}, t)$ $(exit square, t)$ for any $t$ $t$ is the solution.

The edge weights are $0$ $0$ or $1$ $1$ , so this can be solved with BFS, though Dijkstra's will also pass.

Comments

There are no comments at the moment.