Блог пользователя ll931110

Автор ll931110, 11 лет назад, перевод, По-русски

Добро пожаловать на очередной раунд Codeforces!

Обратите внимание, что время раунда #191 изменено. Раунд начнется в четверг 16:30 MSK.

Меня зовут Linh (ll931110), я из Вьетнама, и я рад представить для вас мой первый раунд Codeforces. Раунд будет Div. 2 onlу; однако, я приглашаю Div. 1 участников посоревноваться и получить удовольствие от непростых задач. Я надеюсь, что этот раунд — хороший подарок для тех, кто участвует в IOI 2013 (а также участников финала ACM ICPC). Заметьте, что раунд будет проводиться всего через пару дней.

Раунд подготовлен мной и fchirica (из Румынии). Традиционно, я хочу поблагодарить команду Codeforces, которая прикладывает много усилий, чтобы поддерживать Codeforces и Polygon.

Приятного решения задач!

UPD1. Будет использоваться динамическая разбалловка. Задачи при этом расположены в порядке предполагаемой сложности.

  • Проголосовать: нравится
  • +201
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Вьетнамо-Румынский контест...интересно)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Я думаю, это заслуга организаторов: у одного автора были одни задачи, у другого — другие, они их совместили.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    It's div2, man

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
11 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

How to read your nick?)

»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

almost missed it. why time changed? :/

»
11 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Смотрю текущих лидеров, которые "не в рейтинге"... мне одному кажется, что здесь что-то не так? Или просто новичкам везет? :)

Hiiragi_Kagami, зарегистрирован: 62 минуты назад.
i_try_to_win_in_div2, зарегистрирован: 6 часов назад.
horseleat, зарегистрирован: 82 минуты назад
for_the_money, зарегистрирован: 68 минут назад
Quit_Quickly, зарегистрирован: 101 минуту назад
hiwang321, зарегистрирован: 60 минут назад
orzkac, зарегистрирован: 6 часов назад
yamal, зарегистрирован: 5 часов назад
YJSNPI_Returns, зарегистрирован: 102 минуты назад
...
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please see Submission http://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 ?

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wow amazingly fast system testing!

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

потратил полчаса на то, чтобы увидеть геометрическую прогрессию в задаче С...

»
11 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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!

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thank you for the interesting contest!

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Полное тестирование прошло так быстро, что я все еще не верю, что оно уже закончилось))

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

very nice problemset&tests congratz authors:D

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Когда будет разбор ?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.com/contest/327/submission/4012901

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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://codeforces.com/contest/327/submission/4021421 got AC.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :-)

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The problems are pretty straight forward...

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

4019604 4017612 4017184

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

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E with DP?

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

И опять в div2 контесте в топе куча только что зареганных людей..

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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://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.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 ?

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

When is the next contest scheduled?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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