Let \(\displaystyle \max_{1\leq i \leq N}D_i=M\). We know from the triangle inequality that it is impossible to return to the origin after \(N\) actions when \(\sum_{i=1}^{N}D_i < 2M\). From now on, we will assume that \(2M \leq \sum_{i=1}^{N}D_i\).

[1] Considering changes in distance from the origin due to movement

For real numbers \(D\), \(R\), \(R'\ (R' \leq R)\) and \((a, b)\ (0 \leq a, b)\) satisfying \(|a|+|b|=R\), we consider the conditions under which \((a', b')\) exists that satisfy:

• \(|a'|+|b'|=R'\), and
• \(|a-a'|+|b-b'|=D\).

From the triangle inequality, it is necessary that \(R-R' \leq D \leq R+R'\).

(In the figure below, the Japanese text says: “The distance between A and B is R-R’, and the distance between A and C is R+R’.”)

For \(D=R-R'\), when \(0 \leq a \leq R'\), the two conditions are satisfied by \((a',b')=(a,b-(R-R'))\) satisfies, and when \(R' \leq a \leq R\), they are satisfied by \((a',b')=(a-(R-R'),b)\) (\(A\) and \(B\) in the figure above).

Also, for \(D=R+R'\), when \(0 \leq a \leq R'\), the two conditions are satisfied by \((a',b')=(-a,(R-R')-b)\), and when \(R' \leq a \leq R\), they are satisfied by \((a',b')=((R-R')-a,-b)\) (\(A\) and \(C\) in the figure above).

From the above, for any \((a, b)\), there is always an \((a', b')\) that satisfies the conditions when \(D=R-R',R+R'\), and since \(|a-a'|+|b-b'|\) changes continuously as \((a', b')\) moves on \(|x|+|y|=R'\), such a pair always exists when \(R-R' \leq D \leq R+R'\).

The same conclusion can be obtained for the case of \(R < R'\) by considering it in reverse.

The particularly important points in the discussion so far can be summarized in the following two points:

• for any \((a, b)\) and \(D\) satisfying \(|R'-R| \leq D \leq|R+R'|\) and |a|+|b|=R\(, the above \)(a,‘b’)$ exists;
• for any \((a, b)\) and \(D\) satisfying \(0 \leq D \leq 2R\) and \(|a|+|b|=R\), there is an \((a', b')\) satisfying \(|a'|+|b'|=R\) and \(|a-b'|+|a-b'|=D\).

[2] The decision problem with fixed order

We consider the decision problem of whether it is possible to finish \(N\) actions with \(|x_i|+|y_i| \leq K\) when the moving distance in the \(i\)-th action is fixed to \(D_i\). First of all, it is necessary that \(D_i \leq 2K\).

Let \(S_i=D_1+D_2+\dots+D_i\) and \(T_i=D_i+D_{i+1}+\dots+D_N\).

Let \(L\) be the smallest \(i\) satisfying \(K \leq S_i\). From the triangle inequality, it is necessary that \(D_L \leq S_{L-1}+K\). If this is satisfied, you can be at any point on the outer circumference ( \(|x|+|y|=K\) ) after \(L\) actions, as seen from the discussion in [1]. Similarly, let \(R\) be the largest \(i\) satisfying \(K \leq T_i\), and then it is necessary that \(D_{R} \leq T_{R+1}+K\). If this is satisfied, you can always return to the origin no matter where you are on the outer circumference after \(R-1\) actions.

Then, if you can start and finish the \((L+1)\)-th to \((R-1)\)-th actions on the outer circumference, you can also finish \(N\) actions with the conditions satisfied. This is indeed possible since it is always possible to stay on the outer circumferences, as seen from the discussion at the end of [1].

Therefore, if \(L\) and \(R\) exist and \(L < R\), the following are the necessary and sufficient conditions.

• \(D_i \leq 2K\)
• \(D_L \leq S_{L-1}+K\)
• \(D_R \leq T_{R+1}+K\)

Let’s consider the other cases.

If the sum of \(D_i\) is less than or equal to \(2K\), the objective is always achievable.

Proof

Let \(k\) be the smallest \(i\) satisfying \(\frac{S_N}{2} \leq S_i\), and let \(a=\frac{S_N}{2} - S_{k-1}, b = S_k - a\).

Consider the following \(S_N\) moves.

• From the \(1\)-st to \(b\)-th move: move from \((x,y)\) to \((x,y+1)\).
• From the \(b+1\)-th to \(\frac{S_N}{2}\)-th move: move from \((x,y)\) to \((x+1,y)\).
• From the \(\frac{S_N}{2}+1\)-th to \(\frac{S_N}{2}+b\)-th move: move from \((x,y)\) to \((x,y-1)\).
• From the \(\frac{S_N}{2}+b+1\)-th to \(S_N\)-th move: move from \((x,y)\) to \((x-1,y)\).

These moves can be grouped into \(D_i\) moves each (the first and third moves should not be mixed, but this does not happen since \(D_i \leq \frac{S_N}{2}\)). The maximum Manhattan distance from the origin during the moves is \(\frac{S_N}{2} \leq K\), so \(|x_i|+|y_i| \leq K\) always holds.

If the sum is greater than \(2K\), then \(L\) and \(R\) do exist, and \(L=R\). First, the above three conditions must be satisfied. If they are satisfied, consider the following way to make \(N\) actions: move to a lattice point \(S_{L-1}\) away from the origin → move exactly \(D_L\) to a lattice point \(T_{R+1}\) away from the origin → return to the origin, which is possible if \(|S_{L-1}-T_{R+1}| \leq D_L \leq S_{L-1}+T_{R+1}\) is satisfied. The first inequality can be seen to hold from \(S_{L-1} < K \leq T_{R+1}+D_L, T_{R+1} < K \leq S_{L-1}+D_L\). The second inequality can also be seen to hold from [1]. Therefore, also in this case, the above three conditions are necessary and sufficient.

[3] The decision problem without fixed order

Based on the discussion in [2], we consider the decision problem when the order of \(D_i\) is not fixed. First, if \(M \leq K\), it is always possible to finish \(N\) actions with the conditions satisfied. From now on, we will deal with the case where \(\frac{M}{2} \leq K < M\).

In this case, \(L\) and \(R\) considered in [2] always exist. If there is only one \(D_i\) greater than \(K\) (i.e., only \(M\)), the answer to the decision problem does not change because we can put another \(M\) in \(D_i\) and perform the moves with a distance of \(M\) consecutively. Therefore, we only need to consider the case where there are at least two \(D_i\)’s greater than \(K\).

In this case, since \(L < R\) always holds, the decision problem can be reduced to whether we can create two sets \(\{i_1, i_2, \dots, i_n\}\) (without common elements) that satisfy the following conditions:

• \(D_{i_1} + D_{i_2} + \dots D_{i_{n-1}} < K\),
• \(K \leq D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}+D_{i_n}\), and
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\).

From the first condition, we have \(D_{i_k} < K\ (k\neq n)\). If \(D_{i_n} \leq K\), the third condition always holds. Now, if the first condition does not hold while \(D_{i_k} < K\ (k\neq n)\) is satisfied, we can recreate a set that satisfies these conditions by properly removing \(i_k\). Therefore, we only need to create a set that satisfies the following conditions:

• \(D_{i_k} < K\ (k\neq n)\),
• \(K \leq D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}+D_{i_n}\), and
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\).

Furthermore, when \(D_{i_n} \leq K\) holds, we can add another \(D_i\) larger than \(K\) without violating these conditions (since there are at least two \(D_i\)’s larger than \(K\)). In this case, the second condition always holds, so the problem becomes whether we can create two sets \(\{i_1, i_2, \dots, i_n\}\) that satisfy the following conditions:

• \(D_{i_k} < K\ (k\neq n)\), and
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\).

It is clear that \(D_{i_n}\) should be as small as possible, so we should choose the two smallest \(D_i\)’s larger than \(K\). Therefore, we can reduce the problem to the following partial sum problem, where \(S\) is the sum of \(D_i\)’s less than or equal to \(K\), and \(A\) and \(B\) are the two smallest \(D_i\)’s larger than \(K\):

• Determine if there is a partial sum \(s\) of \(D_i\)’s less than or equal to \(K\) such that \(A-K \leq s \leq S-(B-K)\).

Let’s consider the case when \(S\) is very large. We will add \(D_i\) less than or equal to \(K\) in ascending order, and stop adding when the sum is greater than or equal to \(A-K\) to create a partial sum \(s\). Since the \(D_i\) being added are less than or equal to \(K\), we have \(s < A\), and this partial sum satisfies the above inequality if \(A+(B-K) \leq S\). In particular, if \(2M \leq S\), this inequality always holds, so we only need to consider the case when \(S < 2M\). In this case, the number of different values among \(D_i\)’s is \(O(\sqrt{M})\), so the partial sum problem can be solved in \(O(M\sqrt{M})\) time.

By using this to perform a binary search, the whole problem can be solved in \(O(M\sqrt{M}\log M)\) time. However, considering that there is always a partial sum satisfying the above when there are two \(D_i\)’s between \(\frac{M}{2}\) and \(K\), inclusive, we only need to consider at most two sets of \(D_i\)’s less than or equal to \(K\), so the problem can be solved in \(O(M\sqrt{M})\) time.