## 571 - Jugs

Moderator: Board moderators

Red Scorpion
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

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
My program solved it in 0.1 second using BFS.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
You're right eloha, BFS can solved this problem. There are something wrong with my BFS. Now I got AC.

Thanks, Eloha.
RS

zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

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

Dominik Michniewski
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
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)

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
Let me give you a hint:
...A and B are relatively prime to one another.
That means you can get any modulo B (0...B-1) you want. You only have to find out how.

PS: If I tell how, that will be way too easy. Sorry.
PPS: Try doing something with A.

Dominik Michniewski
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
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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
There is a contadiction in the problem description
A solution is a sequence of steps that leaves exactly N gallons in jug B.
and
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.
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.
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
``````
The solution should have 6, 6, 6, 14, 6, 10 and 1 step(s).

Dominik Michniewski
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
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)

Dominik Michniewski
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

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)

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:
First, congratulations on getting it accepted.
Dominik wrote:I don't get TLE but WA...
Oops. I thought you got TLE. Pardon.

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.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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.

poti
New poster
Posts: 3
Joined: Mon Mar 06, 2006 5:48 pm
is it said that we should output the sequence with minimal moves sequences

my prog outputs different combination of moves(1 or 2 steps longer) but it gives right output.

help!!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
If you output is one or two steps longer than the judge sample, so it is not the minimum steps. Hint: Use bfs, its solution will ensured to be minimum length.