zscoder's blog

JOI 2012/2013 Contest — Spaceships
By zscoder, history, 8 years ago, In English

Problem statement :

There are N planets in the galaxy. For each planet i, it has two possible states : empty, or it is connected to some other planet j ≠ i with a one-way path. Initially, each planet is in the empty state (i.e. there are no paths between any pair of planets)

There are three types of operations :

  1. If planet i is in empty state, connect it with planet j with a one-way path (i and j are distinct)

  2. If planet i is currently connected to planet j with a one-way path, remove that path. Consequently, planet i is now in empty state again

  3. For a pair of planets u, v, find a planet x such that one can travel from u to x and v to x. If there are multiple such planets, find the one where the total distance travelled by u and v is minimized (distance is the number of paths it passes through). If there are no solutions, output  - 1.

Q, N ≤ 106. Time limit is 10 seconds.

One of the official solutions uses splay tree to solve this problem, but I have no idea how it works (I haven't use splay trees before). Can anyone tell me how to use splay tree on this problem? Thanks.

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

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

The problem seems interesting. My only idea of splay tree usage would be Link-Cut Trees, though a solution with them is not obvious. The structure of the resulting graph can be represented as a forest but the trees' roots can be cycles which makes stuff complicated.

Can you provide a link with the author solution (code) ?

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

    Sure, here is the Splay Tree solution.

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

      After some google translates and browsing the editorial of the problem (277 slides in Japanese) I finally found what I wanted to. There's an additional constraint that you did not mention — cycles can't be formed. It's an extremely important constraint since now the whole structure of the graph indeed becomes a forest and Link-Cut Trees start making a lot more sense.

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

        Actually this is said in first paragraph:

        1. If planet i is in empty state, connect it with planet j with a one-way path (i and j are distinct)
        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I believe empty state refers to not having an outgoing edge? A single vertex can have arbitrarily many ingoing edges and still be in an empty state. This constraint does not imply the lack of cycles.

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

        I don't understand how the author's Splay Tree solution work. Can you enlighten me? (I don't get why there is splay() and splaySolid())

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

          I'm not sure how it works either. I believe it is a toned-down version of Link-Cut Tree (if you're not familiar with those, you'll have to read some).

          Once we know that cycles can't form we're basically given the problem of keeping a dynamic forest and answering LCA questions. Link-Cut Trees are a great specifically for such problems, though I'm not too good with them and hence I don't understand author's solution.

          The Japanese editorial however mentions two methods — one is Link-Cut and the other is Euler Path Trees which I find much easier to understand in this problem, even if it is harder to implement.

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

          Looks like splaySolid() is usually called "splay" and splay() is usually called "expose".

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

UPD: I've missed that the graph should be directed.

→ Reply