OJ Board

Posted: **Fri May 12, 2006 1:30 pm**

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

what is this?? plz explain me

Posted: **Fri May 12, 2006 1:50 pm**

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

Posted: **Fri May 12, 2006 9:15 pm**

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

Posted: **Fri May 12, 2006 10:08 pm**

thnx TIMO

i got it. tomorrow i will solve it.

bye

Posted: **Sat May 13, 2006 8:42 am**

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.

Posted: **Sat May 13, 2006 12:03 pm**

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?

Posted: **Sat May 20, 2006 9:52 pm**

tan_Yui wrote: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

Posted: **Fri Jul 28, 2006 7:51 pm**

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?

Posted: **Sat Jul 29, 2006 1:40 am**

StatujaLeha wrote: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.

Posted: **Sat Jul 29, 2006 8:21 am**

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.

Posted: **Sat Jul 29, 2006 9:15 am**

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).

Posted: **Sat Jul 29, 2006 10:32 am**

Darko wrote: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

Posted: **Sat Jul 29, 2006 7:11 pm**

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.

Posted: **Tue Aug 01, 2006 9:16 pm**

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

Posted: **Wed Aug 02, 2006 8:40 am**

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

OJ Board

11002 - Towards Zero

I have TLE

Re: Wrong Answer

11002 How do you do memoization for this problem?

Re: 11002 How do you do memoization for this problem?