11002  Towards Zero
Moderator: Board moderators
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

 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.
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.

 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..
It is the right method, but depends on how you define your recurrence..
Check out http://www.algorithmist.com !

 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,sumnum[in]);
}
}
so is it efficient or not?
if not how can ...just give some hint plz
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,sumnum[in]);
}
}
so is it efficient or not?
if not how can ...just give some hint plz

 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..
Check out http://www.algorithmist.com !

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
Wrong Answer
I tried to solve with DP solution, but got WrongAnswer...
Here is my input/output. Is my output correct?
Here is my input/output. Is my output correct?
Output :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
Thank you.Sorry, I found my stupid mistake after this post ....

 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.
help would be appreciated
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*m1);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*m1);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*m1][1]);
}
return 0;
}

 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.
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.
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.
E.g., for the image in the problem statement: for the only square with the number 8 the possible sums are +15 and +1.