practice_has's blog

Codeforces 2018B Speedbreaker

By practice_has, history, 3 months ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

  1. If $$$a[L] < len$$$ and $$$a[R] < len$$$, then $$$f(L, R) = 0$$$, because there is no possible way to conquer all of these cities, since getting from one end of the segment to the other end requires at least $$$len$$$ steps.
  2. If $$$a[L] \geq len$$$ and $$$a[R] < len$$$: Then, $$$f(L, R) = f(L+1, R)$$$, because whatever "conquering plan" we find in the range $$$[L+1, R]$$$, we can simply extend the plan by conquering the city $$$L$$$ afterwards.
  3. If $$$a[L] < len$$$ and $$$a[R] \geq len$$$: Similar to case 2, but now we have $$$f(L, R) = f(L, R-1)$$$.
  4. If $$$a[L] \geq len$$$ and $$$a[R] \geq len$$$: First, calculate $$$f(L+1, R-1)$$$. Then, we have to check if $$$L$$$ and $$$R$$$ are valid solutions. Let's check for $$$L$$$ first. Since the range $$$[L, R]$$$ is a contiguous range, we would conquer city $$$L$$$ at time 1, then city $$$L+1$$$ at time 2, $$$L+2$$$ at time 3 and so on until conquering city $$$R$$$ at time $$$len$$$. It's pretty clear that the times at which we conquer are increasing by one from left to right. So, $$$L$$$ is a valid starting city if
$$$a[L] - 0 \geq 1,$$$
$$$a[L+1] - 1 \geq 1,$$$
$$$a[L+2] - 2 \geq 1$$$

and so on. Subtracting $L$ on both sides gives us:

$$$a[L] - L \geq 1-L, $$$
$$$a[L+1] - (L+1) \geq 1-L, $$$
$$$a[L+2] - (L+2) \geq 1-L, $$$

etc. The right side remains constant. Now, we can calculate a new array

$$$b_i = a_i - i$$$

We can now say:

$$$b_i \geq 1-L$$$ for all $$$L \leq i \leq R$$$

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand the range of cities part of the editorial either.

When I was thinking about the solution, I realized that for any index i, the starting point has to be in i-(a[i]-1) to i+(a[i]-1), because we reach the starting point at time 1 and we have a[i]-1 moves before we exceed the deadline for index i.

So any solution has to be in the intersection of all of the i-(a[i]-1) to i+(a[i]-1). (Alternate solution mentioned in the editorial.)

Now we can use the other part of the editorial to see if the solution of the intersection is possible. At any time t we have made t moves so the size of the covered range is t. We need to cover all a[i] <= t in this range. So we have to check if it is possible to cover all values <= t in an interval of size at most t.

For this, the precalculation is pretty smart, we find the first and last occurrence index of each value in the array. Then for first[t] we make it the minimum of first[1] to first[t] (easy to do in a loop) and similarly last[t] is the maximum of last[1] to last[t] — now the values of first[t] and last[t] are the ends of the subarray needed to cover all elements with a[i] <= t. We can check if the size of these intervals > t, in that case there is no solution. Otherwise, the solution is the intersection of all i-(a[i]-1) to i+(a[i]-1). Submission: 283410594

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, you perform the check from t = 1 up to t = n. If it fails for a lower t, the solution is invalid, so you can’t do it in reverse or in any random order. It will naturally hold for t = n because everything is within the array of size n, right? I’ve got the solution now—it was about intersecting ranges, as stated, and then verifying it by checking from t = 1 to t = n. The editorial explained it in the reverse order, which is why it didn’t make sense to me at first. Thanks, dude!

    → Reply