slycelote's blog

Codeforces Beta Round #23 tutorial
By slycelote, 14 years ago, translation, In English

A. You're given a string...


Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is O(L4) with a small multiplicative constant.

B. Party


It's clear that at least one person (the one with the least number of friends) will have to leave. We claim that at least two persons will leave. Indeed, suppose that only one person left, and he had d friends. Then all other people had more than d friends before he left, and after that they had less than d + 1 friends, i.e. not more than d. So, his leaving influenced the number of friends for every other person, which means that he was friends with everyone: d = N - 1. But he has fewer friends than everyone — a contradiction.

So, the answer is not more than N - 2. We'll prove that it's possible for N - 2 people to stay (of course, if N > 1). The graph of friendship will be the following: take a complete graph on N vertices and delete one edge. Then the degrees of two vertices equal N - 2, and other degrees equal N - 1. After the first two vertices are removed, we have a complete graph on N - 2 vertices, and all degrees equal N - 3, which means that no one else will leave.

C. Oranges and Apples


Sort the boxes in increasing number of oranges. Count the total number of apples in boxes with odd and even numbers. If the boxes with odd numbers contain at least half of all apples, choose them (there are exactly N boxes with odd numbers). If the boxes with even numbers contain at least half of all apples, take them and the last box (which contains the largest number of oranges). It's easy to see that in both cases the conditions of the task are fulfilled.

D. Tetragon


Let ABCD be the quadrangle that we're looking for, and K, L, and M be the middle points of equal sides AB, BC and CD, correspondingly. Let M' be the point symmetric to M with respect to L. Triangles BLM' and CLM are equal by two sides and angle, so BM' = CM = BL = BK, i. e. B is the circumcenter of the triangle KLM'.

Knowing B, we can reconstruct the whole quadrangle, using the symmetries with respect to the points K, L, and M, and then check whether it satisfies all conditions.
Note that we don't know which of the given points is L, so we need to check all 3 cases.

E. Tree


Lemma. In one of optimal solutions there are no simple paths of length 3.
Proof. We can remove the middle edge from such a path. The connected component will split into two components of sizes a and b, where a ≥ 2, b ≥ 2, and therefore ab ≥ a + b.

We'll root the tree and calculate recursively the numbers hv = the solution of the problem for the subtree with the root v, and fv = the product of hu for all children of v. If v is a leaf, then hv = fv = 1.

We show how to calculate hv, given the solution for all subtrees of v. Consider the connected component of v in an optimal solution. It follows from the lemma that the component has one of the following types:
1. The single vertex v.
2. The vertex v and several children of v.
3. The vertex v, one child of v — w, and several children of w.

In the first case the result of the game is fv.

In the second case it equals Πfi · Πhj · k = Π(fi / hi) · fv · k, where i iterates over children belonging to the connected component, j iterates over the rest children, and k is the size of the component. Since we want to maximize the result, we're interested in children with the largest value of fi / hi. Therefore, the largest possible result in this case equals the maximum value of Πi ≤ s  (fi / hi) · fv · (s + 1), where it's supposed that the children are sorted in descending order of fi / hi.

In the third case we can use a similar reasoning for every child w. The best result will be the maximum of the expression fv · (fw / hw) · Πi ≤ s (fi / hi) · (s + 2) as w iterates over children of v, and s iterates from 1 to the number of children of w; note that the children of w have already been sorted in the previous step.

Therefore, the number of operations necessary to calculate fv is proportional to the total number of children and grandchildren of v, which is less than n. The complexity of the algorithm, then, is O(n2) (ignoring operations with long numbers).
  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
thanks by the analysis, you have made an excellent work!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks!
    Hope that the lack of comments indicates that everything is clear rather than the opposite :)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Perfectly clear adamax, you save me a headache..
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I don't really get problem B... Is everyone considered friends with themselves or not? If so, then a complete graph will result in nobody leaving - everyone will have N friends. If not, then whatever the configuration, there will be no one with exactly N friends, so everyone will have to leave...

