Codeforces 2018B Speedbreaker

Revision en1, by practice_has, 2024-09-28 23:19:37

Hi everyone, I’m having trouble understanding the editorial for the problem Speedbreaker, and I haven’t been able to find a clear explanation, either in the comments under the editorial or on YouTube. Could someone explain the approach in detail for a beginner like me? I don’t understand how city i, after being chosen as a starting city, can be verified as a valid starting city. How do you check or confirm this? What is the method for selecting the next set of adjacent cities, and in what order should this be done? Is it done greedily, or is there a particular strategy involved? Please explain everything from scratch. Additionally, how can the range of cities from l = max(l, i — a[i] + 1) to r = min(r, i + a[i] — 1) be considered valid starting cities? The editorial seems too straightforward, and I’m having difficulty understanding the underlying intuition. I’ve spent a day on this but still can’t figure it out. Could someone please explain the approach in a way I can understand? It would be a huge help!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English practice_has 2024-09-28 23:19:37 1110 Initial revision (published)