witua's blog

Codeforces Round #104
By witua, 13 years ago, translation, In English

Hi!

Tomorrow, January, 22-nd at 11:00 o'clock (Moscow timezone), will have place Codeforces Round #104! The problemsetter will be me, Herasymiv Vitaliy (witua). Thanks a lot to Artem Rakhov (RAD) for help in praparing the problems and Maria Belova (Delinur) for problems translation.

I hope you will like this round.

See you tomorrow!

Points destribution today is:

DIV1: 500-1000-1500-2500-2500

DIV2: 500-1000-1500-2000-2500

Thanks to all, and here are the results:

Division 1:

  1. tourist
  2. dzhulgakov
  3. PavelKunyavskiy
  4. wuzhengkai
  5. shangjingbo
  6. ilyakor
  7. Gerald
Division 2:
  • Vote: I like it
  • +143
  • Vote: I do not like it

Comments Comments (43)
| Write comment?
»
13 years ago, # |
  Vote: I like it -32 Vote: I do not like it
Thanks for preparing this round and I hope everyone will have fun attending it!
Good luck to all contestants :-)
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it
    I think that people don't believe in wishes ,, So usually posts saying good luck get minuses 
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it
      No, the reason is simpler. There are about 1500-2000 contestants participating in each round. If each of them add a comment with "GL&HF" the post become useless and unreadable. Because of this such comments (though not evil by nature) are regarded as meaningless and annoying.

      And what about believing in wishes... Notwithstanding wishes count rating system have such a magic property that total points won (for all contestants) roughly equals total points lost.
      → Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
This is the earliest blog for the CF Round I have ever seen.Normally it is written 2-3 hours before the contest only.So hoping that I will solve questions early too and then get early editorials also:)
→ Reply
»
13 years ago, # |
  Vote: I like it -52 Vote: I do not like it
Good luck and have fun to everyone!
→ Reply
»
13 years ago, # |
  Vote: I like it +44 Vote: I do not like it
Today is Chinese New Year's Eve. Happy New Year!
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    Yes.and that is why the standings before the system tests are dominated by them.7 chinese in top 12.:)
    → Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Lucky round ?
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Arg, was div2 E Newtons Identities?
It only struck me in the last minute that that might be fast enough, since there are much less than 10^5 lucky numbers less than 10^5..
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi there,
Can someone explain me how to calculate C(n,k) MOD P as fast as possible? It is what I didn't know about Problem E.

