Official

D - AtArcher Editorial by evima

The closer to the center, the higher the score is. This property of the target is the key to the problem.


Table of contents

The solution to this problem has four steps.

  • Step 1: The pattern of the optimal solution
  • Step 2: Reduce it to a brute-force problem
  • Step 3: Make it faster (1)
  • Step 4: Make it faster (2)

Then, we summarize the solution in Section 5 and show sample implementations (C++ and Python) in Section 6. If you are in a hurry, go to Section 5.


Step 1: The pattern of the optimal solution

The target gives higher scores to arrows that are closer to the center. Let us consider the way arrows are shot in the optimal solution.

The first thing to note is that the arrows should be “centered” for a higher score.

In the figure above (with \(D = 3\)), the score is improved by centering the arrows. Since the score for each arrow never decreases by this, the total score never decreases, either.

After centering the arrows as much as possible, the arrows will be evenly spaced, with coordinates \(x, x+D, x+2D, \dots, x+(N-1)D\). In the above figure, \(x = -5\).

Now, let us try to brute-force this pattern of the optimal solution, in the following sections.


Step 2. Reduce it to a brute-force problem

First, by centering the arrows, it is always possible to make \(-(N-1)D \leq x \leq 0\) hold, because:

  • if \(x \lt -(N-1)D\), the arrows can be further centered by moving them to the right;
  • if \(x \gt 0\), the arrows can be further centered by moving them to the left.

Also, we can limit \(x\) to be an integer, because if \(x\) is not an integer, changing it to the closest integer does not change the score.

Thus, if we try the \((N-1)D+1\) ways to shoot the arrows, \(x = -(N-1)D, -(N-1)D+1, -(N-1)D+2, \dots, -1, 0\), the highest score obtained is the answer.

Finding the total score for one \(x\) would take \(O(NM)\) time if implemented naively, so let us try to find the number of arrows in each segment using divisions. It can be calculated that the number of arrows in the segment \([L, R)\) is:

\[\max\left(\min\left(\left\lceil \frac{R-x}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L-x}{D} \right\rceil, N\right), 0\right)\]

because:

  • the number of arrows with coordinates less than \(L\) is \(\max\left(\min\left(\left\lceil \frac{L-x}{D} \right\rceil, N\right), 0\right)\),
  • the number of arrows with coordinates less than \(R\) is \(\max\left(\min\left(\left\lceil \frac{R-x}{D} \right\rceil, N\right), 0\right)\).

We have to do this for \(2M-1\) segments, so the computation for each \(x\) now takes \(O(M)\) time.

Thus, we can solve the problem in a total of \(O(NMD)\) time, but under the constraints \(N \leq 10^5, M \leq 10^5, D \leq 10^6\), it is too slow.


Step 3: Make it faster (1)

Above, we brute-forced the cases \(x = -(N-1)D, -(N-1)D+1, -(N-1)D+2, \dots, -1, 0\), but we can narrow the range.

Look at the figure below. Although the arrows are centered, it intuitively looks suboptimal.

Why is it?

Because we can move the leftmost arrow at coordinate \(-11\) to the right end to increase the score. Here, the distance of that arrow from the center decreases from \(11\) to \(4\), and the other arrows do not move.

When can we move the leftmost arrow to the right end or move the rightmost arrow to the left end to make it closer to the center?

Moving the leftmost arrow to the right end

Consider moving an arrow at coordinate \(x\) to \(x+ND\). It will get closer to the center when \(-x \gt x+ND\), that is, \(x \lt -\frac{ND}{2}\).

Moving the rightmost arrow to the left end

Consider moving an arrow at coordinate \(x+(N-1)D\) to \(x-D\). It will get closer to the center when \(x+(N-1)D \gt -(x-D)\), that is, \(x \gt \frac{ND}{2}+D\).

Thus, the arrows cannot be further centered when \(-\frac{ND}{2} \leq x \leq -\frac{ND}{2}+D\). We can state that this range always contains the optimal solution.

That is, if we brute-force the \(D\) ways to shoot the arrows \(x = A, A+1, A+2, \dots, A+(D-1)\), where \(A = -\lfloor \frac{ND}{2} \rfloor\), the highest score obtained is the answer. (\(x = A + D\) is also in the range, but that case is symmetric to the case \(x = A\), with the same score.)

In the figure below, we now have to compute the score for just \(D = 3\) values of \(x\), compared to \((N-1)D+1 = 13\) above.

