I enjoyed yesterday's qualification round of Google Code Jam 2011. Once figured out, the problems are arguably straightforward. Code Jam website also provides informative explanation for the solutions to each problems.

Nevertheless, I want to chip in on the Bot Trust problem. Code Jam's solution is a straightforward one, though I find that my solution is more concise yet still simple to understand. Let's look at the code:

The idea is simple, as the problem wants the minimum time to complete the order, this algorithm does exactly that without the need for calculation at every time increment. Instead, it iterates through each command and calculates the time the corresponding bot completed the command. Last location and time of both bots are maintained. If the time a bot uses is less than the current time, it means that the bot moved in place earlier but has to wait for the other bot to push the switch, hence the time it takes is either its moving time or the latest time, whichever is larger. The +1 at the end is the time used to push the switch.

May 08, 2011