Hello all.
There was a problem from the ACM Greater NY Contest that my team was unable to solve. The problem statement can be found here. It is not mentioned in the problem statement, but K represents the current test case number, while N <= 600.
We feel that it can ultimately be reduced to a graph problem, but don't know how to go about doing so. Could you give me any hints on how to solve it?
This problem seems very similar to lostcows found here: http://tjsct.wikidot.com/usaco-feb11-gold (without the reconstruction). You can see the editorial here http://contest.usaco.org/TESTDATA/FEB11.lostcows.htm (for this version, you'll need some additional optimizations since N is larger, though the number of outgoing edges is much smaller).
A hint is to think about an easier version when you only have two robots on different signposts and want to merge them together. It may also be helpful to think about how you would actually reconstructing the sequence, if it exists.
Thanks, Lewin. I'll look into modifying that solution to work for my problem.
Nice problem. I do not know solution in suggested editorial. But it seems that: 1. Solution exists <=> exists sequence of buttons for any pair. 2. Now graph problem :) To resolve suggest in 1. Create graph G(V,E), where V={(i,j), i,j=1..n}. We want to mark all vertices that satisfy 1. Initially mark only (i,i), i=1..n. E create by buttons, every button add edges: (Ai,Aj)->(i,j), i,j=1..n. So every button add n*n edges, and |E|=n*n*k, where k — number of such buttons. All pairs that satisfy 1 are reachable from (i,i), i=1..n. It solve by time O(V+E)=O(n*n*k) and equal memory.