I need a piece of advice on above problem. The most difficult part of it for me was the fact that to solve it you need to detect that connection appeared on the last move and there was no connection one move before.
This happens only if by removing just one piece from the table you can break connection. With the problem limits provided, it is possible to solve this problem "brute-force" style, removing pieces one by one and checking if connection was lost. If you couldn't break connection by removing one piece, then connection couldn't happen on the last move. Brute force worked nicely - approximately 90 seconds in Python for hard. Still, I am not sure that this was intended solution. I tried some other approaches. In the essence it boils down to detecting if there is a bottleneck node in the graph. a) mincut didn't work for me, as it helps to detect bottleneck edge, not bottleneck node. b) various experiments with BFS / DFS didn't work for me. c) tried searching for similar problems online - lots of information on searching for bottleneck edge, but couldn't find anything about bottleneck nodes. Is there some modification of data or algorithm which can help apply maxflow/mincut to this problem? I know there are lots of C++ solutions for download - I find C++ quite cryptic, especially when written in "competition mode" and I am not yet so desperate to decode. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/2e952a7a-e82a-4949-b8f6-4b47be1ea7f3%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
