11002 - Towards Zero

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11002 - Towards Zero

Post by qndel » Sat Mar 11, 2006 5:58 pm

I solved this problem in 02.924 s using DP. I used 25040 KB of memory :o . 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Mar 12, 2006 2:00 am

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

Post by qndel » Sun Mar 12, 2006 11:07 am

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

Post by asif_rahman0 » Wed Mar 15, 2006 9:33 pm

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:

Post by Larry » Mon Mar 20, 2006 6:45 pm

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

Post by asif_rahman0 » Mon Mar 20, 2006 10:10 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

Post by lonelyone » Thu Mar 23, 2006 11:32 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:

Post by Larry » Fri Mar 24, 2006 1:51 am

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

Post by lonelyone » Fri Mar 24, 2006 6:14 am

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

Post by lonelyone » Sat Mar 25, 2006 6:38 am

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

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

Post by asif_rahman0 » Wed Mar 29, 2006 10:05 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

Wrong Answer

Post by tan_Yui » Tue May 02, 2006 3:05 pm

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

Post by asif_rahman0 » Wed May 10, 2006 9:03 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

Post by asif_rahman0 » Fri May 12, 2006 8:34 am

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

Post by misof » Fri May 12, 2006 8:43 am

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.

Post Reply

Return to “Volume 110 (11000-11099)”