Editorial for WC '18 Finals S2 - Top Billing
Submitting an official solution before solving the problem yourself is a bannable offence.
.....
...#. .E ... ....
..#.. S. .#E ..#.
.#..E S.. .#.E
S.... S...
Fig 1. Fig 2.
Consider the layout for a grid with in figure 1. Tom Cows will reach the ending cell in minutes (for example by following the sequence of moves →→→→↑). On the other hand, Monkey Freeman will move as follows:
- Up (the cells above and to the right both have equal Manhattan distances of to the ending cell, so he'll choose the former)
- Up (similarly choosing it over moving down)
- Right (similarly choosing it over moving down)
- Up (similarly choosing it over moving left)
- Right (similarly choosing it over moving down)
- etc…
This pattern will repeat until Monkey reaches the grid's top-right cell, at which point he'll move straight downwards to the ending cell. For this particular grid, Monkey will require minutes, which is slower than Tom by the minimum required amount of minutes. More generally, this pattern can be extended to any square grid, as in the examples in figure 2.
For any such grid, Tom will need minutes while Monkey will need minutes, yielding the minimum required difference of . If we need to fill a non-square grid (such that ), then additional rows of vacant cells may simply be added below this pattern without affecting anything.
Comments