natalia's blog

Codeforces Round #100
By natalia, 13 years ago, translation, In English

Hello everybody!

I hope you have finished New Year celebrations, or you are ready to make a small break to take part in the anniversary Codeforces Round #100. Round will have place January 4 at 15:00 (UTC). There will be a common contest for participants of the both divisions with the same set of 6 problems. The top 100 participants of the contest receive prize t-shirts.

Score distribution: 500-1000-1500-2000-2500-3000 

As you may have guessed, the author of the problems is me. Invaluable help in preparation (and a bit in inventing) of problems was provided by Artem Rakhov (RAD) and in translation of the problem statements into English by Maria Belova  (Delinur).

Under the influence of my festive mood, the problem statements turned out to be about different characters celebrating New Year. All characters and events are fictional, please take any resemblance as completely coincidental :) 

The contest is over. Codeforces team and I personally want to thank all who take part in the greatest round in Codeforces history! Much to our surprise, the 100th place was shared by two contestants: pooya_ and Timur_Sitdikov. Of course, they both will receive prize t-shirts as all others who took higher places. Prizewinners will receive special emails.

Congratulations to the winners:

1. Egor
4. Petr
6. e-maxx
9. Coder

Announcement of Codeforces Round 100
  • Vote: I like it
  • +314
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Will Div1 and Div2 coders be mixed in the same rooms?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    Yes, it will be like "Testing Round #4" (all will be mixed). And I think it's right.
    → Reply
»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
Can you make a PDF version of the problem statements?
→ Reply
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Rated or Not?
→ Reply
»
13 years ago, # |
  Vote: I like it -65 Vote: I do not like it
It would have been much better,if the contest was separate for each division,with 50 t-shirts for each...
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    if seprate person's in two groups then some of the participant in Div.1 create new account and register for Div.2 so it's better to combine all the participants.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it
      If you assume that,then anything could be possible.Any user can have two accounts,winning away two t-shirts.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        "If you assume that,then anything could be possible.Any user can have two three accounts,winning away two three t-shirts."
        -piyush006
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it -6 Vote: I do not like it
          I believed that CF will check if your code is similar to others.
          → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    It would be unfair for people who recently made it to div 1 - their chances of winning a t-shirt would be really low when compared to situation when they had stayed in div 2.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +24 Vote: I do not like it

      Of course, Codeforces cannot make a decision that makes everybody happy. So let's just forget the debate and enjoy the contest!

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it
      if we can't get the t-shirt, maybe CF can send us the JPG or other type of t-shirt image and we can make it by our own. so don't think the t-shirt just do the best

      → Reply
»
13 years ago, # |
  Vote: I like it +21 Vote: I do not like it
That awkward moment when you know you have no chance of winning a t-shirt.
→ Reply
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
> 2500 registrants!
→ Reply
»
13 years ago, # |
  Vote: I like it +23 Vote: I do not like it
This is sad.

For A, I set EPSILON as 1e-10 and I keep failining. After I changed to 1e-8 I passed the pretest ...

Argh why D=
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Many of DIV 2 participant will be going down :P
→ Reply
»
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it
This is the toughest problem set I have seen through ever.Even the easy one was quite difficult.Cheers to natalia for creating the problemset.I am sure I am going to learn much from the editorials .So lookking forward for it.....
→ Reply
»
13 years ago, # |
  Vote: I like it +26 Vote: I do not like it
points were not properly distributed, b was tougher than c or d
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    IMHO b easier than c, but d is the easiest in problemset...
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it
      may be but it took me a lot to understand problem b
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it
      Yes ,truly D was the easiest one .Read it now after the contest as was stuck in the previous ones during the contest :(
      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    For me also B was much much easier then C. Seeing the no of solve for C, I went for C. I got wa and when get the case, got no idea for solving it. But when finally I read B, it took me 2 min to solve and then 5 min to submit. D was indeed very easy but seeing its number, I thought the idea must be wrong and don't code that.
    → Reply
»
13 years ago, # |
  Vote: I like it +20 Vote: I do not like it
I'd like to study Russian...
→ Reply
»
13 years ago, # |
  Vote: I like it +39 Vote: I do not like it
Wow, System Testing is really fast :)
→ Reply
»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it
the system test runs fast today, doesn't it?
→ Reply
»
13 years ago, # |
  Vote: I like it +38 Vote: I do not like it
