Блог пользователя SkyMagic

Автор SkyMagic, история, 6 месяцев назад, По-английски

can anybody please share the solution or the thought process of this problem? i am really having a hard time on it https://codeforces.me/gym/105192/problem/D Thanks!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by SkyMagic (previous revision, new revision, compare).

»
6 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

First, consider the problem without the trees. It should be fairly intuitive that it's never worth it to change direction in this simpler version – just pick a direction and keep going there.

Formal argument

Now, look at what happens once you are wrapped around a tree. By again picking a direction and repeatedly going there, you can increase the length of the leash by 1 unit per step. This is clearly optimal – you can't increase the length by more than the distance you move. Thus, it's never useful to wrap around more than one tree.

So, we can just try wrapping around every tree (look at each tree, compute time to get there (Manhattan distance) and length of the leash at the tree (Euclidean distance), and add the time remaining after reaching the tree to the length of the leash), and also try not wrapping around any tree (e.g. try all four directions). Then take the maximum. This runs in $$$\mathrm{O}(n)$$$.