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

joemmanuel
New poster
Posts: 4
Joined: Tue Aug 01, 2006 9:01 pm
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...

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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];

Igloo
New poster
Posts: 2
Joined: Mon Aug 14, 2006 4:39 pm
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.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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``````

Code: Select all

``````23
0``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

Igloo
New poster
Posts: 2
Joined: Mon Aug 14, 2006 4:39 pm
Martin Macko wrote: Try this:

Code: Select all

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

Code: Select all

``````23
28``````

Code: Select all

``````23
0``````
Thanks a bunch, it seems that I did not set the complete array to zero..

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.

basted
New poster
Posts: 1
Joined: Sun Feb 03, 2008 8:25 pm
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;
}
``````

Zwergesel
New poster
Posts: 11
Joined: Tue Jul 27, 2010 7:29 pm

### Re: 11002 - Towards Zero

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

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

### Re: 11002 - Towards Zero

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;
}
``````