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!
Note: this is my solution and not the official solution from the editorial.
Imagine we have a magic function $$$f(L, R)$$$ that tells us how many solutions there are in the range $$$[L, R]$$$ if we only want to conquer the cities inside the range. Also, let's say that $$$len$$$ is the length of the range. Now, try to define that function recursively:
and so on. Subtracting $L$ on both sides gives us:
etc. The right side remains constant. Now, we can calculate a new array
We can now say:
Checking that can be done by a minimum segment tree. Checking if R is a valid solution can be done in a very similar fashion.
In the base case, you return 1, as a[i] will always be greater than or equal to 1 according to the problem’s constraints. I understand your solution; it’s making good use of the power of recursion. However, this approach is completely different from the one in the editorial, right? The editorial seems to be working with the intersection of ranges. First, they verify if there’s any solution by checking if, at time t, the range [L, R] ensures that every a[i] <= t is within the range, and the length of the range is less than or equal to t. They check this from t = 1 to t = n, as it needs to be true for lower values of t in order to proceed to higher ones. If a solution or strategy exists, they then intersect the ranges [(i — a[i] + 1), (i + a[i] — 1)] for each i. That’s a different approach. If you’ve figured that part out, could you kindly explain it as well? Thanks again for this beautiful solution.
No I haven't.