Friday, December 28, 2012

USACO - Mother's Milk

I don't know why, but I had a great misunderstanding of the problem statement from this sentence "FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty" :-) I thought by second bucket he means bucket B, and by first bucket he means bucket A. But no problem I will pay more attention from now on. So after I understood the problem statement correctly, I thought a little about the "states" in pouring buckets, I felt that I can present each state as a node, and cause each bucket has a capacity from 1 to 20, so we have at most 20*20*20 nodes, we can DFS over all of them and find what can remain at bucket C when bucket A is empty. Now that we have presented nodes, we are facing a graph, graphs do need edges don't they? (Unless we are facing a null graph). So what is an edge in our graph? By edge I mean how can we go from one node to another? Consider first sample input in the problem statement, Suppose this triple as a staring node (0,0,10), what other nodes can we visit directly from this node?
(8,0,2) & (0,9,1) am I right? what happens after that? Just like DFS (or BFS) other nodes that are not visited and can be visited, must be visited :-) (too many 'visited's) 

3 comments:

  1. When would the tree terminate? To me it seems that you could continue to pour milk between jugs indefinitely. (Though this thought is most likely incorrect, I don't understand why.)

    ReplyDelete
    Replies
    1. You would need to keep some kind of hash set to store nodes already visited, eventually the the nodes won't be unique anymore and the tree will terminate.

      Delete