571 - Jugs
Moderator: Board moderators
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
571-Jugs-BFS ?
I use BFS to break this problem, but get TLE.
Is this problem can't be done using BFS ?
Am I in the right track ?
Thanks.
RS
Is this problem can't be done using BFS ?
Am I in the right track ?
Thanks.
RS
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
571 - Jugs
I got TLE for this problem by using brute force ,is there anyway to imporve it?
More over,the problem said that when either of the jugs containing exactly N gallons of water ,you can show the result .But in the example output ,the result is shown only when jug B has N gallons of water .Pls explain for me because there's a shorter way if we can also fill N-gallons in jugA .
Thanks
More over,the problem said that when either of the jugs containing exactly N gallons of water ,you can show the result .But in the example output ,the result is shown only when jug B has N gallons of water .Pls explain for me because there's a shorter way if we can also fill N-gallons in jugA .
Thanks
its ok
Hi zizi,
a brute-force solution will obviously get TLE. Backtracking and minor pruning should be enough. -- make sure you don't get the same combination of water in the jugs twice.
There is a yellow tick associated with it -- meaning it has got multiple outputs. So it does not matter which jug ends up having the liquid. It does not always have to be B.
Hope it helps.
a brute-force solution will obviously get TLE. Backtracking and minor pruning should be enough. -- make sure you don't get the same combination of water in the jugs twice.
There is a yellow tick associated with it -- meaning it has got multiple outputs. So it does not matter which jug ends up having the liquid. It does not always have to be B.
Hope it helps.
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
Could anyone help me with this problem ?
I try to solve it with BFS (something like state machine in which I walk only to unvisited states).
Are there some special, tricky inputs ?
I can send my code to intrested persons
Best regards
DM
I try to solve it with BFS (something like state machine in which I walk only to unvisited states).
Are there some special, tricky inputs ?
I can send my code to intrested persons
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- New poster
- Posts: 39
- Joined: Fri Nov 14, 2003 11:18 pm
- Location: Riga, Latvia
- Contact:
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
I don't understand you, Aleksandrs ... Coudl you explain it ?
I don't get TLE but WA ... So I think that I find solution if it exist. When I use BFS it's impossible (I think) that I'll find solution which is longer that shortest one ... So why WA ?
I consider six operations on jugs: fill/empty A, fill/empty B, pour A->B , pour B->A.
Best regards
DM
I don't get TLE but WA ... So I think that I find solution if it exist. When I use BFS it's impossible (I think) that I'll find solution which is longer that shortest one ... So why WA ?
I consider six operations on jugs: fill/empty A, fill/empty B, pour A->B , pour B->A.
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
There is a contadiction in the problem description
My program only stops when B contains N and gets accepted, so that is the proper condition.
As is often the case with Miguel A. Revilla's problems, the descriptions are in crooked English, ambiguous or contradictory as in this case, and sometimes the judges i/o doesn't match the description. This results in a lot of wasted submissions. On the other side, this man has done a lot to set up and maintain this wonderful site, and has written countles, mostly very interesting and original problems. He is invaluable to our programmers community, but he should have his texts looked over by someone with a better command of the English language
Dominik:
BFS should work. Try this input
The solution should have 6, 6, 6, 14, 6, 10 and 1 step(s).
andA solution is a sequence of steps that leaves exactly N gallons in jug B.
Looking at the output for the second example, it's clear that only the first condition holds (B should contain N) because A contains N one step earlier.Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water.
My program only stops when B contains N and gets accepted, so that is the proper condition.
As is often the case with Miguel A. Revilla's problems, the descriptions are in crooked English, ambiguous or contradictory as in this case, and sometimes the judges i/o doesn't match the description. This results in a lot of wasted submissions. On the other side, this man has done a lot to set up and maintain this wonderful site, and has written countles, mostly very interesting and original problems. He is invaluable to our programmers community, but he should have his texts looked over by someone with a better command of the English language
Dominik:
BFS should work. Try this input
Code: Select all
3 5 4
5 7 3
11 13 9
27 59 17
19 37 1
67 91 19
1 1 1
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
I have answers with the same length as you , little joey ... (If I dont count 'success' as step) ... and still WA ...
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
Finally I solved it with nice time (0.016 sec). I made stupid (!!!!!!) mistake in output So BFS works fine
Best regadrs
DM
Best regadrs
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- New poster
- Posts: 39
- Joined: Fri Nov 14, 2003 11:18 pm
- Location: Riga, Latvia
- Contact:
First, congratulations on getting it accepted.
Anyway, I'll explain what I was trying to hint at.
Since A and B are relatively prime, the sequence A, A+A, A+A+A, ... yields every modulo B (0...B-1). As you can see, it's pretty trivial from now on.
By the way, my code stops when the amount needed is in any of the jugs. So no problem here, I guess.
Oops. I thought you got TLE. Pardon.Dominik wrote:I don't get TLE but WA...
Anyway, I'll explain what I was trying to hint at.
Since A and B are relatively prime, the sequence A, A+A, A+A+A, ... yields every modulo B (0...B-1). As you can see, it's pretty trivial from now on.
By the way, my code stops when the amount needed is in any of the jugs. So no problem here, I guess.
I tried to use BFS to solve this problem, but got SIGSEV. Does anyone see what is wrong? I've tried littering the code with asserts, but it was no help. :( The idea of my code is to keep track of which states have been visited in the states array. states[j][2] is 0 iff we haven't visited the state yet where jug A has i gallons and jug B has j gallons. otherwise, states[j][2] represents what operation we performed to get to state i,j from the state states[j][0],states[j][1]. once BFS finds a state where jug B has the target amount of gallons, we run backwards through the states array 'til we get back to 0,0, then we print forwards again.
EDIT: Note to people who looked at this code before this edit. I have changed states from a char array to an int one since states[j][0] and states[j][1] can be as large as 1000. i still get sigsev though, save me please! :)
[cpp]
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#include <stdlib.h>
#include <stdio.h>
int done,states[1001][1001][3];
enum { pour_a=1,pour_b,fill_a,fill_b,empty_a,empty_b };
queue<pair<int,int> > q;
int a,b,n;
void print_out(int x, int y) {
int i,xx=x,yy=y,temp;
vector<int> ops;
while (xx || yy) {
ops.push_back(states[xx][yy][2]);
temp = xx;
xx = states[xx][yy][0]; yy = states[temp][yy][1];
}
for (i=ops.size()-1;i>=0;i--) {
if (ops==fill_a) printf("fill A\n");
else if (ops==fill_b) printf("fill B\n");
else if (ops==empty_a) printf("empty A\n");
else if (ops==empty_b) printf("empty B\n");
else if (ops[i]==pour_a) printf("pour A B\n");
else printf("pour B A\n");
}
}
void go(int x, int y) {
if (y==n) {
done = 1;
return;
} else {
int xx,yy;
if (!states[0][y][2]) {
states[0][y][2] = empty_a;
states[0][y][0] = x; states[0][y][1] = y;
q.push(make_pair(0,y));
}
if (!states[x][0][2]) {
states[x][0][2] = empty_b;
states[x][0][0] = x; states[x][0][1] = y;
q.push(make_pair(x,0));
}
if (!states[a][y][2]) {
states[a][y][2] = fill_a;
states[a][y][0] = x; states[a][y][1] = y;
q.push(make_pair(a,y));
}
if (!states[x][2]) {
states[x][2] = fill_b;
states[x][0] = x; states[x][1] = y;
q.push(make_pair(x,b));
}
yy = y + x;
xx = x - (b-y);
if (xx<0) xx = 0; if (yy>b) yy = b;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_a;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
xx = x + y;
yy = y - (a-x);
if (yy<0) yy = 0; if (xx>a) xx = a;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_b;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
}
}
int main() {
int i,j;
char buff[20];
while (strlen(gets(buff))>1) {
q = queue<pair<int,int> >();
sscanf(buff,"%d %d %d",&a,&b,&n);
done = 0;
q.push(make_pair(0,0));
for (i=0;i<=a;i++) for (j=0;j<=b;j++) states[i][j][2] = 0;
states[0][0][2] = 1;
while (!q.empty()) {
pair<int,int> p = q.front();
q.pop();
go(p.first,p.second);
if (done) {
print_out(p.first,p.second);
break;
}
}
printf("success\n");
}
exit(0);
}
[/cpp]
Thanks.
EDIT: Note to people who looked at this code before this edit. I have changed states from a char array to an int one since states[j][0] and states[j][1] can be as large as 1000. i still get sigsev though, save me please! :)
[cpp]
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#include <stdlib.h>
#include <stdio.h>
int done,states[1001][1001][3];
enum { pour_a=1,pour_b,fill_a,fill_b,empty_a,empty_b };
queue<pair<int,int> > q;
int a,b,n;
void print_out(int x, int y) {
int i,xx=x,yy=y,temp;
vector<int> ops;
while (xx || yy) {
ops.push_back(states[xx][yy][2]);
temp = xx;
xx = states[xx][yy][0]; yy = states[temp][yy][1];
}
for (i=ops.size()-1;i>=0;i--) {
if (ops==fill_a) printf("fill A\n");
else if (ops==fill_b) printf("fill B\n");
else if (ops==empty_a) printf("empty A\n");
else if (ops==empty_b) printf("empty B\n");
else if (ops[i]==pour_a) printf("pour A B\n");
else printf("pour B A\n");
}
}
void go(int x, int y) {
if (y==n) {
done = 1;
return;
} else {
int xx,yy;
if (!states[0][y][2]) {
states[0][y][2] = empty_a;
states[0][y][0] = x; states[0][y][1] = y;
q.push(make_pair(0,y));
}
if (!states[x][0][2]) {
states[x][0][2] = empty_b;
states[x][0][0] = x; states[x][0][1] = y;
q.push(make_pair(x,0));
}
if (!states[a][y][2]) {
states[a][y][2] = fill_a;
states[a][y][0] = x; states[a][y][1] = y;
q.push(make_pair(a,y));
}
if (!states[x][2]) {
states[x][2] = fill_b;
states[x][0] = x; states[x][1] = y;
q.push(make_pair(x,b));
}
yy = y + x;
xx = x - (b-y);
if (xx<0) xx = 0; if (yy>b) yy = b;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_a;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
xx = x + y;
yy = y - (a-x);
if (yy<0) yy = 0; if (xx>a) xx = a;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_b;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
}
}
int main() {
int i,j;
char buff[20];
while (strlen(gets(buff))>1) {
q = queue<pair<int,int> >();
sscanf(buff,"%d %d %d",&a,&b,&n);
done = 0;
q.push(make_pair(0,0));
for (i=0;i<=a;i++) for (j=0;j<=b;j++) states[i][j][2] = 0;
states[0][0][2] = 1;
while (!q.empty()) {
pair<int,int> p = q.front();
q.pop();
go(p.first,p.second);
if (done) {
print_out(p.first,p.second);
break;
}
}
printf("success\n");
}
exit(0);
}
[/cpp]
Thanks.