OJ Board

The Online Judge board
https://onlinejudge.org/board/

11002 - Towards Zero

https://onlinejudge.org/board/viewtopic.php?t=10164

Page 3 of 3

Posted: Wed Aug 02, 2006 5:57 pm
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...

Posted: Sat Aug 05, 2006 2:23 am
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];

Posted: Mon Aug 14, 2006 5:02 pm
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.

Posted: Mon Aug 14, 2006 8:35 pm
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

Posted: Mon Aug 14, 2006 8:41 pm
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.

Posted: Mon Aug 14, 2006 8:50 pm
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..

Posted: Tue Aug 15, 2006 10:30 am
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.

Posted: Sun Feb 03, 2008 8:29 pm
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;
}

Re: 11002 - Towards Zero

Posted: Tue Jul 27, 2010 7:43 pm
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

Re: 11002 - Towards Zero

Posted: Thu Jul 02, 2015 7:59 am
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;
}
All times are UTC+02:00
Page 3 of 3

Powered by phpBB® Forum Software © phpBB Limited