11002 - Towards Zero

[qndel]

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.

[sclo]

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]

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.

[asif_rahman0]

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]

Depends on how you memo/backtrack.

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

[asif_rahman0]

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]

could somebody give me so more test cases
plz help me
thanks a lot

[Larry]

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]

sorry, but that algorithm not mine
and please give me some more test cases if you could
thanks a lot

[lonelyone]

sorry, but I solved it already
thanks anyone...^^

[asif_rahman0]

thnx larry.
i got it & now i changed my code. but still getting WA.

so i need some input/output

[tan_Yui]

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]

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]

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]

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.