Gerald's blog

Codeforces Beta Round #88 (Editorial)
By Gerald, 13 years ago, translation, In English
Consider three cases.
  • s = f, ans = t.
  • s < f, we must find the smallest non-negative k such, that t ≤ (s - 1) + 2(m - 1)k. ans = s - 1 + 2(m - 1)k + (f - s).
  • s > f, similarly, we must find the smallest non-negative k such, that t ≤ 2(m - 1) - (s - 1) + 2(m - 1)k. ans = 2(m - 1) - (s - 1) + 2(m - 1)k + (s - f).
We can find k in any reasonable manner, for example, by using formulas of integer division.

Suppose, that the first player made a move x ≤ a, then consider the remainder rem = x· 109%mod. Obviously, if (mod - rem)%mod ≤ b, then the second player can win. Thus, we must iterate through all relevant values of x (we don't need iterate through more than mod values) and check whether the second player to win. If there exist a losing move for second player, then won the first, else second. Since we iterate through all relevant moves of the first player, then we can easily determine his winning move (if such move exist).

Approval. If the tournament has at least one cycle, then there exist a cycle of length three.

A constructive proof. Find any cycle in the tournament by using any standard algorithm, such as depth-first search. If there is no cycle, then output -1, else choose any three consecutive vertices of the cycle v1 v2 v3 (Av1, v2 = Av2, v3 = 1). Since given graph is a tournament, then there is an edge (v3, v1), or there is an edge (v1, v3). The first of these two cases, we find immediately the cycle of length three of the vertices v1 v2 v3,  the second, we can reduce the length of the loop (erase vertex v2). 

We can reduce the length of the cycle until we find a cycle of length three.

Imagine a recursion tree our transformation F. This tree is binary. We write on the edges leading into the left subtree, zero, and on the edges, leading to the right, one. Now consider the path of some number a (hereafter, we assume that we substracted one from all numbers in the array over which we make the conversion). This path start in the root of the tree and end in some leaf, and numbers written on the edges of the path is exactly bit representation of a in order from least significant bit to the most significant bit.

Construct the recursive function which solve our problem, similar to how we carry out a query to the segment tree. Here is the prototype of this function.

solve(idx, tl, tr, l, r, u, v)

This function returns the answer to the query (l, r, u, v), if we consider only subtree with positions [tl, tr], while on the path from the root to the subtree is written bit representation of idx. If l ≤ tl ≤ tr ≤ r, then we calculate answer by formulae, else we divide our segment of positions and return sum of answers from left and right part.

As described above, the answer to the whole subtree is a formula. Here you need to use the fact that all the numbers in the subtree have the form k· 2depth + idx, where depth - depth of subtree. We must find k such, that u ≤ k· 2depth + idx ≤ v and then calculate the sum of  appropriate numbers.   

Asymptotics of this solution O(m· log(n)· (formulae - for - whole - subtree)). We can calculate formulae for whole subtree in O(logn).

In this problem, suggested a solution using heavy light decomposition. Graph, given in problem statement, is a cycle, on which are suspended trees. For each tree construct the data structure (heavy light + segment tree), which can perform change on the path from some vertex to any parent, and to maintain the amount of ones. The same structure we use for the cycle. 

Suppose, that we have no cycle, i.e. there is just a bunch of trees (forest). Then the amount of switched-on edges uniquely determines the number of connected components (each switched-on edge decrease the amount of components by one). 

Suppose, that we have only the cycle. Then, similarly, the amount of switched-on edges uniquely determines the number of connected components.

We will maintain the amount of switched-on edges in the cycle and in the all trees. So, the answer to the problem Compscicle + Compstrees - CntCicle, where Compscicle - the amount of connected components in cycle, Compstrees - the amount of connected components in all trees, CntCicle - the amount of vertexes in cycle.


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

13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Are you just translate your editorial (Russian version) into English Version by Google Translate?

All right, I saw your tags anyway :)

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please tell me, In problem B

rem = x· 109%mod

why  109 is used?? why its particularly 109?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Adding k zeroes at the end of number equals to multiplying it by 10k.
    → Reply
13 years ago, # |
  Vote: I like it +53 Vote: I do not like it
Another way to do problem E is to use link-cut trees, which I invented.  (They're described in this paper: http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf )  My code for this problem using link-cut trees is here: http://www.codeforces.com/contest/117/submission/842663  The link-cut trees are in the Node class, near the end of the file.

Not that it matters here, but link-cut trees give you a running time of O(n log n) instead of the O(n log^2 n) solution described here.  I also think they're rather elegant, if I do say so my self.

                   ---Danny Sleator
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it
    Oh, glad to see you here, it's really perfect solution. I've heard a lot about your trees, and about a lot of magical things they can do, but never tried to use them in practice.

    I think, I should try to solve this problem in this way, the truth, when I first tried to read this article, I found it quite difficult, I hope I will be able to overpower her at this time.

    With great respect, 
    Gerald Agapov
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it
      I've submitted a new version of my solution, this time with a better description of how it works.  http://www.codeforces.com/contest/117/submission/860934

      This, combined with looking at the code, should make it a lot easier to understand.

      ---Danny
      → Reply
      • 10 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        In the link operation, shouldn't we update the counts? Edit: it's done in expose.

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

        I am probably misunderstanding something, but in link, shouldn't one of q's children be made q? If this isn't the case, then how does one construct a link/cut tree to represent a whole tree (using your implementation)?

        → Reply
  • 13 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    A legend in this thread!

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone please explain the idea behind niyaznigmatul's solution to problem C? (http://mirror.codeforces.com/contest/117/submission/715444)

I think it boils down to proving this fact:

If there's an edge from i to j and out[j] >= out[i] then certainly there's a cycle i -> j -> k -> i for some node k (where out[u] is the number of outgoing edges from node u).

Any idea on how to prove this? I can't convince myself that his solution is correct.
→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another solution for problem C. let us consider the vertex with the biggest outcoming degree. if the degree is equal to n-1 we could ignore it ans solve the problem for remaining graph. otherwise we could name this vertex as a (( King )) of digraph. we know that every vertex could achieve from king with distance at most 2.so because of what we say before there is vertex like V that the edge between king and V is (( V -> king )). and we just need the path from king to V and we could find the middle vertex easily that we name it U. so the answer to the problem is (( king , U , V )).

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

Need help for Div 2 C. Getting the Wrong Answer for test case #34. According to my solution, I do dfs on vertexes and store their levels with respect to vertex 1(level 0). As soon as I add a vertex to stack I check whether the difference between its old level(only if that vertex had been visited before, else its level will be -1 by default) and new level (obtained by 1+current level of the top vertex of the stack)is equal to 3 or not. If it is, then I store current top vertex and the vertex whose difference in levels was 3. Now I only need to find the last vertex such that there is an edge from first to second and second to third and third to first.

My Solution

Can anyone explain why getting wrong answer or give a short test case?????

THANKS

→ Reply