The total complexity has been reduced to \(O(MD)\), but still too slow under the constraints \(M \leq 10^5, D \leq 10^6\).


Step 4: Make it faster (2)

How to do it faster? Unfortunately, we cannot further narrow the range of search. It is desired to compute the total scores for \(x = A, A+1, A+2, \dots, A+(D-1)\) “at once”.

Previously, the computation was done as follows.

  • Compute the total score for \(x = A\), that is, the sum of \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) for \(x = A\).
  • Compute the total score for \(x = A+1\), that is, the sum of \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) for \(x = A+1\).
  • \(\vdots\)
  • Compute the total score for \(x = A+(D-1)\), that is, the sum of \(\left\{\min\left(\left\lceil \frac{R_i-x}{D} \right\rceil, N\right) - \max\left(\left\lceil \frac{L_i-x}{D} \right\rceil, 0\right)\right\}\times S'_i\) for \(x = A+(D-1)\).

Here, \(L_i, R_i, S'_i\) represent the \(i\)-th segment from the left with the range \([L_i, R_i)\) and the score \(S'_i\) (see the latter half of Step 2). Specifically, the positive score area of the target can be divided into \(2M-1\) segments, as follows.

  • \(L = (-x_M, -x_{M-1}, \dots, -x_2, -x_1, x_1+1, \dots, x_{M-2}+1, x_{M-1}+1)\)
  • \(R = (-x_{M-1}, -x_{M-2}, \dots, -x_1, x_1+1, x_2+1, \dots, x_{M-1}+1, x_M+1)\)
  • \(S' = (s_{M-1}, s_{M-2}, \dots, s_1, s_0, s_1, \dots, s_{M-2}, s_{M-1})\)

Let us try to do this computation from another direction, as follows.

  • First, initialize the total scores \(v_0, v_1, \dots, v_{D-1}\) for \(x = A, A+1, \dots, A_{D-1}\) to \(0\)s.
  • Add the contributions of Segment \(1\) to the total scores. That is, for \(k = 0, 1, 2, \dots, D-1\), add \(\left\{\max\left(\min\left(\left\lceil \frac{R_1-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_1-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_1\) to \(v_k\).
  • Add the contributions of Segment \(2\) to the total scores. That is, for \(k = 0, 1, 2, \dots, D-1\), add \(\left\{\max\left(\min\left(\left\lceil \frac{R_2-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_2-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_2\) to \(v_k\).
  • \(\vdots\)
  • Add the contributions of Segment \(2M-1\) to the total scores. That is, for \(k = 0, 1, 2, \dots, D-1\), add \(\left\{\max\left(\min\left(\left\lceil \frac{R_{2M-1}-(A+k)}{D} \right\rceil, N\right), 0\right) - \max\left(\min\left(\left\lceil \frac{L_{2M-1}-(A+k)}{D} \right\rceil, N\right), 0\right)\right\}\times S'_{2M-1}\) to \(v_k\).

The values to add, which may look complicated, represent the number of arrows in Segment \(i\) (see the latter half of Step 2). This number changes at most twice: when the value \(\left \lfloor \frac{L_i - (A+k)}{D} \right \rfloor\) changes, or the value \(\left \lfloor \frac{R_i - (A+k)}{D} \right \rfloor\) changes. Thus, the values to be added in each step, \(v_0, v_1, v_2, \dots, v_{D-1}\), look as \(a, a, \dots, a, b, b, \dots, b, c, c \dots, c\): we just add the same value to at most three segments.

Adding the same value to a segment can be done fast by utilizing prefix sums, which allows us to find the final values of \(v_0, v_1, \dots, v_{D-1}\) in \(O(M+D)\). The answer is the largest among them.


5. Summary

The problem can be solved in the following steps.

  1. Restrict the arrows to be at \(x, x+D, x+2D, \dots, x+(N-1)D\) for some \(x\), after which the optimal solution can still be obtained.
  2. Further limit the options to the \(D\) cases \(x = A, A+1, A+2, \dots, A+(D-1)\) where \(A = -\left\lfloor \frac{ND}{2} \right\rfloor\), after which the optimal solution can still be obtained.
  3. The positive score area of the target can be divided into \(2M-1\) segments. For each of them, add its contributions to the total scores for the cases \(x = A, A+1, A+2, \dots, A+(D-1)\) all at once, utilizing prefix sums, to compute the scores for all cases in \(O(M+D)\) time.
  4. The answer is the largest value computed in 3.


6. Sample Implementations

posted:
last update: