571 - Jugs

[Red Scorpion]

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]

My program solved it in 0.1 second using BFS.

[Red Scorpion]

You're right eloha, BFS can solved this problem. There are something wrong with my BFS. Now I got AC.

Thanks, Eloha.
RS

[zizi]

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]

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]

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

[Aleksandrs Saveljevs]

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]

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

[little joey]

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]

I have answers with the same length as you , little joey ... (If I dont count 'success' as step) ... and still WA ...

Best regards
DM

[Dominik Michniewski]

Finally I solved it with nice time (0.016 sec). I made stupid (!!!!!!) mistake in output So BFS works fine

Best regadrs
DM

[Aleksandrs Saveljevs]

First, congratulations on getting it accepted.

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]

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]

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]

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.