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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Fri May 12, 2006 1:30 pm

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

what is this?? plz explain me

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Fri May 12, 2006 1:50 pm

Hi asif_rahman0, I want try to help you :D .

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 :D
"Life is more beautiful with algorithm"

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Fri May 12, 2006 10:08 pm

thnx TIMO
:)

i got it. tomorrow i will solve it.

bye

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

I have TLE

Post by medv » 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?

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

Re: Wrong Answer

Post by Martin Macko » 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

0
4
0
5
12
50

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

11002 How do you do memoization for this problem?

Post by StatujaLeha » 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?

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

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

Post by Martin Macko » 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.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » 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. :)

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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).

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » 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
In being unlucky I have the record.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » 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.

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

Post by joemmanuel » 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!!

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » 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 :wink:
In being unlucky I have the record.

Post Reply

Return to “Volume 110 (11000-11099)”