PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming
PROBLEM:
A robot is programmed to move a_0 steps forward, and then turn left or right, then a_1 steps forward, and then turn left or right, and so on until a_N. You can increase or decrease a_i, but this takes one second and you must keep each a_i positive. You can also choose the turning direction freely, with no time cost. What is the minimum number of seconds needed so that the robot goes back exactly to its starting point? Or determine if it’s impossible.
QUICK EXPLANATION:
If N < 3, then it’s impossible.
Otherwise, split the $a_i$s into two lists: one for odd and one for even vertices. For each list, say b_1, b_2, \ldots, b_m, find the minimum absolute value of their sum obtained by giving a sign to each b_i (positive or negative). This can be done with dynamic programming. Let F(i,s) be the smallest absolute value sum assuming you need to give signs to the first i values, and the sum of the remaining values is s. Then the answer must be F(m,0), and F(i,s) has the following recurrence:
The base case is F(0,s) = s. Thus, you can compute F(m,0) by computing all F(i,s) in increasing order of i.
EXPLANATION:
Horizontal and vertical
The fact that you can only turn 90 degrees either clockwise or counterclockwise tells us quite a few details about the directions of the i th movement. This is due to the fact that the i th movement is perpendicular to the $(i+1)$th movement, which means:
- The 0 th movement is vertical. (In fact, it’s always upward.)
- The 1 st movement is horizontal.
- The 2 nd movement is vertical.
- The 3 rd movement is horizontal.
- The 4 th movement is vertical.
- etc.
And since we can select which way to turn at every point (at no cost), we can select which (vertical or horizontal) direction each movement goes to, except the 0 th movement which is always upward. But we want the robot to return the starting point, which means the overall horizontal and vertical movement must be 0 individually. Formally, this is the same as giving signs to the movements so that the overall sum is 0.
This reduces our problem to two separate subproblems, one for the list [a_0, a_2, a_4, \ldots], and another for [a_1, a_3, a_5, \ldots]. The subproblems are identical in nature:
Given a list [b_1, b_2, b_3, \ldots, b_m], what is the minimum number of modifications needed so that it’s possible to give signs to them so that the overall sum is 0.
The answer is the sum of the two answers, so let’s focus on this subproblem instead.
Subset sum to zero
As a special case, note that if m = 1, then the answer is NO immediately, because in this case there is only one summand, and it must stay positive, so there’s no way you can change that to make a sum of 0. However, if m > 1, then we can show that it’s possible. Indeed, we can increase/decrease b_m until it becomes equal to b_1 + b_2 + \ldots + b_{m-1}, and then we can make everything positive except for b_m, and the sum will be zero. The problem now is to find the minimum number of modifications.
If it’s already possible to give signs to [b_1, b_2, \ldots, b_m] so that the overall sum is 0, then the answer is already 0. But how do we know that?
Notice that this is similar to the subset sum problem (in fact, you can reduce this problem to the subset sum problem), but instead of selecting a subset, we’re selecting signs instead. This can be solved with dynamic programming: Let F(i,s) be the answer to the following question: Is it possible to give signs to [b_1, b_2, \ldots, b_i] so that the overall sum is s? The original problem amounts to checking whether F(m,0) is true.
To compute F(i,s), we consider two cases, depending on the sign of b_i in the sum:
- If b_i is positive, then for the sum to be s, the sum of the remaining elements must be s - b_i. This is possible if F(i-1,s-b_i) is true.
- If b_i is negative, then for the sum to be s, the sum of the remaining elements must be s + b_i. This is possible if F(i-1,s+b_i) is true.
Thus, F(i,s) = F(i-1,s-b_i) \vee F(i-1,s+b_i). For the base case, we can say F(0,0) = \text{true} and F(0,s) = \text{false} if s \not= 0. Using this recurrence, we can now compute F(m,0) with memoization. Note that the maximum absolute value of s we will encounter is \sum_i b_i, which is not that large. This gives us an O(m \sum_i b_i) algorithm to compute F(m,0) with memoization.
So we can now know if 0 is already achievable without modifications. But what if it’s not? Then we must find the minimum number of modifications needed. In each modification, you’re allowed to increase or decrease any b_i. But notice that this operation only adjusts the final sum by 1, so if the minimum absolute value sum that can be achieved in the first place is s_{\min}, then you will need at least |s_{\min}| modifications. But is this number of changes achievable?
Yes! Here’s one way to do it:
- Suppose s_{\min} > 0. Let b_i be an element which you assigned a negative sign. Then we can increase b_i s_{\min} times, and then the sum becomes 0. Note that we increased b_i so it will surely be positive.
- Suppose s_{\min} < 0. Let b_i be an element which you assigned a positive sign. Then we can increase b_i |s_{\min}| times, and then the sum becomes 0. Note that we increased b_i so it will surely be positive.
The reason this works is because if m > 1, then at least one summand will be assigned a positive sign and at least another one will be assigned a negative sign. Otherwise, they all have the same sign, and in that case we can flip the sign of any summand and get a sum with a lower absolute value!
Thus, the answer must be |s_{\min}|. All that remains is actually computing s_{\min}. Well, we can use our function F for this! Simply compute F(m,s) for all |s| \le \sum_i b_i, and find s_{\min} as the number with the smallest absolute value such that F(m,s_{\min}) is true.
Optimizations
Here are some tips to optimize this DP solution:
- Only compute F(i,s) for nonnegative s by using the fact that F(i,s) = F(i,-s). This is true because if you can achieve the sum s, then you can achieve the sum -s by simply flipping the signs! This reduces the number of states by half.
- Instead of doing a top-down approach as the above, you can do a bottom-up approach, i.e., you start at F(0,0) = \text{true}, and figure out which F(i,s) are also true by working bottom-up, using a BFS/DFS approach. This will guarantee you’ll only generate the important cases.
- You can ignore F(i,s) if s exceeds \frac{1}{2} \left(\sum_i b_i\right) + 500. This is because if s far exceeds half the total sum, then you can simply make the remaining values negative to get the smallest possible sum. Therefore, cases with really large s won’t yield you the smallest possible sum. The 500 is there to handle tricky cases where m is odd.
Time Complexity:
O(N \sum a_i)
They’re so awesome … at screwing up! I did the same as you, and rejected this idea.