ll931110's blog

Codeforces Round #191 (Div. 2)
By ll931110, 11 years ago, In English

Welcome to another Codeforces Round!

Please note that the time of round #191 was changed. Contest will start at Thursday 12:30 UTC.

My name is Linh (ll931110). I'm from Vietnam, and I'm glad to present to you my first Codeforces round. It is for Div 2 only; however, I welcome participants from Div. 1 to participate and enjoy challenging problems. I hope this would be a pleasant gift for those who are going to IOI 2013 (and participants from World Finals), which will take place in just a couple of days.

This round is prepared by me and fchirica (from Romania). Also, I would like to thank the Codeforces team who puts efforts on making Codeforces and Polygon possible.

Happy solving!

UPD1: The score of problems in this round will be dynamic. The problems will be sorted in increasing difficulty order, at least in our perspective.

UPD2: The contest is over! Congratulations for everybody, especially for those who solved E. You proved to be smarter than I am (your solutions were totally unexpected to us). Thank Gerald, Aksenov239 and Delinur for helping us on preparing the round!

Div. 2 winners:

  1. SillyHook02

  2. Tsukiko

  3. Quit_Quickly

  4. Zhengxu

  5. sevenzplus

Those are five people who nail all problems!

Unofficial winners:

  1. Kissshot

  2. R_R_

  3. xchernoff

  4. wakaka

  5. phtniit

The editorial will be completed soon after revising and adding possible alternative solutions. You are welcome to post your answers in comments.

Thank you and see you in the next round!

UPD3: Editorial is now available. Remind that it is not the final version, as we are writing possible alternative solutions for problems. Stay tuned!

UPD4: Editorial is now completed.

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

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

Thank you for the contest!
And I hope your first round will be successful!

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

i think contest's date is late for some IOI participants.

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

    It's div2, man

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

      And what? IOI participants on div. 2 it's also exists, and number of them near half.

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

        It's just that I doubt that competitive IOI participants have a great desire to solve div2 problems. And aside from that, it turns to be "contest date is late for some people", which is common.

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

How to read your nick?)

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

    this is how: ll931110

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

      I mean, for example: JKeeJ1e30 reads like "Zhelezo" which mean "Iron" in russian. JK is like russian letter "Ж". Another letters in this logic.

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

      "llninethreeoneoneonezero"?

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

      Maybe it like. II means 20 century. 93 means 1993 year when he was born. In this logic 11 means 11th month(november) and 10 is day.

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

    ll is his name. and 931110 is his birthday. you can read what ever you want :)

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

Our flight to Australia should depart 20 minutes after the start of this contest, but we'll participate if the flight is delayed. :)

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

nice, hope there is always 1 contest per week at least :D

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

Oh the first CF round made by Vietnamese. As a Vietnamese, I'm really excited !

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

It's a pity that our school have to cut off the internet after the midnight, so I only get 30 minutes to work out and submit my solutions. Can you suggest the officials to start the contest a little earlier if it doesn't bother most of the coders, that would be lovely.(Ps I'm in China)

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

    I have the same problem and I came from China too. Also our school would cut off the internet and power when the CF contest start(7:30pm MSK) by coincidence.But I always use my phone to create wifi hot spot to porovide network for my computer,then I can participate in the contest.I think the contest start little earlier will bring great convenience for Chinese participants.

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

      My mobile phone operators is CMCC, as a result I can't create a hot spot.T^T

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

It is very unfortunate that the start time has been moved. I was very much looking forward to this contest.

Thanks for preparing it, anyway.

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

almost missed it. why time changed? :/

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

Missed it, didn't notice the time change :( please try and avoid this in future, not many of us keep checking the time..

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

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

    Что неправильно в этом решении? http://mirror.codeforces.com/contest/327/submission/4020058) (точнее, что надо сделать, чтобы оно зашло)?

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

      Во-первых, возводить надо по модулю. Питон не потянет 2^100000 за 1 сек. Во-вторых, зачем делать это вручную если в питоне есть встроенная функция pow(x,y,z), которая возвращает x^y по модулю z, причем работает за O(log(z)) и в данном случае не будет использовать длинку.

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

        спасибо, понял, как надо было

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

        Скорее за O(log(y))

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

Please see Submission http://mirror.codeforces.com/contest/327/submission/4018453 . I use the data 100000 to hack it . When I run this code(I type it by my own on contest) on my PC , I use 10+ s. On the custom test , it speads 3s+. However , unsuccessful hack , it says that only use 78ms . WTF ? What's wrong with codeforces ?

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

    it's normal(i had unsuccess. hack too). mb it's because when you run code in debug mode it works slow.Remember about optimizations. Or if you type n manually it will use about 0.5 sec :D .

    Today many solutions(sieves,bruteforces) passed TL. if n was 10^6 , it would be cool

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    "When I run this code(I type it by my own on contest) on my PC , I use 10+ s"

    run it in "Custom test" on Codeforces

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

how did the system testing complete so early this time??within 5 minutes

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

Wow amazingly fast system testing!

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

For problem E, In case of k = 2, call smaller k1 and larger k2. My idea was to find number of permutations having prefix sum k1 and k2. Then find the number of permutations such that it's initial prefix has some k1, and some other initial prefix has sum k2. how do you solve the just above part?

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

This has got to be the fastest system testing and rating change in the history of codeforces!! :O

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

very good and fast system testing today! :)

