Editorial for WC '18 Finals S2 - Top Billing


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.
.....
...#.       .E  ...  ....
..#..       S.  .#E  ..#.
.#..E           S..  .#.E
S....                S...

Fig 1.         Fig 2.

Consider the layout for a grid with R = C = 5 in figure 1. Tom Cows will reach the ending cell in 5 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 4 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 11 minutes, which is slower than Tom by the minimum required amount of 2C-4 = 6 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 C minutes while Monkey will need 3C-4 minutes, yielding the minimum required difference of 2C-4. If we need to fill a non-square grid (such that R > C), then R-C additional rows of vacant cells may simply be added below this pattern without affecting anything.


Comments

There are no comments at the moment.