10603  Fill
Moderator: Board moderators
10603  Fill
Hi,
I got WA for this. I use memoization to solve. But WA
anyone got test cases? and what the answer for this?
Input
5
12 23 42 14
12 53 75 23
56 23 34 2
23 55 72 25
124 86 173 84
Output
166 14
728 23
0 0
23 23
1012 77
I got WA for this. I use memoization to solve. But WA
anyone got test cases? and what the answer for this?
Input
5
12 23 42 14
12 53 75 23
56 23 34 2
23 55 72 25
124 86 173 84
Output
166 14
728 23
0 0
23 23
1012 77
http://www.harvestsoft.net
Stephanus
Stephanus
 filigabriel
 New poster
 Posts: 15
 Joined: Thu Oct 16, 2003 7:43 pm
 Location: M
 Contact:
I got ACC using BFS, but I'm still confused why I got WA using DFS + memoization
can u help?
thx
regards,
stephanus
[cpp]
/*
@ Problem : Fill
@ UVa id : 10603
@ Lang. : C++
@ Author : Stephanus
@ Date : 26 May 2004
*/
#include <iostream>
#include <map>
using namespace std;
#define f(a,b,c) (1000000*(a)+1000*(b)+(c))
#define INF 2000000
/* Memoization */
class Memo {
public:
int mindiff;
int poured;
};
map<int,Memo> memo;
map<int,Memo>::iterator p;
class Jug {
public:
int vol;
int maxvol;
};
Jug jug[3];
int wantvol;
// doit return min difference
int doit(int &poured)
{
// base case
if (jug[0].vol == wantvol  jug[1].vol == wantvol  jug[2].vol == wantvol)
{
poured = 0;
return 0;
}
// memo case
int y = f(jug[0].vol,jug[1].vol,jug[2].vol);
p = memo.find(y);
if (p != memo.end())
{
if (p>second.mindiff == 1) {
//cout << "memo1" << endl;
poured = INF;
return INF;
} else {
//cout << "memo2" << endl;
poured = p>second.poured;
return p>second.mindiff;
}
}
// init
Memo t;
t.mindiff = 1;
t.poured = 1;
memo.insert(pair<int,Memo>(y,t));
// operation
int i,j,k;
int mindiff,minpour;
int diff,pour;
int delta;
mindiff = INF;
minpour = 0;
for (k=0; k<3; k++)
if (jug[k].vol < wantvol)
{
diff = wantvoljug[k].vol;
if (diff < mindiff) mindiff = diff;
}
for (i=0; i<3; i++) for (j=0; j<3; j++)
if (i != j && jug.vol != 0 && jug[j].vol != jug[j].maxvol)
{
// pour i to j untill j full
if (jug[j].maxvol  jug[j].vol <= jug.vol)
delta = jug[j].maxvol  jug[j].vol;
else delta = jug.vol;
jug.vol = delta;
jug[j].vol += delta;
diff = doit(pour);
if (diff == mindiff && delta + pour < minpour)
minpour = delta + pour;
if (diff < mindiff)
{
mindiff = diff;
minpour = delta + pour;
}
jug.vol += delta;
jug[j].vol = delta;
}
t.mindiff = mindiff;
t.poured = minpour;
memo.insert(pair<int,Memo>(y,t));
poured = minpour;
return mindiff;
}
int main()
{
int ncase,n;
int mindiff;
int poured;
cin >> ncase;
for (n=0; n<ncase; n++)
{
// input
cin >> jug[0].maxvol >> jug[1].maxvol >> jug[2].maxvol >> wantvol;
// init
memo.clear();
jug[0].vol = 0;
jug[1].vol = 0;
jug[2].vol = jug[2].maxvol;
// process
mindiff = doit(poured);
// output
cout << poured << " " << wantvolmindiff << endl;
}
return 0;
}[/cpp]
can u help?
thx
regards,
stephanus
[cpp]
/*
@ Problem : Fill
@ UVa id : 10603
@ Lang. : C++
@ Author : Stephanus
@ Date : 26 May 2004
*/
#include <iostream>
#include <map>
using namespace std;
#define f(a,b,c) (1000000*(a)+1000*(b)+(c))
#define INF 2000000
/* Memoization */
class Memo {
public:
int mindiff;
int poured;
};
map<int,Memo> memo;
map<int,Memo>::iterator p;
class Jug {
public:
int vol;
int maxvol;
};
Jug jug[3];
int wantvol;
// doit return min difference
int doit(int &poured)
{
// base case
if (jug[0].vol == wantvol  jug[1].vol == wantvol  jug[2].vol == wantvol)
{
poured = 0;
return 0;
}
// memo case
int y = f(jug[0].vol,jug[1].vol,jug[2].vol);
p = memo.find(y);
if (p != memo.end())
{
if (p>second.mindiff == 1) {
//cout << "memo1" << endl;
poured = INF;
return INF;
} else {
//cout << "memo2" << endl;
poured = p>second.poured;
return p>second.mindiff;
}
}
// init
Memo t;
t.mindiff = 1;
t.poured = 1;
memo.insert(pair<int,Memo>(y,t));
// operation
int i,j,k;
int mindiff,minpour;
int diff,pour;
int delta;
mindiff = INF;
minpour = 0;
for (k=0; k<3; k++)
if (jug[k].vol < wantvol)
{
diff = wantvoljug[k].vol;
if (diff < mindiff) mindiff = diff;
}
for (i=0; i<3; i++) for (j=0; j<3; j++)
if (i != j && jug.vol != 0 && jug[j].vol != jug[j].maxvol)
{
// pour i to j untill j full
if (jug[j].maxvol  jug[j].vol <= jug.vol)
delta = jug[j].maxvol  jug[j].vol;
else delta = jug.vol;
jug.vol = delta;
jug[j].vol += delta;
diff = doit(pour);
if (diff == mindiff && delta + pour < minpour)
minpour = delta + pour;
if (diff < mindiff)
{
mindiff = diff;
minpour = delta + pour;
}
jug.vol += delta;
jug[j].vol = delta;
}
t.mindiff = mindiff;
t.poured = minpour;
memo.insert(pair<int,Memo>(y,t));
poured = minpour;
return mindiff;
}
int main()
{
int ncase,n;
int mindiff;
int poured;
cin >> ncase;
for (n=0; n<ncase; n++)
{
// input
cin >> jug[0].maxvol >> jug[1].maxvol >> jug[2].maxvol >> wantvol;
// init
memo.clear();
jug[0].vol = 0;
jug[1].vol = 0;
jug[2].vol = jug[2].maxvol;
// process
mindiff = doit(poured);
// output
cout << poured << " " << wantvolmindiff << endl;
}
return 0;
}[/cpp]
http://www.harvestsoft.net
Stephanus
Stephanus

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10603  Fill
My approach to solve this using BFS was to keep an int array of size 201 that is the least total amount of poured water needed to produce that amount of liters in at least one of the jugs. Initialize this to all INT_MAX.
I also keep a bool array of size 201*201*201 that tracks if a state has been visited, initialized to all false.
My queue contains the amount currently in each jug and the amount of water poured so far.
Then for every reachable state I try the 6 possible pourings.
Then find the maximum d' less than or equal to d that is reachable.
This algorithm got AC for me in 0.036 seconds.
I also keep a bool array of size 201*201*201 that tracks if a state has been visited, initialized to all false.
My queue contains the amount currently in each jug and the amount of water poured so far.
Then for every reachable state I try the 6 possible pourings.
Then find the maximum d' less than or equal to d that is reachable.
This algorithm got AC for me in 0.036 seconds.
Check input and AC output for thousands of problems on uDebug!
Re: 10603  Fill
I do not understand this part "It is allowed to pour water from one jug into another until either the first one is empty or the second one is full."
can you explain a test case?
EDIT:
Explained by Moustafa Mahmoud
you can pour some water from one jug (call it 'a') to another (call it 'b'), you MUST keeping pouring until either jug 'a' becomes empty or jug 'b' becomes full.
So, the initial state you're in is that the first two jugs are empty and the 3rd one is full. From that state you can move to other states according to the above condition.
So, think of the states as nodes, and from one state you have 6 possible moves:
 pour from jug 1 to jug 2
 from jug 1 to 3
 from jug 2 to 1
 from jug 2 to 3
 from jug 3 to 1
 from jug 3 to 2