well done guys, it was a good contest! the only thing lacking was hacking possibilities, next time try to exclude some (not all, mind you! :D ) corner cases from the pretests!

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

thank you for the interesting contest!

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

Nice problem E indeed I love it :)

when k<2 the problem is easy

when k=2 the answer is:

answer = n! — (the number of permutations that passes k[0] + the number of permutations that passes k[1] — the number of permutations that passes both k[0] and k[1])

to calculate the number of permutations that passes both k[0] and k[1]:

find the number of ways to choose two Non-intersecting sets from the the input integers so that the sum of elements in first set is K[0] and the sum of elements in the second set is k[1]-k[0] (assuming k[1]>k[0] if not swap them) then for each way we have (u! * v! * (n-v-u)!) permutation satisfy condition above where u is the number of elements in first set and v is the number of elements in second set

to calculate the number of ways to choose two Non-intersecting sets from the the input integers one can use meet in the middle attack but the number of permutations depends on the size of two sets so:

for i=1 to N do

for j=1 to N do

let P = the number of ways to choose two non-intersecting sets from the the input integers so that the sum of elements in first set is K[0] and the sum of elements in the second set is k[1]-k[0] and the first set contain i integers and the second set contains j integers

add to answer i! * j! * (n-i-j)! * P

end for

end for

this is my guess to problem E , I didn't code it so I'm not quite sure that my idea is ok

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

very nice problemset&tests congratz authors:D

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

How to solve C?

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

I fail system test #24,but in custom test I run with 656ms.In theory，my algorithm is O(n).Can someone tell me why I got a TLE? my code http://mirror.codeforces.com/contest/327/submission/4012901

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

    There are more than 10^5 primes between 2 and 2000000. So, finding primes upto 2000000 is more than enough. It will improve the runtime significantly. My code also calculated prime upto 10^7 and I got AC. Even with a slight modification (strange, but replacing printf with cout) your code http://mirror.codeforces.com/contest/327/submission/4021421 got AC.

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

      So strange！cout is more slow in theory, isn't it?

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

        yah it's strange! that's why I submitted your code 11 times to test only. Actually there is another very fast O(N) solution that even doesn't need sieve :-)

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

          Can print the big number and every pair of number's divisor is less than 2,because 2 is the smallest factor.

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

            What about print i, from 10^6 to 10^6 + n ? :D

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

      It is rather easy to calculate all primes between 2 and 10000000 in < 300ms. 4022940

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

The problems are pretty straight forward...

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

Fantastic problem set for your first Codeforces round. Congratulations! Keep on programming :)

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

E's test case didn't catch overflow in calculating sum. (meaning it didn't have the case where overflow in calculating sum cause the sum of some subsets equals 'bad luck' numbers). You can see my latest submission, which got accepted instead of WA.

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

pretty fast system testing and rating updates, i am impressed :)

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

4019604 4017612 4017184

These solutions in fpc appear to be the same. Please check.

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

How to solve E with DP?

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

I don't usually post things like these... but I am very confused why I got WA on the very first test case of D. http://mirror.codeforces.com/contest/327/submission/4023027

In the end, doesn't my solution create the same towers in the same positions as the judge's solution? [EDIT] Note: please ignore the code, and jump straight to the very first test case output.

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

Wow, there were only two successfull hacking attempts during the whole round!

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

    what's even more strange, is that both were made by coders from the same room!! :D

    http://mirror.codeforces.com/contest/327/room/25

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

      What is more strange that XmanX first submitted a solution in which he outputs hardcoded value for n=1, which fails system tests. Then submits a solution in which he hardcodes output for n=2. His submitted time is 1:24:01 and solution gets hacked at 1:24:47. After which he removes the hardcoded output and gets accepted.

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

Great contest , i loved it . The problems were great , but if you look at eoy5ihz536 , 4mkf2bw9w6 and xhn4ws5gz9 ' s contest submissions , they are the same . Moreover they were submitted by 1 minute gaps for each problem . I think they are trying to cheat . Shoudn't this contest be unrated for them ?

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

When is the next contest scheduled?

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

[user: RR, 2013-07-04] what is this ? :D

→ Reply