JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial PlayingCubes solution using MaxFlow
 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
 Forums Tutorial Discussions Maximum Flow tutorial PlayingCubes solution using MaxFlow Previous Thread  |  Next Thread