can anybody please share the solution or the thought process of this problem? i am really having a hard time on it https://mirror.codeforces.com/gym/105192/problem/D Thanks!
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 2 | awoo | 163 |
| 4 | TheScrasse | 154 |
| 5 | nor | 153 |
| 6 | maroonrk | 152 |
| 6 | -is-this-fft- | 152 |
| 8 | Petr | 145 |
| 9 | pajenegod | 144 |
| 9 | orz | 144 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/20/2024 18:13:23 (k2).
Desktop version, switch to mobile version.
Supported by
Auto comment: topic has been updated by SkyMagic (previous revision, new revision, compare).
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.
Consider any straight line in the plane. Now plot the Euclidean distance to a fixed point along the line. This will have a minimum, and increase monotonically in both directions. So when you have some interval along the line, the maximum in the interval will always be at either end of the interval. Consider all points you can reach in a certain number of steps. The set of points forms a diagonal square. All points in this square except its four corners (corresponding to picking a direction and sticking to it) are in the middle of some line segment entirely contained within the square, so cannot be optimal. (This argument is continuous while the actual problem is discrete, so it doesn't quite work, but it can be modified to work.)
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)$$$.
Thank you very much!