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

Post Reply
joemmanuel
New poster
Posts: 4
Joined: Tue Aug 01, 2006 9:01 pm

Post by joemmanuel »

:( Well, i've thought about that and modified, including the range [-3000,3000] on my bool array, but still WA :( I don't know what could it be... may be a tricky case that im not testing...
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

joemmanuel wrote::( Well, i've thought about that and modified, including the range [-3000,3000] on my bool array, but still WA :( I don't know what could it be... may be a tricky case that im not testing...
All cases I've tried your code on were solved correctly. Possibly the problem might be in the really big array
bool usd[70][70][6000];
Top
Igloo
New poster
Posts: 2
Joined: Mon Aug 14, 2006 4:39 pm

Post by Igloo »

joemmanuel wrote:Hi.

I've tried to use some kind of memoizaton, using a bool array for each square in the board ( usd ) to know all sums that can be reached to that square.

I've tried all test cases but still WA... can u help me?
.......
Trying to debug my program, I encountered a case where your program gives a faulty output:

11 -30 -42 10 -18 -42 -30 -42 34 18 -30 -42 42 42 42 22 -26 14 -26 -46 34 -38 22 -6 38 -38 34 46 -10 14 26 46 22 -50 38 -18 10 42 22 30 -18 -46 10 -46 10 30 46 22 -14 -50 -10 -42 -30 -18 -2 18 10 38 -46 -46 -22 -2 -38 -14 -22 10 2 -26 14 -42 38 -6 22 14 -18 26 -14 -38 -26 -26 18 6 -38 26 38 -14 -6 42 -50 -42 18 42 46 -18 6 14 18 -18 46 26 -14 30 38 30 38 22 22 -18 -50 -14 -22 22 26 -26 -18 22 46 30 30 -18 18 42

The result should be 2, but your program gives 0. This (probably) has to do with the fact that you do not use range-checking in your assignments, it works fine for n=1,2,3,4,5,6,7,8,9,10 but not for n = 11.

My program still does not work correctly, keep getting WA

Code: Select all

...........
I am aware that this piece of code is very large, but it is my first part of code that I've written for here.
Last edited by Igloo on Tue Aug 15, 2006 8:59 pm, edited 1 time in total.
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Igloo wrote:My program still does not work correctly, keep getting WA
I am aware that this piece of code is very large, but it is my first part of code that I've written for here.
Try this:

Code: Select all

27
49
49 49
49 50 50
50 49 49 49
49 49 49 50 49
50 49 49 49 49 49
49 50 50 49 49 50 49
49 49 49 50 50 49 50 49
50 49 49 49 50 49 49 50 49
49 49 49 50 49 49 50 50 50 49
50 50 50 50 49 49 50 50 50 49 49
50 50 50 49 50 49 49 49 50 49 49 50
49 50 50 49 49 49 49 49 49 50 49 50 50
49 50 49 50 50 50 49 49 49 49 49 49 50 49
50 50 49 49 49 49 50 49 49 49 49 50 49 49 50
50 50 50 49 49 49 50 50 49 49 50 50 49 50 49 49
49 50 49 49 50 49 50 49 50 50 49 49 50 49 50 50 49
49 50 49 49 50 50 49 50 49 50 50 50 50 50 50 50 50 50
49 49 49 49 50 49 50 50 50 50 49 49 50 49 49 50 49 50 49
49 49 49 49 50 50 50 49 49 49 50 50 50 50 49 50 49 49 49 50
50 49 50 49 50 50 49 50 50 50 50 49 50 49 49 49 50 50 49 49 49
50 50 50 50 50 49 50 50 50 50 50 50 49 50 49 49 50 50 50 49 50 50
50 50 50 50 49 50 50 49 50 49 49 49 50 50 49 50 50 50 49 49 49 49 50
50 49 49 49 49 49 50 50 50 49 50 49 50 49 50 50 50 50 50 50 50 50 50 49
49 50 49 49 50 49 50 49 50 50 50 50 50 49 49 49 50 50 49 49 50 50 50 49 49
50 50 50 49 50 50 49 49 50 49 50 49 50 49 50 49 50 49 50 50 49 50 49 49 50 49
50 49 49 49 49 50 50 49 50 49 50 50 49 50 50 49 50 49 49 49 49 50 49 50 49 49 49
50 49 50 50 49 50 50 49 50 49 50 50 50 49 50 49 49 49 50 49 50 50 49 50 50 50
50 49 49 50 49 50 49 50 49 49 49 49 49 49 49 50 50 49 50 49 49 49 49 49 49
50 50 50 49 50 49 50 50 49 50 49 50 50 50 49 50 49 49 50 49 49 49 50 49
49 49 50 49 49 50 49 49 49 50 49 50 49 49 50 49 50 50 49 49 49 49 50
49 49 49 49 49 49 49 50 49 49 49 49 49 50 50 49 50 49 50 50 49 50
49 50 49 50 50 49 50 50 50 49 50 50 49 50 50 49 49 49 49 49 49
50 50 50 50 50 49 49 49 49 50 49 50 50 50 49 50 49 50 49 49
49 50 50 49 50 50 49 50 49 50 50 50 49 50 49 50 50 50 50
50 49 50 50 49 49 50 50 50 50 49 50 50 50 49 50 49 49
49 50 49 50 50 50 50 49 50 50 50 49 49 49 50 49 50
50 49 50 49 50 49 49 50 50 49 50 50 49 50 50 49
50 49 50 49 50 50 49 49 49 49 50 49 50 50 49
49 50 50 50 50 50 50 49 49 50 50 50 49 50
49 49 49 49 50 50 49 49 50 49 49 50 50
49 50 49 49 50 49 50 49 50 49 49 50
50 50 49 49 50 50 50 50 49 50 49
50 50 49 49 49 49 50 50 50 49
49 50 49 49 50 49 50 50 49
49 49 49 49 50 50 49 49
50 49 50 50 50 50 49
50 50 49 49 49 50
50 49 50 50 49
49 50 50 50
49 50 49
49 49
50
22
49
50 49
49 49 49
50 50 49 49
49 49 49 50 49
50 50 50 49 49 50
49 50 49 49 50 49 49
50 50 50 50 49 49 50 50
49 49 49 49 49 50 49 49 49
49 49 50 50 49 50 49 49 50 50
49 49 50 49 50 50 49 49 50 49 50
49 49 50 50 49 50 49 49 50 49 50 50
50 49 49 50 50 49 49 49 50 49 50 50 50
49 50 50 49 50 49 49 50 50 50 50 49 50 49
50 50 50 50 50 50 50 49 49 50 49 49 49 49 49
49 50 49 50 49 49 50 49 50 49 50 49 49 50 49 49
49 50 50 50 49 49 49 49 50 49 49 50 49 49 50 49 50
49 49 50 49 50 50 50 50 49 49 50 50 49 50 49 50 49 50
49 50 49 49 49 49 50 50 49 50 50 50 50 50 50 49 50 49 49
50 50 49 50 50 49 50 49 49 49 50 50 49 49 50 50 49 50 49 50
49 50 49 50 49 50 49 50 50 49 50 49 50 50 50 49 50 49 50 50 49
49 50 50 49 49 49 49 49 49 50 49 50 49 50 49 50 50 50 49 50 49 49
49 50 50 50 50 50 49 49 49 49 50 50 49 49 50 49 49 50 50 49 49
50 50 49 50 49 50 50 50 50 49 50 50 50 49 49 50 49 49 50 49
49 49 49 49 50 49 49 49 49 49 49 50 50 50 49 50 49 49 49
49 49 50 50 50 49 50 49 49 50 50 50 50 50 50 50 49 49
50 49 49 50 50 50 49 49 49 50 49 49 50 49 49 50 50
50 50 49 49 50 49 50 49 50 50 49 50 50 49 49 49
49 49 50 50 49 50 50 49 50 50 50 49 50 49 50
50 50 49 50 50 49 49 50 50 50 50 49 50 50
50 50 50 50 49 50 50 50 49 50 49 49 50
49 50 50 49 49 50 49 50 49 49 49 50
50 50 50 49 49 49 50 50 49 49 50
50 50 49 50 50 50 50 49 50 50
50 50 50 49 50 50 49 50 50
49 50 49 50 50 50 50 49
49 50 49 49 49 50 49
49 49 50 50 49 50
49 49 49 49 49
49 50 50 50
49 50 49
49 49
50
0
My AC's output:

Code: Select all

23
28
Your output:

Code: Select all

23
0
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Martin Macko wrote:
joemmanuel wrote::( Well, i've thought about that and modified, including the range [-3000,3000] on my bool array, but still WA :( I don't know what could it be... may be a tricky case that im not testing...
All cases I've tried your code on were solved correctly. Possibly the problem might be in the really big array
Joemmanuel, your code isn't working on the input I've just found for Igloo, too.
Top
Igloo
New poster
Posts: 2
Joined: Mon Aug 14, 2006 4:39 pm

Post by Igloo »

Martin Macko wrote: Try this:

Code: Select all

.........................
My AC's output:

Code: Select all

23
28
Your output:

Code: Select all

23
0
Thanks a bunch, it seems that I did not set the complete array to zero..
Top
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Igloo wrote:Thanks a bunch, it seems that I did not set the complete array to zero..
After getting AC, please, remove the code from your previous post.
Top
basted
New poster
Posts: 1
Joined: Sun Feb 03, 2008 8:25 pm

Post by basted »

I use DP but I get WA. I tried the testdata in this topic and get WA but I don't understand why. Could you please help?

Code: Select all

r[(2*n)-2][0]=a[(2*n)-2][0];
for(int i=(2*n)-3,k=1;i>=0;i--){
if(i>=n-1)k++;
else k--;
for(int j=0;j<k;j++){
if(j==0)r[i][j]=closest(r[i+1][j]+a[i][j],r[i+1][j]-a[i][j]);
else if(j==k-1)r[i][j]=closest(r[i+1][j-1]+a[i][j],r[i+1][j-1]-a[i][j]);
else r[i][j]=closest(closest(r[i+1][j]+a[i][j],r[i+1][j-1]+a[i][j]),closest(r[i+1][j]-a[i][j],r[i+1][j-1]-a[i][j]))-a[i][j];
}
}
and the closest function

Code: Select all

inline int closest(int a,int b){
        if(abs(a) < abs(b))return a;
        else return b;
}
Top
Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

Re: 11002 - Towards Zero

Post by Zwergesel »

Here's a test case that my accepted program couldn't solve (it worked after I changed an array size), but a correct implementation should solve.
Maybe this one could be added to the test data?

Code: Select all

30
50
50 50
50 50 50
50 50 50 50
50 50 50 50 50
50 50 50 50 50 50
50 50 50 50 50 50 50
50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49 49
49 49 49 49 49 49 49 49
49 49 49 49 49 49 49
49 49 49 49 49 49
49 49 49 49 49
49 49 49 49
49 49 49
49 49
29
0
Correct output should be:

Code: Select all

0
Top
jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 11002 - Towards Zero

Post by jddantes »

Getting TLE a couple of times now.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

#define INF 1<<26
#define UNVISITED -1

int offset;

int input[59][30];
int max_val;

int arr [59][30][3001];
// bool visited[59][30][3001];
int N;

int f(int i, int j, int sum){

	// printf("%d %d %d %d\n", i,j,sum,input[i][j]);

	if(i == 2*N-1-1){
		return abs(sum);
	}

	// if(visited[i][j][sum+offset]){
	// 	return arr[i][j][sum+offset];
	// }

	if(arr[i][j][sum+offset] != UNVISITED){
		return arr[i][j][sum+offset];
	}

	int ret = INF;

	if(i<N-1){

		// lower pyramid, go up

		for(int j = 0; j<i+1; j++){
			// left
			int lu_plus = f(i+1, j, sum+input[i+1][j]);
			ret = min(ret, lu_plus);
			int lu_minus = f(i+1, j, sum-input[i+1][j]);
			ret = min(ret, lu_minus);

			// right
			int ru_plus = f(i+1, j+1, sum+input[i+1][j+1]);
			ret = min(ret, ru_plus);
			int ru_minus = f(i+1, j+1, sum-input[i+1][j+1]);
			ret = min(ret, ru_minus);
		}
	} else {
		int numCols = N - (i-(N-1));
		// printf("I is %d, numCols is %d\n", i, numCols);
		for(int j = 0; j<numCols; j++){
			// left
			if(j){
				int lu_plus = f(i+1, j-1, sum+input[i+1][j-1]);
				ret = min(ret, lu_plus);
				int lu_minus = f(i+1, j-1, sum-input[i+1][j-1]);
				ret = min(ret, lu_minus);
			}

			// right
			if(j < numCols-1){
				int ru_plus = f(i+1, j, sum+input[i+1][j]);
				ret = min(ret, ru_plus);
				int ru_minus = f(i+1, j, sum-input[i+1][j]);
				ret = min(ret, ru_minus);
			}
		}

	} 

	// visited[i][j][sum+offset] = true;
	return arr[i][j][sum+offset] = ret;
}

int main(){
	while(scanf("%d", &N)!=EOF){
		if(!N){
			return 0;
		}
		max_val = (2*N-1)*50;
		offset = max_val;
		for(int i = 1; i<N; i++){
			for(int j=0; j<i; j++){
				scanf("%d", &input[2*N-1-i][j]);
				for(int val = -max_val; val<=max_val; val++){
					// arr[i][j][val+offset]'
					// visited[2*N-1-i][j][val+offset] = false;
					arr[2*N-1-i][j][val+offset] = UNVISITED;
				}
			}
		}
		for(int j = 0; j<N; j++){
			scanf("%d", &input[N-1][j]);
			for(int val = -max_val; val<=max_val; val++){
				// visited[N-1][j][val+offset] = false;
				arr[N-1][j][val+offset] = UNVISITED;
			}
		}
		for(int i = N-1; i>=1; i--){
			for(int j = 0; j<i; j++){
				scanf("%d", &input[i-1][j]);
				for(int val = -max_val; val<=max_val; val++){
					// visited[i-1][j][val+offset] = false;
					arr[i-1][j][val+offset] = UNVISITED;
				}
			}
		}

		int ret = f(0,0, input[0][0]);
		// printf("%d %d %d %d\n", input[0][0], input[1][0], input[1][1], input[2][0]);
		printf("%d\n", ret);

	}

	return 0;
}
Top
Post Reply

Return to “Volume 110 (11000-11099)”