11002 - Towards Zero

[asif_rahman0]

Sorry i dont got ur +-15 & +-1 for values 8(eight)

what is this?? plz explain me

[Timo]

Hi asif_rahman0, I want try to help you .

I will give you example from the sample input.

.....[0][1][2][3]
[0] 2
[1] 3 1
[2] -3 5 7
[3] 6 10 -2 20
[4] -7 -5 -8
[5] 10 8
[6] 7

let set(i,j) be the number that we can reach if we in
the row i and column j.

set(0,0) = {2}
set(1,0) = {5,1} -> 5=|2+3|, 1=|2-3|
set(1,1) = {3,1} -> 3=|2+1|, 1=|2-1|
.
.
.
set((i,j)

for the sample input the answer is in the set(6,0).

I hope you understand my explanation

[Darko]

I tried to implement it that way, but got TLE (in Java). Do you ignore any sums on your way down or you keep them all? For the sample input my set has 47 elements for the last square (min is 0).

Darko

[asif_rahman0]

thnx TIMO


i got it. tomorrow i will solve it.

bye

[Darko]

Ok, I got it accepted after writing some crappy Set, which worked because of the constraints. So I need a Set.. and PQ.. and Maps... and a bunch of other stuff.

I am torn now - should I write my own Java Collections Framework, or should I learn C++/STL? Which approach would take less time? I don't know C++ at all. I do know some basic C (not sure if that would help). I am very comfortable with Java.

[medv]

To asif_rahman0:
You cave wrong answer on test

3
40
50 50
40 40 40
0 50
41


Your program gives 30, but answer is 9.

I have TLE. Here is my program:

#include <stdio.h>
#include <memory.h>
#define MAX 1500

int m[2][2*MAX+3];
int i,j,k,n,num;

void main(void)
{
while(scanf("%d",&n),n)
{
memset(m,0,sizeof(m));
scanf("%d",&num); m[0][num+MAX] = 1;
for(i=1;i<n;i++)
{
for(j=0;j<=i;j++)
{
scanf("%d",&num);
for(k=0;k<2*MAX+3;k++)
if (m[(i+1)%2][k])
m[i%2][k+num] = m[i%2][k-num] = 1;
}
memset(m[(i+1)%2],0,sizeof(m)/2);
}
for(;i>1;i--)
{
for(j=1;j<i;j++)
{
scanf("%d",&num);
for(k=0;k<2*MAX+3;k++)
if (m[(i+1)%2][k])
m[i%2][k+num] = m[i%2][k-num] = 1;
}
memset(m[(i+1)%2],0,sizeof(m)/2);
}
for(j=0;j<MAX;j++)
if (m[0][MAX+j] || m[0][MAX-j]) break;
printf("%d\n",j);
}
}

Can smbd help me?

[Martin Macko]

I tried to solve with DP solution, but got WrongAnswer...
Here is my input/output. Is my output correct?
Output :

Sorry, I found my stupid mistake after this post ....

Thank you.

My AC's output for your input is

Code: Select all

0
4
0
5
12
50

[StatujaLeha]

I get TLE on this problem. I think it can be because I use for memoization std::map<>. Please tell about how do you do memoization for this problem?

[Martin Macko]

I get TLE on this problem. I think it can be because I use for memoization std::map<>. Please tell about how do you do memoization for this problem?

Have you read all other threads on this problem? (see: http://online-judge.uva.es/board/viewtopic.php?t=10128 and http://online-judge.uva.es/board/viewtopic.php?t=10164)

Btw, if there is a thread on a particular problem, please, use that thread to post your question instead of creating a new one.

[StatujaLeha]

Have you read all other threads on this problem?

Yes, of course. I have only understood that there are various kinds of memoization's implementation. I want to know if there is a faster implementation than with using std::map<> as cache.

[Darko]

Well, why not ask the question in that thread then? This is how we end up with 10 threads on each problem.

In my Java solution I used a set (as suggested by misof in yet another thread on this problem) to determine different sums in each row, so I could build the table (which is not needed, but it was easier for me). I didn't use memoization (unless you count adding an element to a set that already contains it as memoization).

I think that STL set would do just fine (I wrote my own and it's not that good, but it worked).

[arsalan_mousavian]

Well, why not ask the question in that thread then? This is how we end up with 10 threads on each problem.

In my Java solution I used a set (as suggested by misof in yet another thread on this problem) to determine different sums in each row, so I could build the table (which is not needed, but it was easier for me). I didn't use memoization (unless you count adding an element to a set that already contains it as memoization).

I think that STL set would do just fine (I wrote my own and it's not that good, but it worked).

due to the problem constraints you can easily use boolean array , instead of set , and it works faster

[StatujaLeha]

Code: Select all

In my Java solution I used a set (as suggested by misof in yet another thread on this problem) to determine different sums in each row, so I could build the table (which is not needed, but it was easier for me). I didn't use memoization (unless you count adding an element to a set that already contains it as memoization).

I think that STL set would do just fine (I wrote my own and it's not that good, but it worked).

Thanks a lot. My initial solution is diffirent from yours. I tried to remember each sum that can be got in some cell and closest to this sum value that can be got when we go from this cell to top-most cell.
When I implemented misof's idea with using std::set<>, it gave me TLE too. When I used bool's arrays instead of std::set<> as adviced arsalan_mousavian I got Accepted.

[joemmanuel]

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?

Code: Select all

#include <stdio.h>
#include <string.h>

int NO=-10000;
const int P=500;
const int N=1000;
bool usd[70][70][1000]={false};
int tab[70][70];
int main(){

	int n;
    while(1){


        memset(usd,false,sizeof(usd));
        
        scanf("%d", &n);
        if(n==0)
        	return 0;

        int i,j,k;
    	for(i=0;i<70;i++)
        	for(j=0;j<70;j++)
                tab[i][j]=NO;

        
        for(i=0;i<n;i++)
        	for(j=0;j<=i;j++)
            	scanf("%d", &tab[i][j]);
        for(i=n;i>0;i--)
        	for(j=0;j<i-1;j++)
            	scanf("%d", &tab[n+(n-i)][j]);


        usd[0][0][tab[0][0]+P]=true;
        
        for(i=0;i<n-1;i++)
        	for(j=0;j<=i;j++)
            	if(tab[i][j]!=NO)
            	for(k=0;k<N;k++)
                	if(usd[i][j][k]==true){
                    	usd[i+1][j][k+tab[i+1][j]]=true;
                        usd[i+1][j][k-tab[i+1][j]]=true;
                        
                    	usd[i+1][j+1][k+tab[i+1][j+1]]=true;
                        usd[i+1][j+1][k-tab[i+1][j+1]]=true;
                    }
                    

        for(;i<(2*n)-2;i++)
        	for(j=0;j<=i;j++)
            	if(tab[i][j]!=NO)
                for(k=0;k<N;k++)
					if(usd[i][j][k]==true)
    	            	if(j==0){
        	            	usd[i+1][j][k+tab[i+1][j]]=true;
            	            usd[i+1][j][k-tab[i+1][j]]=true;
                	    }
                    	else{
                        	usd[i+1][j][k+tab[i+1][j]]=true;
	                        usd[i+1][j][k-tab[i+1][j]]=true;
    	                    usd[i+1][j-1][k+tab[i+1][j-1]]=true;
        	                usd[i+1][j-1][k-tab[i+1][j-1]]=true;
            	        }


		for(k=0;k<P;k++)
        	if(usd[i][0][P+k]==true || usd[i][0][P-k]==true){
	            printf("%d\n", k);
    	        break;
        	}


    }



   return 0;
}

thnx!!

[arsalan_mousavian]

i think you miss the results range bacause it is belongs to the interval [-3000,3000] but you assume it between -500 and 500