## 11002 - Towards Zero

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 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

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
thnx TIMO

i got it. tomorrow i will solve it.

bye

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 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

To asif_rahman0:
You cave wrong answer on test

3
40
50 50
40 40 40
0 50
41

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

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?

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

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)

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
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
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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

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
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
i think you miss the results range bacause it is belongs to the interval [-3000,3000] but you assume it between -500 and 500
In being unlucky I have the record.