SEFI2's blog

IOI 2012 problem
By SEFI2, 10 years ago, In English

hi everybody, help me with this problem, please.

i read hints for task but didnt understand how to check the candidates they are criticals in optimal time.

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

»
10 years ago, # |
← Rev. 7   Vote: I like it +15 Vote: I do not like it

I am currently solving IOI problems to get ready for the upcoming IOI problem and this one is really cool in my opinion. I'll explain the way I constructed my solution, it may not be optimal or easiest but it worked and it is pretty fast and easy to code in my opinion.

First let's see how do we keep track of cycle formation, i.e. how to know if a cycle has formed after the addition of some edge. This is pretty easy to do if we use Union Find. If the edge connects vertices that are already from the same set, obviously we get a cycle. Cycle tracking will be the only thing we need in order to solve the problem.

Let's number the states we could be in (according to my solution) :

State 1 — linear graph (set of disjoint paths) — answer is the number of vertices in the graph.

State 2 — there is a single cycle — answer is the number of vertices that lie on the cycle

State 3 — there is some vertex of degree 3 or larger — the critical vertices can be only it or its neighbours

State 4 — "blocked" graph, i.e. there are no critical vertices — answer is 0

Now, suppose a query of connecting vertices A and B comes. Let's see what we do in each possible case.

If we are in state 1 currently : if the vertices are from different sets — we continue being in state 1. If the vertices are from the same set, simply use a dfs to find the amount of vertices that lie on the cycle, and change the state to 2.

If we are in state 2 currently : if after adding the edge, the degrees of A and B are both less than 3 and a new cycle is formed — go to state 4 as the graph will be forever blocked. If the degrees of A and B are both less than 3 and no new cycle is formed — simply stay in the same state. If A or B's degrees becomes 3 go to state 3.

In my solution, upon going to state 3 we create 4 separate graphs. Since upon going in state 3 we have at most 4 candidates (the vertex with degrees 3 and its neighbours) we create 4 different graphs in each of which some candidate doesn't exist. Now what we do is keep track of cycle formation in those 4 new graphs. If at some point some graph becomes non-linear — simply the candidate it corresponded to is no longer critical and we can throw that graph away.

If we are in state 3 currently : update in all 4 graphs adding the edge (unless it connects to the removed vertex, the candidate) and check if a cycle is formed. If in some graph a cycle is formed, declare the graph as blocked and the candidate it corresponded to as non-critical. At the end the answer for your query will be the number of graphs that are still linear (0~4).

If we are in state 4 — simply do nothing, and return 0 upon queries, once blocked the graph can't be unblocked.

Note that my solution relies on the observation that once a vertex becomes non-critical, it can never be critical again. The idea of keeping 4 graphs at once seemed simplest to me, there may be another easier solution but I do not think that implementing that solution is hard at all.

Assuming Union-Find's complexity is O(log* N) we get worst-case O(4 * Q * log* N) = O(Q * log* N)

If you have any questions, feel free to ask me :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    On the contest I've written exactly the solution you've described. Unfortunately, TL was very strict, and it didn't pass the last two (as I remember) groups. All my attempts of non-asymptotic optimization weren't successful.

    Reason is that DSU is in fact heavy data structure with some big enough constant, and here we are using 5 copies of that data structure (one for source graph and four for state 3). In fact all you need for that four copies is observing if all the components are paths and handling cycle creation events. It can be done without using DSU in linear time (storing at most two neighbors for each vertex), so the solution complexity will be O(Q), that is enough to pass.

    I was really surprised because for me it was first example of the task where DSU wasn't fast enough. Some other participants of that contest faced the same problem too.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      That seems very odd, I've never seen DSU act slow or heavy. I couldn't find the exact time limit, however my solution works for 1300ms on the largest testcase. The time limit must've been 1s which is very harsh. It seems to me that it should be possible to optimize it enough to pass but I'll take your word for it. However if it did time limit indeed, it must've been only on Subtask 5, since Subtask 4 is N,Q<=100,000 in which simply there is no way it could work that slow, my solution takes less than 100ms for testcases with N,Q<=100,000.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes, there were actually problems with subtasks 2 and 5.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        As far as I remember, we got some success with DSU (not sure if whether it was a full score or not) after optimizing it in a non-asymptotic way: get rid of recursion (and store stack of vertices in a static array during path compression)), pack values into one array of structs instead of two and all that stuff which is usually irrelevant.

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

IGNORED

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Ah, the nostalgia. I tried something that involved a loooot of casework, and almost got the problem working for full score — I was failing just on 1 or 2 test cases per batch (which means it was probably the same 1 or 2, and I missed a special case). It's kind of funny to watch how many people had a hard time optimizing already working solutions, while it was a "0 or 100" problem for me...

→ Reply