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:
- 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.
- 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\).
- If \(dp_x = \text{true}\), then the answer is
Yes
; otherwise it isNo
.
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: