PROBLEM LINK:Author: 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: $$F(i,s) = \min(F(i1,sb_i), F(i1,s+b_i))$$ 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 verticalThe 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:
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 zeroAs a special case, note that if $m = 1$, then the answer is 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:
Thus, $F(i,s) = F(i1,sb_i) \vee F(i1,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:
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. OptimizationsHere are some tips to optimize this DP solution:
Time Complexity:$O(N \sum a_i)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Jun '16, 15:16

A TRUE EDITORIAL AND EFFICIENT TOO (WITHOUT USING DP) :https://www.codechef.com/viewsolution/10572704 (refer to this link for code with detailed explanantion) answered 22 Jun '16, 08:03

The logic I applied for calculating minimum s is as follows: Define an array dp[SUM]. SUM=sum of all elements in array. dp[0]=1; for all other index: dp[i]=0; Now for all i=0 to n for all j=SUMarr[i] to 0 if(dp[j]) dp[j+arr[i]] This would give us '1' at all the positions i in array dp for which there exist a subset with sum i then we can find the minimum s by calculating minimum of SUM2*i for all i in dp where dp[i]=1. But this approach is giving WA. CODE: https://www.codechef.com/viewsolution/10559422 Can anyone explain the error or atleast provide me with couple of test cases for which this fails. Thank you. answered 21 Jun '16, 20:43

I felt the time limit was very strict. My recursive dp solution with same complexity failed. :( answered 21 Jun '16, 22:26

java solution used bottom up and bfs approach giving TLE : https://www.codechef.com/viewsolution/10577125 answered 22 Jun '16, 21:59

CAN SOMEONE PLS LOOK INTO my soln and tell what edge case its missing ..? https://www.codechef.com/viewsolution/10751467 @author pls help bfs & bottomup dp used answered 08 Jul '16, 10:29
