You are not logged in. Please login at www.codechef.com to post your questions!

×

RWALK - Editorial

0
1

PROBLEM LINK:

Contest
Practice

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: $$F(i,s) = \min(F(i-1,|s-b_i|), F(i-1,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 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)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester 1
tester 2

This question is marked "community wiki".

asked 19 Jun '16, 15:16

kevinsogo's gravatar image

7★kevinsogo
1.7k583142
accept rate: 11%

edited 22 Jun '16, 10:49

admin's gravatar image

0★admin ♦♦
19.6k349497539


Hey, I thought of this during the contest, but rejected the idea assuming it would TLE.

How does this pass with 50 test cases ?

link

answered 21 Jun '16, 14:57

s4shyam95's gravatar image

5★s4shyam95
2086
accept rate: 20%

2

Because Codechef :D They're so awesome ...... at screwing up! I did the same as you, and rejected this idea.

(22 Jun '16, 16:44) shinjiikari5★

It passes 50 test cases with the limit 500 because the big-O constant is very small (~ 1/4 or even 1/8 with more optimizations.)

(02 Jul '16, 07:26) kevinsogo7★

A TRUE EDITORIAL AND EFFICIENT TOO (WITHOUT USING DP) :https://www.codechef.com/viewsolution/10572704 (refer to this link for code with detailed explanantion)

link

answered 22 Jun '16, 08:03

akshatagrawal's gravatar image

3★akshatagrawal
292
accept rate: 0%

edited 02 Jul '16, 17:25

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=SUM-arr[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 SUM-2*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.

link

answered 21 Jun '16, 20:43

little_finger's gravatar image

5★little_finger
622
accept rate: 0%

I felt the time limit was very strict. My recursive dp solution with same complexity failed. :(

link

answered 21 Jun '16, 22:26

mishraiiit's gravatar image

6★mishraiiit
1018
accept rate: 0%

java solution used bottom up and bfs approach giving TLE : https://www.codechef.com/viewsolution/10577125

link

answered 22 Jun '16, 21:59

sanket407's gravatar image

4★sanket407
4849
accept rate: 10%

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

link

answered 08 Jul '16, 10:29

ankesh18's gravatar image

6★ankesh18
627111
accept rate: 7%

edited 08 Jul '16, 10:37

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,127
×3,615
×1,965
×105
×7

question asked: 19 Jun '16, 15:16

question was seen: 3,587 times

last updated: 08 Jul '16, 10:37