Official

D - Robot Arms 2 Editorial by en_translator


The idea of this problem was originally proposed by Keyence.

First, consider a simple situation, one-dimensional version, which is like:

Is it possible to place \(p_1, p_2, \dots, p_{N+1}\) on a number line so that

  • \(p_1=0,p_2=A_i, p_{N+1}=x\);
  • \(\vert p_i - p_{i+1} \vert = A_i\)?

\(1 \leq A \leq A_{\max}, 2 \leq N \leq N_{\max}\)

This is an educational DP (Dynamic Programming) problem, which you can solve as follows:

  1. Let \(dp\) be a boolean array with indices between \(-A_{\max}N\) and \(A_{\max}N\). Initially, let \(dp_{0} = \text{true}\) and \(\text{false}\) for other indices.
  2. For each \(i=1, 2,\dots,N\), update \(dp\) as follows:
     a. Prepare a new boolean array \(nxtdp\) with the same indices as \(dp\). Initialize \(nxtdp\) with \(\text{false}\).  b. For each \(j = -A_{\max}N, \dots, A_{\max}N\), perform the following if \(dp_{j} = \text{true}\):   I. If \(j + A_i \leq A_{\max}N\), then let \(nxtdp_{j + A_i} \gets \text{true}\).   II. If \(i \geq 2\) and \(j - A_i \geq -A_{\max}N\), then let \(nxtdp_{j - A_i} \gets \text{true}\). (We guard with \(i \geq 2\) so that \(p_1 \to p_2\) is in the positive direction.)
     c. Let \(dp \gets nxtdp\).
  3. If \(dp_x = \text{true}\), then the answer is Yes; otherwise it is No.

The complexity is \(\mathrm{O}(N^2 A_{\max})\), which is fast enough.

Let’s get back to the original problem. Considering the relation between \(p_i\) and \(p_{i+1}\), it will be like:

  • \(p_1 \to p_2\) moves \(A_1\) in the positive direction of \(x\) axis;
  • \(p_n \to p_{n+1}\) (where \(n\) is a \(3\)-or-greater odd number) moves \(A_i\) or \(-A_i\) in the positive direction of \(x\) axis;
  • \(p_n \to p_{n+1}\) (where \(n\) is an even) moves \(A_i\) or \(-A_i\) in the positive direction of \(y\) axis.

Additionally, if \(n\) is odd, even if we flip the direction of \(p_n \to p_{n+1}\) to one of the positive or negative direction of \(x\) axis to another without changing the other, it does not affect to the \(y\) coordinate of \(p_{n+1}\) (and vice versa).
Therefore, we can solve this problem independently for \(x\) and \(y\) axis. That is,

  • solve the one-dimensional problem for a sequence \(A_o = (A_1, A_3, A_5, A_7,\dots)\) and destination \(x\);
  • solve the one-dimensional problem for a sequence \(A_e = (A_2, A_4, A_6, A_8,\dots)\) and destination \(y\) (where we allow the first element of \(A_e\) to be either positive or negative.).

If the answer to both case is Yes, then the answer for the entire problem is Yes; otherwise, the answer is No. The complexity is \(\mathrm{O}(N^2 A_{\max})\), which is fast enough to solve this problem.

posted:
last update: