saba_tavdgiridze's blog

POI[2012] Tour de Byteotia
By saba_tavdgiridze, history, 9 years ago, In English

Can anyone give me an idea how to solve this problem ? Tour de Byteotia Thanks in advance!

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saba_tavdgiridze (previous revision, new revision, compare).

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

Am I right or it is enough to find any spanning tree and delete other edges?

Apart from that, POIs have editorials. Try searching oi.edu.pl website

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    You're wrong since the graph is not necessarily connected, hence it can have no spanning tree.
    By the way, even if the input graph always had a spanning tree, the solution would be still wrong.
    Simply consider a clique, where you would add N - 1 edges and at least is possible.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Let's try to add the maximum amount of edges so that no cycle passes through vertices 1..K.
You can first of all add all "safe" edges (x; y) — those which have x>K and y>K.
After that, iterate through the others, and add an edge only in case it won't form a cycle (this can be checked with the help of DSU).
After we're done, the answer is formed by the edges we didn't add.

→ Reply