gen's blog

Codeforces Round #200
By gen, 11 years ago, translation, In English

Hello everyone!

The anniversary Codeforces Round #200 is scheduled to take place today at 7:30 PM Moscow time. The round will be held in both divisions and will be rated.

The round problems were prepared by Evgeny Vihrov (gen), Andrey Vihrov (andreyv) and Gerald Agapov (Gerald). As always, we would like to thank Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems, and also Maria Belova (Delinur) for translating the problem statements.

In this round you will help mad scientist Mike to realise his peculiar ideas and carry out unusual experiments. The authors think that the problems constitute a good balance between mathematics and programming. We also tried to make the statements short and easy to read :] As always, we hope that every participant will find a problem to his taste.

We wish you good luck and an interesting round!

UPD1: Score distribution is standard:

DivI: 500 1000 1500 2000 2500

DivII: 500 1000 1500 2000 2500

UPD2: Congratulations to the top 5 winners in each division!

DivI

DivI

  1. tourist
  2. KADR
  3. SillyHook06
  4. niyaznigmatul
  5. Igor_Kudryashov

DivII

  1. Giraffy
  2. jzc
  3. ryad0m
  4. Kamilot
  5. API
  • Vote: I like it
  • +204
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I love that balance between mathematics and programming!

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

In round #100, the top 100 participants were awarded t-shirts. How nice if top 200 will be awarded in #200 and so on :-) Seriously, what will be the next round which awards the top X participants? Haha~

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

    Top 200 will be awarded in CF #200 and so on ? So after next few years Mike have to buy more than 1000 T-shirts :) What about your sons in the future when they start to compete :) I think Mike need to Open a T-shirts factory for next generation :)

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

There wasn't any surprise for this round! I was waiting a long long time for this day and CF #200! :)

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

It will be better if there are extra T-shirts for coders which behaved excellently in CF Round #200!

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +17 Vote: I do not like it

Time flies! Codeforces #100 is my first round, and now it comes to #200 rapidly.
It gives a lot of fun, hope it to be better and better.
(of course it's already terrific now, except the network speed some times... )

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

I like your handle gen! MCZ Xian, a Gen user in Street Fighter 4, won EVO this year. EVO is the biggest fighting game tournament in the world. Did anyone watch it too on stream ?

Sorry for being off topic :p

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

What about awarding all participants with +/- 20% of rating. If their rating is going to increase, increase it 20% more and if it is to be decreased, decrease it 20% less :-D

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

    Rating changes are irregular in a way — even if you get the same place, the rating change depends on the others who compete (your 'relative place'). So that'd be hardly noticeable.

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

Which Mike is he? :D

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

So which is the score distribution? :-"

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

and score distribution ??

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

Nice problem set linking science with coding :) !!

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

cf was unavailable for long time. time should be increased.

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

my code in mingw32 output correct answer but here ,cf said wrong answer!!!:| why?

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

    different compiler may result in a slightly different result. Or may also happen when u compile using windows or linux. maybe u should post your code so we could check what is wrong with it?

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

score distribution was so wrong

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

One of the best contests I ever participated on CF. Less to code more to think :)

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

I loved the round and absolutely loved the problem statements and setting 5/5

How could I approach problem C efficiently?

I only managed to deduce a formula for some special cases... If anyone could give me some tips that would be great :)

Thanks,

Bruno

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

    f(a,b) = a/b + f(b, a%b);

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

      But this might fail according to this

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

        Good catch. (fortunately it passed according to given scenario)

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

        The question permits only a.)one resistor; b.)an element and one resistor plugged in sequence; c.)an element and one resistor plugged in parallel.

        so u only can add one resistor at a time to the existing element. (u cannot add two elements)

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

    solve (a, b) = (b / a) + solve (min(a, b % a), max (a, b % a))

    and solve (0, a) = 0;

    Explanation: you assume that b >= a, then you will take (b / a) resistors for taking in series with other resistors, so cost (b /a) for those resistors.

    For remaining you need to use 1 and x in parrallel which is a / b = x / (x + 1). which means x = a / (b — a).

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