Thanks a lot.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it
    Pascal triangle?
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it
      as fast as possible:)
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      We can do it using Pascal triangle.
      But the Problem wanted it Modulu a prime number, so there will be a faster solution

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

    As n!/k!/(n-k)!. Modulo division can be performed with multiplication by inverse (http://en.wikipedia.org/wiki/Modular_multiplicative_inverse). For prime modulo p, the inverse of a can be found using Euler's theorem as a^(p-2). It can be calculated using fast exponentiation in O(log N).

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Great man! Thanks a lot! I didn't know about that!
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      For this formula: sum([int(k*p/q) for k in range(1,(q+1)/2)]) where p and q are both prime numbers and not equal to 2. How to calculate it fast?
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If you need to calculate your formula many times, you can use particular sums (sorry if it wrong. in russian the popular name for it is частичная сумма) for unchanging var p. Like precalculating. e.g. for array: a = [1,2,3,5,6,12,4]. for each element we calculate s[i]. s[i] = a[0] + a[1] + ... + a[i]. So we can use formula: s[0] = a[0], s[i] = s[i - 1] + a[i] (i > 0) to calculate it. i.e. after calculating, we have s = [1, 3, 6, 11, 17, 29, 33]. So if you want to calculate a[l + 1] + ... + a[r - 1] + a[r], just use s[r] - s[l].

        P.S. you can change the line sum([int(k*p/q) for k in range(1,(q+1)/2)]) to sum(k*p//q for k in range(1,(q+1)//2)). I think it will be faster than the first one.

        P.P.S. I didn't check it for python2.7, but for python3.2 it should work.

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Choose(n, m) = (n!) / ((k!) * (n-k)!)
    We can precalculate k! % mod for all k = 0..n, then
    Choose(n, m) = (n! % mod) * ((k! % mod) * ((n-k)! % mod)) ^ (-1) % mod, where a^(-1) % mod is such a number, that a * a^(-1) = 1 % mod. Calculating a^(-1) % mod requires O(log(mod)) time and can be done with Extended Euclidean Algorithm, or using standard function (such as BigInteger.modInverse in Java).
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      becuase mod is prime( 1000000007 is prime) 

      so we can use pow(a, 1000000005 ) to find inverse
      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    use multiplicative inverse

    → Reply
»
13 years ago, # |
  Vote: I like it +283 Vote: I do not like it
Some moment during system testing
 
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    look @ the "up" vote for your post! :)  (its +47 )

    {lets make it +74)

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

    And now this comment has +47:


    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Print screen at the moment, when I saw the comment (click to see full image).
    → Reply
»
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it
I think the time limit for the last Div 1 problem is a bit strict. My O(N log N) solution using C++ cin timed out, and after contest I used scanf and got accepted in about 2 seconds. This is not a long contest, so I think judge should allow 4x time of the optimized solution, which is currently 1 seconds. Some correct solutions timed out because of this.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Generally, I think time limit should not be too much, because codeforces server is tooooo fast. In a Codeforces contest long ago, there's a problem with N <= 10^5 and I got accepted with O(N^2) algorithm, with buffered reading to read a few MBs.
    Maybe if time limit is increased, some tricky brute force solutions would pass system test. And I think cin is super super slow, even if the time limit is tripled, I don't think it would have much chance to pass
    → Reply
»
13 years ago, # |
  Vote: I like it +15 Vote: I do not like it
This is your 3rd contest I participated in (the others are round 77 and 91). Surprisingly, I became red after all of them. In my opinion, they're truly "lucky" contests :-)
→ Reply
»
13 years ago, # |
  Vote: I like it +29 Vote: I do not like it
tourist got +47 to the rating (just another lucky number :)
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    looks like "47" is the luckiest of all the lucky number.
    [frequency of its occurrence on this page taken into account]
    → Reply
»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I solved the problem E in last 30 seconds, it's a prize for me in Chinese New Year~ 
Thank you code force ;)
→ Reply
»
13 years ago, # |
  Vote: I like it +19 Vote: I do not like it
I got +4 rating increase in this round. It's the lowest lucky number :(
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Your contribution is : +47 which is lucky

    Your Registration is 13 month ago. so 1 + 3 = 4 which is lucky sum 
    Your Rating is: 2023. so 2 + 0 + 2 + 3 = 7 which is lucky sum
    So ;you are really lucky in this month.
    Wait not finish. Your previous contest rating increase +16. so 1 + 6 = 7. That is also lucky sum.
    ha ha ha ha :)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      Thanks. I even didn't notice that :p
      I hope I will get +117 rating increase in the next Codeforces Round.
      It is lucky multiplication (1 x 1 x 7 = 7), and my rating will be 2023 + 117 = 2140, it is lucky sum (2 + 1 + 4 + 0 = 7).
      ha ha ha ha :)
      → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.


But how can i understand 04,07,044,047,077 are either lucky numbers or not.
I think that those are also lucky numbers.
Because above numbers are equivalent to 4,7,44,47,77.

Can anyone explain me, whether am i wrong or correct?
Thanks.
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    decimal record contains only the lucky digits 4 and 7

    0 is not a lucky digit.
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't understand why I got WA on problem B.

I got some AC codes and tested many cases, but nothing error.
So I checked my submission(#1104370), but I don't understand the message of Checker Log, it said "wrong output format 44444444444444444444444444...777777777777777777777774 is not valid integer"(test data is "100000 100000 1 1").
I checked this test data before, but I didn't find anything error.

Well, I'm upset, who can help me? Thanks very much!
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Well, I found the mistake, I just create an array with length of 2000000, I should have allocated more space.
    → Reply
»
13 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Could someone tells me the solution of problem D || E of div1 ? Many thanks ~!

→ Reply