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!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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!
Название |
---|
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!