In Div1, problem A, in my room, I saw two people use %lld to read or write 64-bit integers in c++, so I hack one of them, but unsucessful. Does it mean is using %lld to read or write 64-bit integers is no longer banned? Maybe next time, the warning "Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier." can be removed.

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

    %lld was never banned. It is just recommended to use %I64d due to historical reasons. With modern MinGW %lld seems to work as well.

    The warning cannot be removed as some people could be using old compilers on their own Windows computers, and then wonder why %lld does not work locally.

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

    I think that means "there exists at least one number when %lld will read not exactly the same as %I64d will under some compiler" rather than "it will always read wrong". So maybe you just didn't guess with hack :)

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

E can be solved by using Gomory-Hu algorithm. It takes the graph and in O(n * flow time) computes a tree such that maxflow from a to b is the minimum weight of an edge on a path from a to b (at first glance one can be amazed that such a tree exists but after some thought it makes sense). So we just have a tree and have to find a permutation that maximizes sum of the lightest edges on paths v_i -> v_{i+1} Answer to this problem is sum of weights of edges in such a tree. Just take the heaviest edge and use divide and conquer algorithm.

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

Nice problemset!

Especially for problem E, the solution is quite simple (maxflow-mincut theorem) but it's hard to think in that way. :)

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

    Thanks; the intended solution was to use Gomory-Hu tree, as Swistakk explained earlier.

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

      I see. That tree can be easily obtained by analyze it in this way:

      Suppose X-Y is a minimal cut of graph G. Then:

      • If x \in X and y \in Y then flow(x, y) = cut(X, Y)
      • Otherwise, it will be no less than cut(X, Y), we focus on nodes only in X and only in Y, so we split S into X and Y.

      Then we focus on X and Y and do the same thing.

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

        Exactly. That's how Gomory-Hu works :). But it's not straightforward to prove that these bounds are really the best ones.

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

          Frankly saying, sometimes I really don't understand people's reasoning regarding to rating comments. I described solution to E and gen replied "Intended solution was as Swistakk explained" and got more pluses than me and few posts below cgy4ever explained Gomory-Hu algorithm and I said "yes, that's how Gomory-Hu works" and I got more pluses than him :P.

          EDIT: Note that ratings I am reffering to may vary. When I was writing this comment cgy4ever's comment got +5 and mine response got +8, but now he has got +16 and I still got +8 :D.

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

            It's even weirder when there are 2 comments below each other, both saying something along the lines of "good luck", one of them is rated around -50 and the other around +50. The only reasonable explanation is heavy trolling of some comments.

            As for me, I usually vote minus on "spam" comments (those that only contain one of the usual phrases related to contests etc.), plus on comments that contribute something to me or are well written (that, of course, requires the comment to talk about something useful, meaningful) and for comments that are just random short replies or I'm unsure of how to vote, I don't vote at all.

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

              Last Wednesday i took 10 random new neutral comments with 0 votes each, upvoted random 5 of them and downvoted other 5. In 12 hours first 5 had +2, +11, +5, +4, +8, and second 5 had -9, -5, -8, -3, -4 respectively. Funny, isn't it?

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

                Yeah, that's one type of trolling. Just voting the more common option. Voting randomly is another common type. (In general, trolling is anything that isn't based at all on your view of the content.)

                Not like we can affect it, anyway. And when one has large contribution, it starts only depending on blogs — comments have much lower weight, so unless you're getting like +50 or -50 for one comment, it doesn't affect contribution at all...

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

Rating update was quite fast! :)

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

Can anyone tell me why this code fails on time limit ? (Div.1 Problem C)

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

