this is a question i found while solving problems from pratice arena on codechef.
I saw many solutions but could not understand the logic.
On some of the posts i found that DIOPHANTUS has given the solution for this, but could not get any relevant material.
Further, the editorial of this question is not provided.
please help me in understanding this problem.
The link is not working foe me ??
The water jug problem can be solved using the extended-eucildean algorithm. Extended-euclidean algorithm finds solution for diophantine equations. How does finding solution of diophantine equation solves the water jug problem? Let me demonstrate:
Imagine you have a jug of 5 liters ( A ) and 3 liters ( B ). You want to make 1 liter of water with this 2 container. The the equation will be, 5x + 3y = 1 ( Ax + By = 1 ). If we can find a solution this equation then our problem is solved. Apply extended_euclidean algorithm on it and you will find that the result is x = 2 and y = -3.
If we put value of x and y in the equation then we get 5 * 2 + 3 * ( -3 ) = 10 - 9 = 1. The equation is indeed solved. But what does x = 2 and y = -3 mean? It means, we need to fill our A bottle 2 times and empty our B bottle 3 times.
This how it will go:
A B
5 (fill Once )
2 3 ( Transfer 3 liter )
2 0 ( Empty Once )
0 2 ( Transfer 2 liter )
5 (fill Twice ) 2
4 3 ( Transfer 1 liter )
4 0 ( Empty Twice )
1 3 ( Transfer 3 liter )
1 0 ( Empty Thrice )
So now that you know the meaning behind the solution, how do you find the number of steps? I guess simulate. You know which bottle you need to fill and which to empty, so do it. Just think about it for a while, it should become clear.
There are other solution to water jug problem, such as BFS and DP. You can give those a try too if you want.
Read this article ( http://e-maxx.ru/algo/extended_euclid_algorithm to learn how to use extended euclidean algorithm.
4 Likes
Hello everyone , I implemented Extended Euclidean Algorithm . But i am not getting how to solve this [http://www.codechef.com/problems/POUR1][1] problem with the help of Extended Euclidean Algorithm.
I got the point explained by @forthright , that we have to find the solution of ax + by = 1.
Is it same for this problem i mean do we need to find the value of x and y for ax + by = c ?
Please anybody explain how to solve this problem using Extended Euclidean Algorithm .
Happy Coding!!!
[1]: http://www.codechef.com/problems/POUR1
can this problem be solved using bfs ???
Yes of course, this link may help you :
Can you please elaborate the advantage of using Extended Euclidean method instead of the Euclidean GCD method here
You may find the proof of Arithmetic solution for this problem here :
http://www.iaeng.org/publication/WCE2013/WCE2013_pp145-147.pdf
1 Like
I think the answer of forthright is wrong…
as we can do that in 4 steps
a(5ltr) b(3ltr)
0 3
3 0
3 3
5 1
hence we got 1 ltr in 4 steps