So Close ... Just 500 place away :D :)
→ Reply
»
13 years ago, # |
  Vote: I like it -13 Vote: I do not like it
TAT
→ Reply
»
13 years ago, # |
  Vote: I like it +16 Vote: I do not like it
In my opinion, this problemset is not balance. C,D are too easy (>500 correct submissions) while E,F are really hard.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    F is easier than it looks.

    I liked the problems, but the points didn't seem right to me.  E is harder than F and D is the easiest in the set.
    → Reply
»
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Поздравляем  farsid1005093, сделавшего 1000000 сабмит!
Congratulation farsid1005093 for 1000000 submit!
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Футболку счастливчику =)?
    → Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
number of  T-shirts will be 101 we have two contestants in the same place #100  :) 
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

About task E:

What to do with C(N,K)? It seems I only precomputed until N <= 5000, K <= 5000.
But you need N <= 10^6, K <= 5000. Precomputing them all shouldn't pass, while the modulo isn't always prime number.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    You can avoid division. C(N,K) will be multiplied by K! in the future.
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    In my solution you need only values of and K! for N ≤ 106 and K  ≤ 5000. Both can be calculated with no problem. C(N, K) can be also calced becouse we need them for fixed N and small K. So we can calc them as product of O(K) numbers, with time of K2.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Oh, okay, thanks! Interesting way to calculate, got to remember that.
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you give me additional explanation ? it's unclear to me how to compute C(N,K) from product of O(K) number.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You don't have to calculate C(N,K) = (N!)/(K! * (N-K)!). Because in solution there is a multiplication with K!, you only need to calculate (N!)/((N-K)!).

        Which you can calculate as:
        (N-K+1)*(N-K+2)*...*(N-1)*N

        Maximum of K numbers will be there, and K is small.
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it
          One note, now that I succesfully changed my code.

          In one place you need:
          ((N! / (K! * (N-K)!)) - 1) * K!

          You can still transform it to neccesary form:
          (N! / (N-K)!) - K!
          → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -110 Vote: I do not like it

I understood why the system test was SO FAST!

I think, admin did the final tests just after the submission and not after the contest.

(ctrl + click to see the system test timing)
(Give me plus now!)
→ Reply
»
13 years ago, # |
  Vote: I like it +24 Vote: I do not like it
