cgy4ever's blog

Codeforces Round #228
By cgy4ever, 11 years ago, In English

Hello everyone!

Codeforces Round #228 (Div. 1 and Div.2) will start at Monday, 3 February 2014, 19:30:00 MSK.

This is my 2nd round on Codeforces. (Click here to see my last round) , As usual, there will be 7 problems: 2 for Div2, 2 for Div1 and 3 for both. And same with the last round, the main character of all problem will be Fox Ciel.

I would like to thank Gerald for testing, and MikeMirzayanov for the Codeforces project including polygon system.

Good luck and have fun!

The score distribution will be published later. And the editorial will be published right after the system test.

By the way, yesterday is the Chinese new year. So I'd like to say Happy New Year to everyone who celebrate it! And I'm very glad to be the writer of the first round in the new year.

Update1: Good news for participants of Petrozavodsk training camp. Top 20 participants of the camp by this round results will get t-shirts from Codeforces.

Update 2: The score distribution for Both Division is regular (500-1000-1500-2000-2500).

Update 3: We postpone the round 10 minutes by technical reasons (dinner on Petrozavodsk Training Camp), sorry for the inconvenience.

Update 4: We've increased the contest time by 5 minutes.

Update 5: Contest ended, thanks for your participating! I'll post the editorial soon.

Update 6: Editorial.

Winners:

DIV1:

  1. tourist
  2. PavelKunyavskiy
  3. Egor
  4. 2222
  5. dreamoon_love_AA

Sadly no one solved E correctly. Egor's solution can pass if the TL is 7 seconds instead of 6, what a pity!

DIV2:

  1. I_love_Hoang_Yen
  2. iaacboy
  3. GoldExperience
  4. shivatejesh
  5. lordpawel

They are the only people who solved all tasks!

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

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

Wow, a new contest. Thanks for preparing problems and I think I will love this contest:) PS: Orz

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

Hm.. there's also a TopCoder SRM earlier on Monday. I wonder if I will be able to participate in both TC and CF :)

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

Your last contest had nice problems.

Thank you for creating another contest.

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

I'm definitely looking forward to the 1st contest in the Chinese new year! 新年快乐！

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

thx

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

Problem description was nice (and short too) of your last contest ...

Hope it here also ... :)

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

Your previous contest's problems were awesome, looking forward!..

→ Reply
»
11 years ago, # |
← Rev. 13   Vote: I like it -19 Vote: I do not like it

We HoPe gEt NeW RaTinG PoiNt aFTer tHiS CoNteST :) .GOOD LUCK eVerYoNe and thanks for this contest cgy4ever MikeMirzayanov Gerald ! (HaPPy NeW YeaR Chinese PeoPLe ;) )

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

    What is wrong with ur SHIFT key :)

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

      No, I don't have any problem.i just wanted to make it interesting...

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

    i think that he just wanted to make it appealing..

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

      Actucally, to me, it' s a little bit hard to read. (Yes, just to me) Well I don' t learn English very well...

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

        THIS IS SPECIAL FOR YOU LiuRunkY.We Hope get new rating point after this contest :) .Good luck everyone and thanks for this contest cgy4ever MikeMirzayanov Gerald ! (Happy new year Chinese peopLe ;) )

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

          Sorry, I apologize for my behaviours before. ThAnKs FoR YoUr FoRgIvEnEsS! Wish you a good luck today.

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

Good luck everyone~ This must be a good contest! :)

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

Мне кажется или все пытаются набрать как можно больше "Вклада".

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

GL for every one

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

two contest in a day!
hard but fun! :D

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

Lack of div1 rounds didn't let div1 users refuse this contest!
1127 registrants for division 1!
Thanks for making this round a both division round ;-)

EDIT: 1144 after extra 10 mins!

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

Don't worry, the round delayed because of dinner on Petrozavodsk Training Camp :)

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

Funny. MikeMirzayanov says that the round is delayed because of dinner at Petr. Training Camp, and in the official post of the round, because of "technical reason". Or is the dinner the actual technical reason?

EDIT: already included above.

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

    Petr. Training Camp sounds great =)

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

      It certainly does :D I would like to have an uppercase dot character for avoiding such things )))

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

Wow! Is dinner a technical reason? :)

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

    actually dinner is an important reason! :)

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

I want to rating under color of my eyes... (red) =D

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

sta-le-ar in gat mancarea

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

'technical'reason == dinner LOL :D

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

Extra time for "Codeforces Unavailable"?

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

Sorry for unstable work. It was a real stress test for server!

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

