satirmo's blog

Graph Problem
By satirmo, history, 8 years ago, In English

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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like 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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, Lewin. I'll look into modifying that solution to work for my problem.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply