meret's blog

Codeforces Round #134
By meret, 12 years ago, In English

Welcome to Codeforces Round #134!

After over two years, it is again my great pleasure to be the main problemsetter of a contest on Codeforces. Thanks a lot to Gerald for helping me organize the round. I hope you will enjoy solving the problems as much as we enjoyed preparing them for you.

Dynamic scoring will be used, but the problems will be ordered by their expected difficulty, from easiest to hardest. Are our predictions correct? I am eager to see. :-)

Good luck!

Update: The contest is over! Here are the results:

First division:

  1. rng_58

  2. panyuchao

    pieguy

  3. tourist

  4. Petr

  5. ACRush

  6. Zhukov_Dmitry

All contestants from the top seven solved three problems. Note that there was a tie for second place. :-)

Second division

  1. dsbuaa

  2. hqztrue

  3. Gullesnuffs

In second division, seventeen contestants solved four problems. Nobody managed to crack E; it was also present in the first division as problem C, and proved tricky even for the experienced competitors.

Congratulations to the winners!

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

Comments Comments (80)
| Write comment?
»
12 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Анонс как-то слишком заранее сделан... Давно такого не было.

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

    А CFR129 давно был? И в нем анонс еще раньше сделан.

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

    Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).

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

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

      Can someone translate this for me please? I feel left out!

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

        ...But when i do "you don't know what i am saying"

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

Thanks for your hardwork,and I must say that I love the sentence "but the problems will be ordered by their expected difficulty, from easiest to hardest" most.Hope to solve as much as I can.

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

Registration duration is diffirence,only 9 hour and 30 minutes, will be start 01:00AM,will be end 10:30AM

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

    Why have negative votes,He is true.

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

      As mentioned before. One does not simply try to understand negative votes on codeforces.

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

And the score distribution is… :-?

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

Good luck, everybody!

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

I'm so happy, that round start 5mins after full hour :D

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

Объясните, пожалуйста, D div 2) Больше часа на ней просидел( Explain , plz , D div 2)

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

    translate from google: Explain, please, D div 2) more than an hour spent on it (

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

    Hint: use Euclidean algorithm.

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

    Think backwards: if a>b then (a, b) -> (a, b-a)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      eg.
6 10
solve
10 test 1 to 9
when test 8 must be below:
10 8
2 8
2 6
2 4
2 2
assert not this.
when test 7 must be below:
10 7
3 7
3 4
3 1
2 1
1 1
here have two possible, choice best one
      → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Great contest! All tasks were very interesting, even A(Div 2)!

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

Сорри, поспешил.

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

Problem B is fine. Solution is easy but I could not guess it during the contest...

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

Nice problem-set but two 500 pointers in div 2, and no 1500 or 2000 pointers in between 1000 and 3000 seemed odd.(Though it happened due to dynamic scoring)

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

It's a nice contest!Well done problemsetter meret!

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

How soon will the rating be refreshed?

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

Nice problems.I'm looking forward to tutorial because nobody solved all problems.

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

Nice problem C div 2. I was studying Graph Theory some hours ago and I got AC in this problem with a DFS.

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

    I use UFS in this problem.I think this problem is very flexible,and there's more than one way to solve it.

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

      What is UFS, I never heard this algorithm, by the way I solved this problem with Union-Find Set.

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

        Union-Find Set.A useful data structure.

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

    shater -_-

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

    UFS is a better choice.

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

Problem E is so Hard..

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

is there any other way (other than graph theory) to solve the problem C(div 2)?if yes,can anyone provide a hint..

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

[user:meret]will someone write the editorial???

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

In Problem B Div.1 (Blackboard Fibonacci), I try to run the large test case (999997 999997) in www.Ideone.com and my laptop then I got runtime Error. But when i submit it to Codeforces system, it accepted :-o (Although the final test has the same test case :-o)

My submission:

Can anyone tell me why?

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

    Maybe problem is in stack size, because you use recursion.

    Here, on CodeForces, stacksize is increased for g++ using compilation string

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

      Thank you!

      Upd: Another Online Judge don't increase stacksize :-(, so my solution can't get AC in some problems. Is it possible to increase stacksize in C++ source code :-(.

      As far as I know #pragma comment(linker, “/STACK: 268435456”) works only in MS Visual C++.

      How about G++ compiler ?

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

        AFAIK, there no way to do in G++, but you can write your problem not recoursively(or use MSVC++, of course)

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

I don't know if DIV I — C was so hard or DIV I — B was hard enough that people spent a lot of time in that problem and didn't have enough time for problem C.

BTW... My solution for DIV I — B was hacked during the contest and I couldn't fix it... The test case? 1 1... I hardcoded it as

T

instead of

0 T

EDIT: Fixing that case passed system test after contest was over.

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

Thanks for holding a match at a different time than usual. I enjoy Codeforces contests but have a hard time competing at the usual time. I enjoyed these problems and hope I don't have to wait so long before my next contest.

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

    To the opposite, it was really hard for me to compete here, in Russia, because of that awful Saturday morning:( I wish next time morning-contests would be held one or two hours later — just to have a good sleep... please!:-)

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

      Oh, common, 11am is not a problem, SRM at 5am is :)

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

      Please think about other countries.For example,the usual contest time(7:30PM Moscow Time) is 11:30PM in China.So I think we should have more contests at times like this one.

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

        Ok, so why not to have contests always at different time?

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

Could anyone tell me how to solve Problem E of Div1?Thanks.

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

Could anyone tell me how to solve Problem C of Div1 (Problem E of Div2)? I have seen some codes but I still can't understand them. Who can give me some hints or useful conclusions to solve this problem? Thanks very very much!

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

    It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {c1, ..., cn}.

    Replace each '?' by either ci or cj, i and j being arbitrary for now. Look at the values in the four cases (ci, cj) = (0, 0), (0, 1), (1, 0) or (1, 1).

    For example, for (ci&(ci&cj)) we would get 0, 0, 0, 1. Note that there's only one way to get 1.

    • If a "3 versus 1" or "1 versus 3" can happen, then choose the right i and j, and the answer will be "YES".
    • If a "2 versus 2" of the form 0, 0, 1, 1 or 0, 1, 0, 1 or 1, 1, 0, 0, or 1, 0, 1, 0 can happen, you can deduce ci or cj, the answer will be "YES".
    • If none of those situations happen, the answer will be "NO".
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thank you very much.Supose that F(ci,cj) is the result of permulation,what is the inital value of F(0,0) F(0,1) F(1,0) F(1,1)? Thank you.

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

        You can compute the values taken in the four cases recursively. Look at this submission for a better idea: 2032900

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

      Could any one can explain why "not all colonies are of the same type" is so important ? ..

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

      Could anyone provide some tricky test cases for Div1-C? I am failing case 13 and its huge :/ (all the tests after 13 are huge too..) Thank you.

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

why the editorial is not uploaded yet ?

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

It looks weird to have 7 people in top 6 when the "6th" place is non-tied. If there is a 2-way tie at place n, I believe the standard way is to denote the next place (n+2), not (n+1).

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

    This is how I did it in the code of the message, for some reason the system replaces it with the enumeration that you see.

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

No editorial yet ... :/

→ Reply