each move will get you to a new state. So each state (node) will have at max 6 neighbours.
the above information is sufficient to define an implicit graph.
can you explain a test case?
EDIT:
Explained by Moustafa Mahmoud
you can pour some water from one jug (call it 'a') to another (call it 'b'), you MUST keeping pouring until either jug 'a' becomes empty or jug 'b' becomes full.
So, the initial state you're in is that the first two jugs are empty and the 3rd one is full. From that state you can move to other states according to the above condition.
So, think of the states as nodes, and from one state you have 6 possible moves:
 pour from jug 1 to jug 2
 from jug 1 to 3
 from jug 2 to 1
 from jug 2 to 3
 from jug 3 to 1
 from jug 3 to 2
each move will get you to a new state. So each state (node) will have at max 6 neighbours.
the above information is sufficient to define an implicit graph.
Re: 10603  Fill
I am using BFS to search all possible states, but TLE. Something wrong with my implementation or there is a way to improve my BFS.
Code: Select all
#include <stdio.h>
#include <string.h>
const int MAX = 10000000000000000;
int f[210][210][210], qA[9000000], qB[9000000], qC[9000000];
char used[210][210][210];
int i, j, k, t, a, b, c, d, MAXD, MINS, nxt, lst;
void check(int D, long long SUM) {
if (D <= d)
if (D > MAXD  (D == MAXD && SUM < MINS) ) {
MAXD = D;
MINS = SUM;
}
}
void add(int I, int J, int K, int poured) {
if (!used[I][J][K]) {
used[I][J][K] = 1;
f[I][J][K] = f[i][j][k] + poured;
qA[lst] = I;
qB[lst] = J;
qC[lst++] = K;
check(I, f[I][J][K]);
check(J, f[I][J][K]);
check(K, f[I][J][K]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
scanf("%d", &t);
while(t) {
scanf("%d %d %d %d", &a, &b, &c, &d);
memset(used, 0, sizeof(used));
qA[0] = 0;
qB[0] = 0;
qC[0] = c;
f[0][0][c] = 0;
used[0][0][c] = 1;
MAXD = MINS = 0;
for (nxt = 0, lst = 1; nxt < lst; nxt++) {
i = qA[nxt];
j = qB[nxt];
k = qC[nxt];
if (i) {
if (i + j > b) add(i + j  b, b, k, b  j);
else add(0, i + j, k, i);
if (i + k > c) add(i + k  c, j, c, c  k);
else add(0, j, i + k, i);
}
if (j) {
if (j + k > c) add(i, j + k  c, c, c  k);
else add(i, 0, j + k, j);
if (j + i > a) add(a, j + i  a, k, a  i);
else add(j + i, 0, k, j);
}
if (k) {
if (k + i > a) add(a, j, k + i  a, a  i);
else add(k + i, j, 0, k);
if (k + j > b) add(i, b, k + j  b, b  j);
else add(i, k + j, 0, k);
}
}
printf("%lld %d\n", MINS, MAXD);
}
return 0;
}
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10603  Fill
Change line 101 to:
printf("%d %d\n", MINS, MAXD);
Try changing line 8 to:
char used[201][201][201];
You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.
I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
You could try making your functions inline.
printf("%d %d\n", MINS, MAXD);
Try changing line 8 to:
char used[201][201][201];
You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.
I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
You could try making your functions inline.
Check input and AC output for thousands of problems on uDebug!
Re: 10603  Fill
After this sentence i have a question:
If we come to a visited state and we have less poured water, in my opinion we should change old value to the new better value. But in this case this problem cannot be solved by BFS. It becomes a DP problem which must be solved using Deikstra algo. Am i right?I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10603  Fill
I solved it using a full BFS, not Dijkstra's algorithm. I kept track of the min amount of water poured to get to every possible d', but continued with the BFS even if the amount of water poured to get to that d' was greater than before. Each reachable state in your used array should only be visited once. This isn't for reducing runtime, but the way your code only kept track of the min water poured for the current d' is probably wrong.
Check input and AC output for thousands of problems on uDebug!
Re: 10603  Fill
I changed my BFS to Dijkstra's algo but again got TLE.
Then i made changes which you recommended and got acc with runtime 2.725.
And changed it to
A got acc with runtime 0.736. The main reason of getting TLE was using memset of full array.
Thanks for your help!
By the way with the modifications that you said my BFS avoided TLE. But got WA.
If you solved this problem with BFS than its a bit modified BFS. Because i think that BFS must be used in unweighted graph, and once you have reached a node by BFS it must be the path minimal cost or value. Maybe i am wrong
Then i made changes which you recommended and got acc with runtime 2.725.
At last i removed the lineChange line 101 to:
printf("%d %d\n", MINS, MAXD);
Try changing line 8 to:
char used[201][201][201];
You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.
I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.
You could try making your functions inline.
Code: Select all
memset(used, 0, sizeof(used));
Code: Select all
for (i = 0; i <= a; i++)
for (j = 0; j <= b; j++)
for (k = 0; k <= c; k++) used[i][j][k] = 0;
Thanks for your help!
By the way with the modifications that you said my BFS avoided TLE. But got WA.
If you solved this problem with BFS than its a bit modified BFS. Because i think that BFS must be used in unweighted graph, and once you have reached a node by BFS it must be the path minimal cost or value. Maybe i am wrong
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10603  Fill
Yes you can also solve this with Dijkstra's algorithm.
You could also try changing used to an int array:
You could also try changing used to an int array:
Code: Select all
for (i = 0; i <= a && i <= C; i++)
for (j = 0; j <= b && i + j <= C; j++)
used[i][j][C  i  j] = INT_MAX;
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 3
 Joined: Fri Jun 20, 2014 9:51 am
10603Fill
Hi,
I got WA for this.Why?
I got WA for this.Why?
Code: Select all
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>
using namespace std;
struct state
{
int water[3];
int amt;
bool operator < (const state& s) const
{
for (int i = 0 ; i < 2 ; ++i)
{
if (water[i] != s.water[i])
{
return water[i] < s.water[i];
}
}
return water[2] < s.water[2];
}
};
int cap[3];
int d;
set<state> ss;
int r_d;
int r_cnt;
bool is_visited(state& s)
{
set<state>::iterator it = ss.find(s);
if (it != ss.end())
{
if (it>amt > s.amt)
{
ss.erase(it);
return false;
}
return true;
}
return false;
}
void set_visit(state& s)
{
ss.insert(s);
}
void bfs()
{
queue<state> q;
state tmp;
tmp.water[0] = tmp.water[1] = tmp.amt = 0;
tmp.water[2] = cap[2];
q.push(tmp);
while (!q.empty())
{
state tmp = q.front();
q.pop();
set_visit(tmp);
int max_liter;
for (int k = 0 ; k < 3 ; ++k)
{
if (k == 0)
{
max_liter = tmp.water[k];
}
else if (tmp.water[k] <= d && tmp.water[k] > max_liter)
{
max_liter = tmp.water[k];
}
}
if (max_liter <= d)
{
if (max_liter > r_d)
{
r_d = max_liter;
r_cnt = tmp.amt;
}
if (max_liter == r_d && r_cnt > tmp.amt)
{
r_cnt = tmp.amt;
}
}
for (int i = 0 ; i < 3 ; ++i)
{
if (tmp.water[i] == 0)
{
continue;
}
for (int j = 0 ; j < 3 ; ++j)
{
if (i == j)
{
continue;
}
if (tmp.water[j] < cap[j])
{
state next;
memcpy(&next,&tmp,sizeof(next));
int cnt = next.water[i] < (cap[j]  next.water[j]) ? next.water[i] : (cap[j]  next.water[j]);
next.water[i] = cnt;
next.water[j] += cnt;
next.amt += cnt;
if (!is_visited(next))
{
q.push(next);
}
}
}
}
}
}
void read_input()
{
scanf("%d%d%d%d",&cap[0],&cap[1],&cap[2],&d);
r_d = r_cnt = 0;
}
int main()
{
#ifdef shichun
freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
#endif
int n;
scanf("%d",&n);
while (n)
{
read_input();
bfs();
printf("%d %d\n",r_cnt,r_d);
}
return 0;
}
Re: 10603Fill
Don't open new thread. Search for existing thread about this problem first.
On every boards Volume header said
For input
your program gives
my acc problem gives
I didn't checked your code.
Maybe one of problems is not memseting (cleaning) old results because when i changed the order of tests your program gave correct result for the first test
input
your program gives
On every boards Volume header said
Try to use existing threads and continue it.If there is a thread about your problem, please use it.
For input
Code: Select all
2
93 157 199 67
96 97 199 62
Code: Select all
343 64
3468 12
Code: Select all
250 64
9859 62
Maybe one of problems is not memseting (cleaning) old results because when i changed the order of tests your program gave correct result for the first test
input
Code: Select all
2
96 97 199 62
93 157 199 67
Code: Select all
9859 62
343 64
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman