MinakoKojima's blog

Codeforces Round #172 Editorial
By MinakoKojima, 12 years ago, In English

Overview ...

In DIV 1, there are 3 normal tasks accompanied with 2 challenge tasks. About 40 competitors solve first three tasks during the contest and I believe there will be more if we extended the duration a little bit.

Task D is a standard data-structure problem hidden behind a classical maximum cost flow model. This kind of problem are usually trick-less, but hard to implement especially under the pressure. Because of this, it becomes tonight's draw-breaker.

Task E is a extended version on a classical DP && Math problem. There are many solutions to the original problem, one is giving a global view under the state transition, and using a data structure to handle it carefully. However, this one is even more harder, few people have ever tried it except Jacob. (Although is wrong.)

As a seasoned competitor, Petr took the C-B-A order which proved to be the best choice through out the night. And after quickly solved C and B, he has sunk into problem A, it takes him about 45 minutes to cut-the-knot and got 2 Successful Hacking Attempt as a reward.

On the other hand, peter50216 gave his response to Problem A straightly! It only took him about 15 minutes to write a code which is full of trigonometric function and if-else. And on top of this is another 15 minutes to solve the successors. After that, he gave 2 Successful Hacking Attempt on A and 1 Successful Hacking Attempt on B as the end.

While we were marvelling at peter50216 for his solid skill in geometry, al13n gave the first attempt to problem D among the game. Unfortunately his solution get TLE on the pretests.

This is a O(mk^2logn) algorithm, and we think it is hard to optimize it to pass the pretests even for our setter. And abandoned the O(mk^2logn) solution and totally reconstructed the O(mklogn) from the sketch now became more difficult and audacious.

While we were praying to al13n, Jacob gave the first solution and the only solution for Problem E among the whole game! It cost all of his time and led him no time to solve others. It sounds like a miracle ..

We were all sooooooo excited and opened his code and look carefully, but, actually I myself got quite confused by his solution, and didn't know why it can work at all.

While all we setter and tester were checking the solution carefully. UESTC_Nocturne (XHXJ) gave the first correct solution among the game for problem D. It is a huge code more than 12kb, and perform as same as our std solution. Although he haven't solve A && B, this break-through has already establish his winner position.

After the contest, I interview her to "how can you solve this problem so quick", and replied as “I have solved the simplified problem, and have thought about this method before.”

At the same time, we found that Jacob's solution was wrong, we generated a few maximal random data, and it return WA about one-quarter of them. After some discussion we decided to add one of them into the tests.

In both problem D and E, our pretests intended to be as strong as possible. How I wish to let Jacob know about his solution is wrong so he can quickly get out of the impasses and get Accepted in the end... .

al13n also pass from the pretests after UESTC_Nocturne, we are relieved to hear about it at first, but found it is a O(mk^2logn) solution with a wrong optimization soon, this solution will definitely fail in system test, but he may didn't aware of it at the time.

There are other three correct solutions for Problem D near the end of the game, among them FattyPenguin's solution is the fastest one, and he make it in ten minutes ago before the contest end and liouzhou_101's solution actually is a O(mk^2logn) one but with some dramatic optimizations. It is hard to block this kind of solution or it could cause some trouble for our Java Users.

Tutorial ...

http://assets.codeforces.com/statements/280-281/Tutorial.pdf

