| Show all threads Hide all threads Show all messages Hide all messages |
| How to solve it? | Fdg | 1772. Ski-Trails for Robots | 8 Jul 2026 14:30 | 5 |
DP + sqrt-decomposition (or tree-like structure) I think that Djkstra in graph of robot's ends will work. No need for Dijkstra or sqrt decomposition :)
Nodes are (0,s), (i,l[i]-1), (i,r[i]+1) where applicable. The main idea is that you do not have to bend towards edges if you can go in a straight line, you can always make that adjustment later when necessary at the same cost. However, tracing all these rays for every obstacle will quickly MLE/TLE. To work around this you need to answer quickly location of nearest obstacle further ahead. This can be done with going back-to-front and paint over segment tree with lazy propagation. Nodes which have no obstacles ahead going in a straight line are terminal nodes (start may also be such, then the answer is 0). So it's K*log(N) to track those nearest obstacles for each of K*2+1 nodes, and then easy BFS from left to right. And don't forget about int64.
Edited by author 08.07.2026 23:27 (LLM-written, always verify, but current AC #1 beating all previous entries)
There’s another O(k log n) way: treat the current answer as a function of the trail number. After each obstacle this function is still made only of `+1/-1` linear pieces, and processing an obstacle just replaces its blocked interval by at most two new pieces. A lazy segtree is enough. |
| why I get wa on test 23? | Aneto | 1772. Ski-Trails for Robots | 8 Jul 2026 10:02 | 5 |
Try it:
8 3 3
2 4
5 8
1 6
Answer: 6 What is the answer for the test:
10 5 2
2 8
4 6
?
Mine is 4. Am I correct? Or is the answer 6 or 10?
L.E.: Nevermind I ACed. Answer is 4.
Edited by author 22.09.2010 20:24
Edited by author 24.09.2010 01:45 I had RE23 because of this
vector<int> l(n), r(n); // should be 'k' |
| WA #23 try this | ivanzakharov | 1772. Ski-Trails for Robots | 18 May 2021 18:40 | 2 |
10 4 2
1 2
8 10
answer: 0
11 6 3
1 2
10 11
5 7
answer: 2
Edited by author 06.03.2021 15:54 |
| WA 27 | moji | 1772. Ski-Trails for Robots | 16 Jul 2013 08:52 | 2 |
WA 27 moji 16 Jul 2013 08:42 very usual segment tree, that helps to fill dynamic vars.
I wonder if anyone have been had the same problem...
help! found it; I wasn't careful about the length of the array.
Edited by author 16.07.2013 08:53
Edited by author 16.07.2013 08:53 |
| need algorithm for 1772. Ski-Trails for Robots | sure | 1772. Ski-Trails for Robots | 22 Mar 2012 22:52 | 1 |
actually i dont have any idea for this my sir gave me this assessment i want to solve this problem please help me how to start the program and which concepts we want to use
|
| if you have wa 23 try this | Olya Chistokova | 1772. Ski-Trails for Robots | 12 Jan 2012 10:41 | 1 |
6 2 3
4 5
2 3
4 5
answer is 1 |
| To admins | Aleksandr Konovalov | 1772. Ski-Trails for Robots | 11 Jan 2012 01:10 | 2 |
To admins Aleksandr Konovalov 10 Jan 2012 22:37 Hello!
I found the following interesting test:
n 1 n
1 1
2 2
3 3
...
n-1 n-1
1 n-1
where n is a large number (such as 100000)
The result is n-1 |
| Shortest Path Algorithm does work | Marshall Mathers | 1772. Ski-Trails for Robots | 5 Jun 2011 21:32 | 1 |
|
| Test 6 | Marginean Ciprian | 1772. Ski-Trails for Robots | 5 Jun 2011 08:25 | 2 |
Test 6 Marginean Ciprian 24 Sep 2010 15:40 I was talking bullshit if you read this before.
Test 6 has k = 0, that was my problem.
Edited by author 24.09.2010 19:18 |
| WA15 | Marginean Ciprian | 1772. Ski-Trails for Robots | 21 Sep 2010 15:44 | 1 |
WA15 Marginean Ciprian 21 Sep 2010 15:44 I use sqrt decomposition and some DP.
My DP idea is to keep for each robot the shortest path which we can find if we detour by left or right. And I use sqrt decomposition to find the next encountered robot on the current path.
Could someone give me a tricky example?
Edit: I wrote the update of the sqrt decomposition again(different) and now I get WA23.
Edited by author 22.09.2010 15:13 |
| why I get wa on test 34? | Sergey Martynov | 1772. Ski-Trails for Robots | 8 Aug 2010 20:18 | 1 |
|
| No subject | lql1993 | 1772. Ski-Trails for Robots | 10 May 2010 21:07 | 2 |
why I get wa on test 39?
Edited by author 30.04.2010 17:12 |
