11002  Towards Zero
Moderator: Board moderators

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 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=23
set(1,1) = {3,1} > 3=2+1, 1=21
.
.
.
set((i,j)
for the sample input the answer is in the set(6,0).
I hope you understand my explanation
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=23
set(1,1) = {3,1} > 3=2+1, 1=21
.
.
.
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"

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
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.
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.
I have TLE
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][knum] = 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][knum] = 1;
}
memset(m[(i+1)%2],0,sizeof(m)/2);
}
for(j=0;j<MAX;j++)
if (m[0][MAX+j]  m[0][MAXj]) break;
printf("%d\n",j);
}
}
Can smbd help me?
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][knum] = 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][knum] = 1;
}
memset(m[(i+1)%2],0,sizeof(m)/2);
}
for(j=0;j<MAX;j++)
if (m[0][MAX+j]  m[0][MAXj]) 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)
Re: Wrong Answer
My AC's output for your input istan_Yui wrote:I tried to solve with DP solution, but got WrongAnswer...
Here is my input/output. Is my output correct?
Output :Thank you.Sorry, I found my stupid mistake after this post ....
Code: Select all
0
4
0
5
12
50

 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?
Have you read all other threads on this problem? (see: http://onlinejudge.uva.es/board/viewtopic.php?t=10128 and http://onlinejudge.uva.es/board/viewtopic.php?t=10164)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?
Btw, if there is a thread on a particular problem, please, use that thread to post your question instead of creating a new one.

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
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).
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:
due to the problem constraints you can easily use boolean array , instead of set , and it works fasterDarko 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).
In being unlucky I have the record.

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

 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?
thnx!!
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<i1;j++)
scanf("%d", &tab[n+(ni)][j]);
usd[0][0][tab[0][0]+P]=true;
for(i=0;i<n1;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][ktab[i+1][j]]=true;
usd[i+1][j+1][k+tab[i+1][j+1]]=true;
usd[i+1][j+1][ktab[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][ktab[i+1][j]]=true;
}
else{
usd[i+1][j][k+tab[i+1][j]]=true;
usd[i+1][j][ktab[i+1][j]]=true;
usd[i+1][j1][k+tab[i+1][j1]]=true;
usd[i+1][j1][ktab[i+1][j1]]=true;
}
for(k=0;k<P;k++)
if(usd[i][0][P+k]==true  usd[i][0][Pk]==true){
printf("%d\n", k);
break;
}
}
return 0;
}
 arsalan_mousavian
 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact: