## 11002 - Towards Zero

Moderator: Board moderators

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

### 11002 - Towards Zero

I solved this problem in 02.924 s using DP. I used 25040 KB of memory . I would be very pleased if anybody would tell me better method or some optimalization of DP method.
NOthing special

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I think you can use a bound to figure out which values to dp on and which to simply return 0. That took off about 2 secs off my solution. These kind of optimization that is often used in backtracking problems might work here.

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole
If I understood, you found bounds for each cell like min(x,y) and max(x,y) and you use in DP numbers only between those 2 values.
NOthing special

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 11002 - Towards Zero

i m getting WA in dis problem!!! but dont get why.
MY logic:
when get -8 it will be 8 then check again for closer to ZERO(0).
again if get -1 then 1. again get ZERO then it will 0. so am i right???

Here give some I/O which i tested. Is It correct? if yes plz give more.

10
20
3 -1
15 5 -9
-3 5 7 6
6 7 5 -3 -1
1 2 3 4 5 -6
5 -7 -1 -2 3 7 -11
-4 -6 -1 -2 -3 8 9 10
-4 -6 -1 -2 -3 8 9 10 4
6 10 -2 20 -7 -5 -8 -10 8 -7
-4 -6 -1 -2 -3 1 9 10 4
-4 -6 -1 -2 -3 8 9 10
5 -7 -1 -2 3 7 -11
1 2 3 4 5 -6
6 7 5 -3 -1
-3 5 7 6
15 5 -9
3 -1
20
0

4
1
3 -3
3 3 -10
-9 -9 -9 10
-9 3 -10
2 3
1
0

4
1
4 -4
3 3 -10
-9 -9 -9 10
-9 3 -10
2 3
1
0

1
1
1

2
1
3 1
1
1

i use memoization with backtraking.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Depends on how you memo/backtrack.

It is the right method, but depends on how you define your recurrence..

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx larry. but it would be great if u just tell me more...then i can make it more.

here i posted my recursive code segment...

void recur(int in,int sum)
{
int i;
if(in==(2*n)-1){
if(min>abs(sum)){
min=abs(sum);
}
return;
}
if(cache[in][sum]) return;
cache[in][sum]=true;
for(i=0;i<=in;i++){
if(num[in]) recur(in+1,sum+num[in]);
if(num[in]) recur(in+1,sum-num[in]);
}
}

so is it efficient or not?
if not how can ...just give some hint plz

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
could somebody give me so more test cases
plz help me
thanks a lot

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Your memo is wrong. For example, you can't just go from a cell on the left to one all the way to the right in succession..

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
sorry, but that algorithm not mine
and please give me some more test cases if you could
thanks a lot

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
sorry, but I solved it already
thanks anyone...^^

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx larry.
i got it & now i changed my code. but still getting WA.

so i need some input/output

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

I tried to solve with DP solution, but got WrongAnswer...
Here is my input/output. Is my output correct?
4
2
3 1
-3 5 7
6 10 -2 20
-7 -5 -8
10 8
7
2
5
-6 -6
7
3
19
-50 4
26 26 -43
20 -16
5
6
-1
0 0
18 0 -29
26 0 0 1
0 0 0 0 0
0 0 0 0 0 50
0 0 0 0 0
0 0 0 0
0 0 0
0 0
36
3
0
-30 -30
-7 -8 -5
-50 -50
0
1
50
0
Output :
Sorry, I found my stupid mistake after this post ....
Thank you.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
i got WA many times. i try to solve it with DP.
plz help me.

Code: Select all

``````#include <stdio.h>
#include <math.h>
#include <memory.h>
#define MIN(a,b) (a)<(b)?(a):(b)
int num[70][70];
bool visited[70][70];
int main()
{
int m,i,j;
while(true){
memset(num,1<<30,sizeof(num));
memset(visited,false,sizeof(visited));
scanf("%d",&m);
if(!m) break;
int mag=0;
bool flag=true;
for(i=(2*m-1);i>0;i--){
if(mag<m&&flag) mag=mag+1;
else{flag=false;mag--;}
for(j=1;j<=mag;j++){
scanf("%d",&num[i][j]);
visited[i][j]=true;
}
}
//dp
for(i=1;i<(2*m-1);i++){
for(j=1;j<=i;j++){
if(num[i+1][j]&&visited[i+1][j]==true&&num[i][j])
{
num[i+1][j]=MIN(abs(num[i][j]+num[i+1][j]),abs(num[i][j]-num[i+1][j]));
visited[i+1][j]=false;
}
if(visited[i+1][j+1]==true&&num[i][j+1]&&num[i][j]&&num[i+1][j+1])
{
int temp1=MIN(abs(num[i][j]+num[i+1][j+1]),abs(num[i][j]-num[i+1][j+1]));
int temp2=MIN(abs(num[i][j+1]+num[i+1][j+1]),abs(num[i][j+1]-num[i+1][j+1]));
if(temp1<temp2)
{
num[i+1][j+1]=temp1;
visited[i+1][j+1]=false;
}
else
{
num[i+1][j+1]=temp2;
visited[i+1][j+1]=false;
}
}
}
}
//
printf("%d\n",num[2*m-1][1]);
}
return 0;
}
``````
help would be appreciated

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 11002 - Towards Zero

i tried so many times to solve this DP problem(11002). but i didn't find any correct reccurence relation to solve it.

if some one explain me some part of DP/recurrence then it would be nice for me to solve it.

(i have a question.)Is recurrence depends on overlapping subproblems??
and
how overlapping comes in 11002 problem?(explain)

plz help.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
I didn't have the time to solve it yet, but the general idea should be: process all squares from bottom to top. For each square compute the set of sums that are possible at the moment when you stand there.

E.g., for the image in the problem statement: for the only square with the number 8 the possible sums are +-15 and +-1.