We want T-shirts : )

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

    I wanted them too... ;(

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

Any hints for Problem D div2 ?

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

    My solution is prolly the easiest, though longer than optimal, to understand. I use linked list and remove ++s and --s http://codeforces.net/contest/344/submission/4465292

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

      You can just use a stack and assign digits for + and -. Let's say '+' is 1 and 0 is '-' . Then you can do the following:

      If current character's code(0 or 1) is the same as the stack's top, then pop, otherwise push the code in the stack. Then, if the stack is empty the answer is "Yes", and if it is not, the answer is "No". Here is my solution 4464633

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

i realy like div1 problem D , i think range assign with segment tree is not intended solution , is it?

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

    It is actually, the core of the solution is to color some whole original tree subtrees in logarithmic time.

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

      Time limit is 4 seconds , so i think that , intended solution is heavy — light decomposition.

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

        Nop, time limit 4 was set for Java solutions.

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

The contest was very specific! It was about any kind of science: Chemistry, Physics, Math, ... . gen was right. It had questions for any tastes. :D

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

Is 21/10 a valid test case for Problem-C (Div.2).....?

acc. to me (7) and (3) in parallel results in (21/10) which equals to 10 resistors minimum. But acc. to AC soln's. ans = 12.

Pls clarify!!!!!!

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

    You cannot combine 7 and 3 in parallel. According to the question, you can combine an element with just one 1 ohm resistor. Hence, combination of two elements in parallel in not permitted.

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

      Thanks for the clarification ...

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

    And 6/5 is also a wrong case. We can use (2) and (3) to get it: 1 / (1/2) + (1/3) = 6/5. So the answer should be 5, not 6.

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

      You should read the statements more carefully.

      There are only two types of combination:

      1) x -> x + 1

      2) x — > 1/(1/x+1/1)

      There is no x,y -> 1/(1/x+1/y)

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

What a great contest, I really enjoyed it...

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

I tried to hack this solution on test case "++++" because of the intermediate state (s[2] == s[-1]), but no runtime error, why?

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

    Well, since it's not Pascal with its range checking for everything, he just access whatever byte is before the char array. It is most likely accessible to the program (hence no segmentation fault) and since we have no idea what's in there, it can only possibly affect the code if there is '-' or '+', meaning that in at least 127 out of 128 cases it will run just fine.

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

      thanks..i think i should ask this question to cpp compiler :P

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

What I liked about this round was that the problems were more connected to the real world than usually. Solving them almost felt like doing some actual work:) Way to go, gen!

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

I became red and feel very happy!!! And first I solved 4 problems. Div1 D was very very cool problem! (I could answer the different types of queries by using the same euler-tour array!!) That should be one of my most favorite problems!! Thanks for writer.

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

Where can we get an Editorial for this round?

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

    Don't worry guys, we will complete it by evening.

    Done, enjoy. ;)

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

I think no one wrote about the solution of Div1 D, so I write it.

third query can be said, "which was the last operation, adding water to the ancestors of the node, or emitting water from the children of the node?".

So we want to calculate two values -- the time of last operation no.1 which added water to the ancestors of the node, and the time of last operation no.2 which emitted water from the children of the node.

Both queries can be done with the different segment trees to the array of Euler-tour.

So we can solve this problem in O(Qlog N).

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

    not O(Qlog N) , O(Qlog NlogN)

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

      This can be solved in O(Q log N), but I know another solution whose order is O(Q log^2 N). (Actually I found this at first, but I thought it is too slow to get accepted and too hard to code, so I tried to find another solution.)

      In this solution, we can use heavy-light decomposition or the general technique of merge the data structures like std::set.

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

The problems were interesting! I liked them!

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

Hello,

Anyone has any tips about Problem E for Div. 2?

I am totally clueless about it and still trying to grasp logic of problems C and D...

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

    Hint for problem E Div. 2 (Read Time):

    Try binary search the answer. For particular time T you have to determine if it is possible to read all tracks (p1..pm) in time T.

    Another hint:

    • There exists an optimal solution where heads don't change their relative order.
    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What a nice tag for the blog post :) "everybody reads tags" Thanks for the laugh!

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

I think there is an issue with Problem 343A — Rational Resistance. Here according to the editorial the answer to the ratio 6/5 would be 6(I have verified this with an accepted solution). But this ratio can be achieved with a resistance of 2 and 3 in parallel, which makes the number of resistors required equal to 5 which would imply the editorial and the system tests to be wrong.

Am I missing something here?

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

    you cannot put resistance of 2 and 3 in parallel.

    According to the problem statement you can only put Ro and Re in parallel where Ro = 1.

    → Reply