most of the solutions in problem B will fail, also my solution :( for k=10^9 n=1017

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

    n is not a paramter I guess

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

    Do 10^9 exist as an input in final test cases?

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

    Mine doesn't fail for 10^9 but for 999997439. (N comes out to be 1017 :))

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

      And for testcase 268435455 your solution will output graph with 1137 vertexes.

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

Great contest..Really enjoyed it Thanks alot

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


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

good contest, good problems

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

When will the ratings be updated? UPD : Updated :D

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

Excuse me, I had an idea about the Div1 B/Div2 D. 1. If we add edges like this 1-3 1-4 2-3 2-4, then we' ll have 2 shortest paths, and 1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7 so that there' ll be4(2*2) paths, 8(2*2*2) paths with only 10 vertices... It seems that it' s easy to construct a graph with 2^n shortest paths. 2. If we devide the number k into a set of numbers which sum is k, and all the numbers must be 2^i( 0<=i<=32), then we can constuct a graph with paths I mentioned before. It is obvious that n won't be very large. Actually the problem can be solved correctly with this idea, but I' m so stupid that can' t work out

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

    your idea is correct,but you have mistake in your implementation also you are using more than 1000 nodes in the graph when binary representation of k contains more than 22 one

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

      Actually this idea uses much less than 1000 nodes, the powers of 2 that sum to 10^9 is the number of ones in the binary representation of k, and each power requires 2*i nodes which is a maximum of 2*32, so the total number of nodes is less than 2 + 32*2*32 << 1000. The problem is that dividing the paths into powers of 2 will have paths that are shorter than other paths requiring extra "dummy" vertices to equalize the paths.

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

        2 + 32*2*32 > 1000

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

          and since each 2^i will have a unique "i" , the sum of "i"s will be (n)*(n-1)/2 ... and 10^9 is < 2^30... sorry, i overestimated

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

      what is the easy solution in this way,please someone post how reduce nodes?

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

        I decomposed k into 33 radix, max nodes count becomes approx 800.

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

      Ohhh, yes. Thanks, I found my mistake. There will be about 1500 vertices when k is big enough...

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

    1-3 1-4 3-5 4-5 5-6 5-7 2-6 2-7

    How does this graph have 4(2*2) paths? I see only 2*2 paths.

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

thanks cgy4ever, you're the best :D

two excellent rounds, I'm looking forward to your third one :)

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

I got different outputs with same code, just one line difference at codeforces.

I get perfect output at my pc. Can anyone please explain why this happening? Got WA at problem B(div. 1), and get this problem by reducing lines of my code.

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

    I don't know why this happens, but may be it will be a useful fact that this code:

    #include <iostream>
#include <cmath>
using namespace std;

int main(){
    int k,len;
    cin >> k;
    k = 1000000;
    len = (int)pow(1.*k,0.2);
    k -= (int)pow(1.*len,5.);
    cout << k;
    return 0;
}

    gives same results whether "k = 1000000;" commented or not.

    Then, we can see that result depends on this: 

    k -= (int)pow(1.*len,5.);

    If we don't use type conversion, we'll get different results, if use — the same anyway. But why? :)

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

      yes. Thanks. :)

      But beyond type conversion, my code is only depend on whether k = 1000000 is commented or not. But, WHY???

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

        Finally, I think, the reason is that len*len*len*len*len != pow(len,5.));

        You can check it easily by cout << ((1.*len*len*len*len*len)==pow(len,5.));

        Another question is why they're not equal. And how it depends on way of assining 1000000 to k.

        Oh, of course, this stuff happens only wiht GNU. MSVS works well with all these cases.

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

          My g++ version is 4.6.3 and two version of my code outputs correctly. Ideone runs g++ 4.8.1 which also outputs 240625. you can check it here

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

    MikeMirzayanov, With due respect, will you check it, please??

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

      pow function returns double type result, (not int), so that the floating-point error could be happened. This behavior happened because of you, not server.

      You can reduce the error by using int(pow(len,5.)+0.5) instead of pow(len,5.).

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

        Once I change //k = 1000000 this line, server is calculating in another way? HOW? How pow(len, 5) produce different result on same server when k is injected value manually?

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

          Pow arguments will be automatically casted into double, so there is no difference between int arguments or floating-point number arguments.

          If len is enough small, Pow(len,5) can still return wrong result. Why? Example, len=10. Your expectation is 100000, but the function could return 99999.99999. Because you wrote: int(pow(len,5)), 99999,9999 will be casted and became 99999.

          I don't know how statement k=1000000 affected to pow function. Your problem is not in this statement, you need to use more safe power function. Built-in pow function doesn't work too fast, and if arguments are enough large, errors will be caused surely.

          If you still want to use pow and other function returning floating-point result, when you cast, you must write something like this: n = int(f(x)+0.5).

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

    "Problems with floating point numbers — the most often reported non-bug". GCC usually use wider floating-point types to compute expressions that can be computed at compile-time, which is permitted by C++ standard.

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

Great contest for me... there were short description to make me known quickly what actually problem wanted...

And the translation was awesome.... easy to understand...

I'm really waiting for your next contest... :)

Great ... Hats off ... :) cgy4ever

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

cgy4ever if possible prepare contest regularly , you are totally awesome . All problem setters should learn from you how to make an interesting round :D

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

So stupid mistake in problem div2 B. I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.I'll never submit code without some own tests.

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

    A better phrase:

    I will never submit a code without some own tests as long as my programming intuition is not on its heights.

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



Other stuff

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

I'm sorry, but I can't find what is wrong with my code for Problem C Div1 Submission:5886576 I'm trying to find the card with maximum number one can take ( in each step ) Is there something wrong in my implementation or....?

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

    Greedy doesn't work in this problem here is test that you will fail 


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

How comes the Dp relation in Div2 Problem D that dp[v] = sum{dp[t] | dist(1,t) = dist(1,v) — 1}? I am not able to get it. Could someone please explain?

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

    If we have dk - 1[v] which contains the count of the shortest paths with length k - 1 from some s vertex to another vertex then it is easy to get the count of the shortest paths with length k.

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

I think that test 7 in the problem B is wrong. Can anybody explain me?

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

Awesome round! I was Candidate Master before but now I am Master. At a point I was on the 7th place with A and C, and that felt really great. However, I couldn't maintain that wonder, but still, great problems and great round!

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

Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together here!

→ Reply