I would be very grateful if someone could clear this up to me...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    In a complete graph everyone will leave at the last step.

    > whatever the configuration, there will be no one with exactly N friends, so everyone will have to leave...

    When a person leaves, the number of friends for other people changes.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then how can we get someone to have N friends in the incomplete graph so that person remains in the end? As I understood it, the number of friends for other people will be strictly decreasing as time goes on, so if someone is to have N friends at some point, he must have had at least N friends previously... Either that or I really can't understand the problem...

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

      I think I should be able to understand it best if you could show me an example for a small N...

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        3 vertices, 2 edges:
        1--2--3

        At the first step no one gets eliminated, since there are no vertices of degree 0.
        At the second step the vertices of degree 1 get eliminated and only vertex 2 stays. Now 2 has degree 0.
        At the third step no one gets eliminated, since there are no vertices of degree 2.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Oh, I understand it now... My bad...

          Thank you for your time and patience.
          → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain why the editorial solution to problem C is correct? I've thought about it for a while and still cannot get why selecting all the odd ones, or all the even ones guarantees that it will be correct.

Thanks.

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

    Suppose 0 ≤ x1 ≤ x2 ≤ x2N - 1 are numbers of oranges. Sum the inequalities x1 ≥ 0, x3 ≥ x2, ..., x2N - 1 ≥ x2N - 2. We get x1 + x3 + ... + x2N - 1 ≥ x2 + x4 + ... + x2N - 2. It means that the left part of the inequality (boxes 1,3, …, 2N-1) contains at least half of all oranges.

    Similarly, sum the inequalities x2 ≥ x1, x4 ≥ x3, ..., x2N - 2 ≥ x2N - 3, x2N - 1 ≥ 0. We get x2 + x4 + ... x2N - 2 + x2N - 1 ≥ x1 + x3 + ... + x2N - 3. It means that the left part of the inequality (boxes 2,4, …, 2N-2, 2N-1) contains at least half of all oranges.

    Now the first subset 1,3, …, 2N-1 contains all odd boxes, and the second one 2,4, …, 2N-2, 2N-1 contains all even boxes. It means that one of them contains at least half of all apples and we may choose it to solve the task.

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

      I am not able to get the logic as why should either of the first subset 1,3,...,2N-1 or second one 2,4,2N-2,2N-1 should contain atleast half of the apples.

      Can you please explain ?

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

        If the sum of two numbers is greater than or equal to s, then at least one of them is greater than or equal to .

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

i do not understand the explanation for problem E. please can any one give an easier explanation.

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

For problem E, an O(n) greedy algorithm is possible (ignoring big numbers). See my code for detail 25487437.

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

    could you explain more ?

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

      Yes. After DFS in a subtree completes, the solution will already make optimal cut in the subtree, and returns a reduced shape that still matter in later decision. Such shape is identified by a integer:

        0:  []          leaf
  1:  [[]]        two-chain
  2:  [[][]]      1-fork-2
  3:  [[][][]]    1-fork-3
  k:  [[]...[]]   1-fork-k
  -1: [[[]]]      three-chain
  -2: [[[][]]]    1-1-fork-2
  -3: [[[][][]]]  1-1-fork-3
  -k: [[[]...[]]] 1-1-fork-k

      When recursion on all children finished, we keep track of all case numbers for children.

      c0: number of 0s (leaves).
cp: list of all positive cases (1-fork-k).
cn: list of all negative cases (1-1-fork-k).

      It won't be hard to prove that you can make globally optimal edge-cut decision by just looking at c0, cp, cn, and reduce the subtree into one equivalent case number to return.

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

        what do you mean by [[]] '[' show what ?

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

          each '[' and ']' pair is a node. child nodes are inside parent nodes.

          [[]] means a two-chain.
[[[]]] means a three chain.
[[][]] means a parent with two children.
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            alright ; but why this greedy algorithm works ; i mean why the best possible answer depends on the best answer of its child's ; consider now you are on vertex v and u is child of v ; maybe the best answer of u returns 1-1-fork-k ; but in the best answer of vertex v we have to use u as a leaf ;

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

              That's why u-1-fork-k is one of the reduced cases.

              When parent v finishes DFS and reduce its subtree, it can cut (1-fork-k) off, and return a two chain (v-u).

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

              And the already cut part will contribute to answer immediately.

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

In one of optimal solutions there are no simple paths of length 3 ..

what it mean ?

can anyone please explain me 2nd and 3rd case formula ?

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

    A simple path is a path in a graph which does not have repeating vertices

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

"Then all other people had more than d friends before he left, and after that they had less than d + 1 friends, i.e. not more than d."

Why couldnt they have had d+3 friends say before and consequently d+2 afterwards?

→ Reply