Sidelights ...

  • There are some disputes about the problem A, but personally I like it very much, this is a basic problem(surely it is evil), can be described in one picture, and all of us could solve it if they are careful. Some people say it is harder than A so it should be swap with Problem C, but I insist on put it at A, because, we all think Problem B && C needs some idea, but A needs only basic knowledge we learned in middle school. And it can be solved in a different style if you have a well-implemented Geometry Template. Some competitors are just good at this kind of problem while others are not. And after all, this is the only problem which has trick in this contest. :)
  • In problem B, some people got confused in “bitwise excluding OR = XOR or OR?”, they are only familiar with "XOR" but get into confused with something like "bitwise excluding OR". Well, as a Non-English speaker, I can only expressed my understanding, we didn't intend to do that. In the original statement we write "XOR" but during the translate process it became "bitwise excluding OR", and I did not think it could cause such trouble. Here we can only recommend you read more English book, because such things will occur from now on and keep up.
  • tourist lost his target (Rating above 3000) after the contest. But we all think he'll return soon.
  • rng_58 didn't participate in the contest but took a virtual participation on the next day. He can't solve D && E and get Rank 5 along after Petr.
  • tclsm2012 as a purple, also solve Problem D during the contest, but failed at A && C at the expense.
  • Both the winner and the runner-up failed on problem A.
  • UESTC_Nocturne's A solution was hacked by scottai1, the latter, also failed at the system test after a while.
  • One of our setter ... came in the hospital after setting problems.
  • We were adding tests against submitted solutions during the contest.

  • Daniel Sleator (A professor at CMU who invented many data structures such as splay trees, link-cut trees, skew heap and discovered amortized analysis, see Wikipedia ...）participated in Div 2 and get promotion to Div 1 after the contest. And he checked our Div 1. E and write a miraculous DP solution1 2 in Ocaml which based on a conclusion.

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

Comments Comments (49)
| Write comment?
»
12 years ago, # |
← Rev. 5   Vote: I like it +14 Vote: I do not like it

The editorial for #172 is still under construction ... Fell free to give me suggestion~~. The link error has been fixed ... bu I need another dayto give it a perfect ending ... ...zzZzZZz zz ... ..-Mar 15th.

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

    In the tutorial of Div.1 C Game on tree, I think there should be "Here we denoted the Depth[root] = 1." .

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

By the way problem C is very similar to: http://www.codechef.com/ACMAMR12/problems/FSSYNC

which some (like me) may have solved recently.

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

Problem have an O(mklogn) algorithm?=.=~ I ac it in O(mk^2logn) at Practice..How lucky I am!

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

    You guy so lucky~ It got AC in 4700ms and we used to make TL 3000ms.

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

"As a seasoned competitor, Petr took the C-B-A order which proved to be the best choice through out the night. And after quickly solved C and B, he has sunk into problem A, it takes him about 45 minutes to cut-the-knot and got two Successful Hacking Attempt as a reward."

Seeing that it took Petr 45 minutes to solve A, I thought, he tried, D or E or both in between solving C and A.

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

"Some people say it is harder than A so it should be swap with Problem C, but I insist on put it at A, because, we all think Problem B && C needs some idea, but A needs only basic knowledge we learned in middle school."

Agreed with you. In fact C is too hard to me. I tried to solve but didn't get any idea. I wonder what is the right way to attack this problem? I tried to draw small small cases and tried to solve those, but still couldn't manage to find any solution.

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

    For each node, calculate the expectancy of movements to remove it. Then sum all those expectancies.

    Node 1 needs one move to be removed. No more, no less. Children of node 1 (depth 2) can be removed directly, or by removing node 1 (either 0 movements or 1 movement = 0.5 expectancy). Similarly, nodes at depth 3 can be removed directly or by removing one of its two ancestors (1/3 expectancy). In general, a node at depth D has an expectancy of 1/D.

    So the solution is to do a DFS from the root and sum all those expectancies you find along the way.

    The pseudo-code would look like the following...

    dfs(node n, depth d)
{
    exp = 1/d
    
    for(every child k of n)
        exp = exp + dfs(k, depth + 1)
        
    return exp
}

    So you just print the value returned by dfs(1).

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

      Thanks. Nice explanation.

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

      You are not computing the expectancy of movements to remove each node. You are computing the probability to choose each node during the game.

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

        No, because the total games when choosing a certain node 'n' aren't the same as the total games when choosing its parent or any other ancestor.

        If the total amount of possible games is G, and the amount of games when choosing node 'n' is f(n), then the probability to choose node 'n' during the game is f(n) / G.

        For example, consider this tree: 1->2->3.

        The expectancy of movements for the removal of node 3 is 1/3, but the probability of choosing node 3 during the game is 1/2, because there are 2 games that choose node 3 ((3,2) and (3,2,1)), and there's a total of 4 possibles games ((3,2,1), (3,1), (2,1) and (1)).

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

          In your example, the probability of choosing node 3 during the game is 1/3. Your argument is wrong because games ((3,2,1), (3,1), (2,1) and (1)) are not equiprobable.

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

            Of course they are equiprobable! If there are G games, then each of the games has a probability of 1/G of turning out. I don't understand what you mean that they aren't equiprobable.

            It's simple: There are 4 games, 2 of them use node '3', so the probability of CHOOSING node 3 is 1/2, not 1/3 like you say.

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

            Ahhhhh, sorry for my last post. Now I see what you mean that they aren't equiprobable...

            In the 1->2->3 tree, you have 33% of choosing each node in the first move. If you choose 1, the game is over. If you choose 2, you have only one move left, which is to choose node 1, so that's 33% more for node 1. If you choose node 3, you can either choose node 2 or 1 after that, each one of them with 33%/2 = 16,6% probability. And if you choose node 2 after 3, you have only one move left, which is to choose node 1, so that's the final 16,6% for node 1.

            The probabilities end up like this:

            Node 1: 33% + 33% + 16,6% + 16,6% = 100%

            Node 2: 33% + 16,6% = 50%

            Node 3: 33%

            So, after understanding you, let me put a different example. Consider a graph with 10 nodes, all of them children of node 1. In that graph, the expected amount of moves to remove nodes 2 to 10 is 1/2, but the probability of choosing them is 1/10.

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

              To my view, for each of such children u, the probability that u is chosen during the game is 1/2 and not 1/10. Please, could you say in other words what do you mean with "the expected amount of moves to remove node u"? It is important to be precise here. Otherwise, it will not be possible to understand each other.

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

                As I said earlier, for node 1, you need one move, no more no less, because you must choose it directly to remove it. For children of node 1, if you remove them by choosing node 1, then you don't add any extra moves, because you already count that move in node 1. If you choose them directly, there's one extra move, so the expectation is 1/2. Similarly, for a node of depth 3, if you remove it by choosing its father or its grandfather, you don't count any extra moves, because you already counted the move in its ancestor. The expectation is then 1/3.

                So, with that reasoning, a node of depth D has an expectation of 1/D moves. I don't know how to explain it better.

                And about what you say about the probability of choosing a certain node u, it's probably the same thing we're talking here.

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

why sevenkplus.com ..?

"Task D is a standard data-structure problem hidden behind a classical DP model."=> "Task D is a standard data-structure problem hidden behind a classical maximum cost flow model."

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

    Because It make us look like more professional.

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

      If codeforces.com last longer than sevenkplus.com --> when someone new tries to download: (╯°□°）╯︵ ┻━┻

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

      I think that hosting editorials at another site is bad, because your site will eventually stop working and we’ll lose this tutorial.

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

      Yes, sevenkplus.com is instable sometimes, and I'm afraid the link will be broken after three months. I am going to contact the administrator to host our pdf document locally after we complete it.

      Thanks for your advice... o(*~▽~*)ブ

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

So what does target mean?

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

Solution for E here: http://codeforces.net/blog/entry/6952

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

There MAY BE a little mistake in the tutorial of 1D by 7k+. The complexity of Query of correct sol. should be O(k log n). 7k+ writes O(k log k)...

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

    I have reported it to xiaodao this morning, and he said this night bugs would be fixed and tutorial would be finished.

    BTW,it's not written by 7k+ but roosephu — -

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

    Oops, a mistake...sad...I find it when posting the solution...

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

      when i saw O(klogk)..i think that heap for solving it= =.. Otl..

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

Very nice tutorial! But I have a problem. When I try to open some of the example codes in the tutorial (astep's Div2A for instance), I got "You are not allowed to view the contest" message and could not view the codes. Is there something wrong?

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

When I try to use this link: http://codeforces.net/contest/280/submission/3285760 from your pdf file, I get message: "You are not allowed to view the contest". Why ?

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

    Authors are administrators of the contest and usual users cannot see their submissions.

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

I liked the overview part very much , I wish it's found in every editorial. The editorial is very good , Thank you :)

→ Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +20 Vote: I do not like it

http://codeforces.net/contest/280/submission/3297237

Wow. !! . Another solution for our E .. !!.I wish every one could seen it !! I am so excited ...

Frankly speaking, it is a unfamiliar programming language for me so that I can only understand part of the code. (Ocaml) (Fortunately, It has some explanatory note on the top!! .. ).

But I thought it might be incorrect, and I am going to generating more data to inspect it carefully ....

BTW: the brush of Ocaml seems has some bug ... m(_ _)m

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

    If information on the profile is correct, that is Daniel Sleator, a known computer scientist. It would be very cool if that is the case :)

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

i read Mr.Daniel Sleator's solution to one question. which he did by Link-cut tree.. just awesome :)

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

One of the best editorials I've seen, thanks very much.

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

WOW ! What a nice tutorial it is !! Hats off to author <3

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

Can somebody please explain this solution for problem div2C/div1A Rectangle Puzzle.

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

In case someone's looking for C's intuition:

Basically, the total number of steps is the total number of vertices v we chose in the process. Lets color them blue. Now observe that each blue vertex adds exactly 1 extra move to the total number of steps.

We want to know with what probability (or number of steps) a vertex v becomes blue. This will be 1 * Prob(v is removed before any of its ancestors), i.e. 1 * (1 / depth[v]), because we chose v out of depth[v] possibilities to remove v.

Since our final answer is the total number of blue vertices, this equals sum of probabilities of each vertex being blue.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B can be solved with ternary search

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

    this is the first usage of std::function i saw that actually doesn't TLE

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

      it s lambda function works as the normal function

      → Reply