JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
PlayingCubes solution using MaxFlow | Reply
Hello! Could someone explain me how to solve this problem http://www.topcoder.com/stat?c=problem_statement&pm=4731&rd=8016 using MaxFlow (problem as an example from the tutorial)? I settled with a maximum bipatile matching algorithm, but it doesn't work (at least in my implementation).
So what is I am doing:
To check whether it is possible to combine a word with given set of cubes, I am using the following algorithm (let's take the example 1 from the problem statement):
Word: "BIRD", Cubes: {"ABCDEF", "DEFGHI", "OPQRST", "MNZLSA", "QEIOGH", "IARJGS"}
I am creating a flow network with the set of letters L, the set of cubes R. So, common scheme:

S - L - R - T.

There is an edge between vertices Li and Rj (1 <= i <= |L|, 1 <= j <= |R|) if cube Rj contains letter Li. All the edges have capacity 1.
So, in my understanding, there can be flow 4, so we can combine the cubes to get word "BIRD" as follows: (letter-cube (0-based):'B'-0, 'I'-4, 'R'-5, 'D'-1). And ok, this is a right answer according to the example answer.

But my algo does not give me MaximumMatching 4. I am using Endmonds-Karp algo. At each iteration I am looking for a shortest augmenting path in the residual network, and assign a flow along this path.
But what if first found path contains letter 'B' + cube 0, and second found path contains letter 'I' - cube 1 ("DEFGHI") (both have the same length)? In that case I will not be able to have letter 'D' as only cubes 0 and 1 contain it, and they are already used!

So, summarizing, my difficulty is: when I see the network of the given case, it seems to be a maximum bipatile matching, and Endmonds-Karp algo should work in this case, but it doesn't. Did I miss something important? Thanks!
Re: PlayingCubes solution using MaxFlow (response to post by root85) | Reply
But what if first found path contains letter 'B' + cube 0, and second found path contains letter 'I' - cube 1 ("DEFGHI") (both have the same length)? In that case I will not be able to have letter 'D' as only cubes 0 and 1 contain it, and they are already used!
Then there still exists an augmenting path:
S - 'D' - "DEFGHI" - 'I' - "QEIOGH" - T.

Note that a part of some previous flow will be pushed back in this path. That's the cool thing of maxflow. So this path gives cube "DEFGHI" to 'D' and let 'I' change from cube "DEFGHI" to "QEIOGH".

So your approach is right. I think you have an implementation bug. Do you handle the capacities right? If you assign a flow over an edge from u to v and decrease the capacity from u to v, then you have to increase the capacity of the edge from v to u.
Re: PlayingCubes solution using MaxFlow (response to post by mishastassen) | Reply
Thank you,mishastassen! Finally got it. Yes that was an implementation bug - I used two 2-dimensional arrays - flow[,] and cap[,]. After I removed the first one and wrote a proper handling of cap[,] my solution passed the systests. Had some stupid errors, I think. Code is in practice room
RSS