Why is that "Beta" still on Codeforces logo?
→ Reply
»
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it
The problem statement was awful i can't understand problem B at all(no sufficient information).....i hope in coming contests the coding ability will be judged not the reading ability.................
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Yes, I could not understand this problem at all.

    Why did Alex. send card 1 to 2 and to 3 and not to 4?
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it
      another example:

      "In other words, so that as a result of applying two Alexander's rules, each friend receives the card that is preferred for him as much as possible."

      does the "him" there refer to "Alexander" or to "each friend?"

      I see nowhere in the problem description where the friends' preferences are considered.  The only use of preference in the rules is "Alexander always chooses one that Alexander himself likes most."
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        "Determine at which moments of time Alexander must send cards to his friends, to please each of them as much as possible."

        The two rules serve to uniquely determine what card Alexander gives to a friend if he decides to give that friend a card after receiving card i. The friends' preferences are not relevant in the choice of the card for Alexander at any given point in time; Alexander's choice given a specific time is independent of their preferences. At a specific point in time, if Alexander is to give friend K a card, Alexander must give friend K the card that Alexander prefers most out of all the cards that Alexander has received at that point in time, excluding card K if he has received it. 

        The friends' preferences are only relevant in returning an answer. The problem is asking to determine, for each friend, the best time for Alexander to send that friend a card. 

        An equivalent formulation of the question is, given that Alexander has to follow the two rules, and he receives the cards 1 through N one at a time, what is the most preferred card that Alexander can make each friend receive? If you can figure this out, then the answer for each person is just the number of the card.

        More detailed explanation of the sample case:

        1) Alexander receives the first card.

        At this point, he can give this card to each of the second, third, and fourth people. The second person is guaranteed to receive at least his second-most preferred card; the third person is guaranteed to receive at least his third-most preferred card, and the fourth person is guaranteed to receive his fourth-most preferred card.

        2) Alexander receives the second card.

        Now, Alexander prefers the first card to the second card, so he will give the first card over the second card in all circumstances except for the first person, who cannot receive the first card. The first person therefore receives his second-most preferred card, which is the best that Alexander can do because Alexander cannot give the first person his most preferred card.

        3) Alexander receives the third card.

        Note that Alexander prefers the third card to the first card, so for all people that are not the third person, if Alexander chooses to send a card now, he must send the third card. This is not an improvement for the first person or the second person. The third person must still receive the first card, as the first card is the most preferred card out of all the ones that Alexander has received so far that is not the third card. The fourth person prefers the third card to the first card, so we now know that giving the fourth person a card at time 3 is optimal.

        4) Alexander receives the fourth card.

        The third card is preferred to the fourth card, so Alexander giving at time 4 is equivalent to Alexander giving at time 3.

        Note that giving at time 1 for friends 2 and 3, at time 2 for friend 1, and at time 3 for friend 4 was found to be optimal, so we return "2 1 1 3" (quotes for clarity). Note that giving at time 4 is equivalent to giving at time 3 for the last friend, so that is why the given sample of "2 1 1 4" is also valid.
        → Reply
»
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
Soooooo close, just 82 points needed :S
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It will be rated or not?
→ Reply
»
13 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Rank 102...

Feel a little sad...

I would appreciate it very much if you can send one more T-shirt!

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it
    if admin do this,so  "by induction" all contestants have to take T-shirt  :)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, you're right
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it
      not really, if they give each 1xx a T-shirt with probability 1/(1xx-100) it will be really low after some time.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        What an interesting idea!
        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        let it be xxx instead of 1xx :P .. 
        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        In that case, the expected number of participants getting T-Shirt would be about 105: http://ideone.com/kzUAE . Since it was not fair that someone might not get a T-Shirt although lower rank coder got one, someone might argue: why don't CF give the T-Shirts to the top 105 participants instead? But hey, why don't we use similar algorithm with 105 replacing 100? It would repeat again and again until the number of T-Shirts given converge to 199: http://ideone.com/MpOeb. However... there might be similar argument: why don't we use the same idea for 2xx participants? They are also so close to the boundary. After the number converges to 299, someone will request the same thing for 3xx, 4xx, etc. In the end, it's not much different than previous idea: everybody has to get a T-Shirt.. :)
        → Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
The problem set was nice .. but the problems were not arranged according to difficulty... problem D was definitely easy and I think many of the novice coders(including me) did not even get time to solve it as a lot of time was spent to understand and code problem A B and C...
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    I am agree, D was really simpler than B and C
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think the right order should be ADBCEF
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      For me:
      D - 500
      B - 500
      A - 1000
      C - 1000

      I can't estimate the difficulty of the last 2 problems.
      → Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Editorial eagerly awaited!
→ Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
In Problem A,During Contest i used Double Precision and got WA on pretest 6( which was a boundary case 6 9 3).........after the contest i just replaced Double by float in my code and got AC.....hard luck :(

how did you guys got hint of using float instead of double ?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    i just replaced floor(2 * pi / (2 * alpha)) on floor(2 * pi / (2 * alpha) + eps)
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used double, but used epsilon while comparing, like s + eps > n. (where eps = 1e-11)
    It is useful to remember this while doing double comparison.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thnx guys...i will remember eps next time while comparing doubles :)
      → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Cant we use the cosine formula instead of sin in Problem A???I am getting WA when I am doing that
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
May I ask why the virtual participation still not available for this round? Is there something special will happen soon?
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -45 Vote: I do not like it

Please give me '+' , I don't know why my Contribution is -12 !

→ Reply