http://usaco.org/index.php?page=viewproblem2&cpid=360 Please tell me how to solve this.I am stuck.I think I am not also getting what the question wants to ask. asked 02 Oct '14, 23:15

The question essentially asks you to find the number of distinct pairing of wormholes such that there is a position on the map which leads to Bessie getting trapped when she starts moving in the +x direction from that position. Two pairings are different if at least one wormhole is paired with a different wormhole in the two pairings. Looking at the constraints, you can tell that brute force must be possible. Total number of distinct pairings can be calculated to check: (12C2 * 10C2 * 8C2 * 6C2 * 4C2 * 2C2 ) / 6! = 11 * 9 * 7 * 5 * 3 *1 = 10395. For each pairing, you can check by running a modified DFS if there is a cycle in the graph described by the pairing. You would have to add edges between wormholes with the same ycoordinate, the edge going from the left wormhole(one with lesser value of xcoordinate) to the right one(one with greater value of xcoordinate). answered 03 Oct '14, 12:44
