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

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

Hi,

Codeforces Round #282 will be held at 13th of December, 19:30 MSK. Please don't note anything since the time is the usual time of contests.

The round is prepared by FarbodY, Haghani and Me(matrix).

We'd like to thank Zlobober who helped us a LOT for preparing the problems, MikeMirzayanov for the Polygon and Codeforces platforms and Delinur for helping us in preparing statements and translating them.

Our special thanks goes to mruxim for testing the round.

The problems will be sorted according to the estimated order of difficulty according to our opinion but we strongly recommend you to read all of the problems.

As always the update regarding score distribution will be posted just before the round starts. :)

UPD: It was written that contest starts at 20:00 MSK. it was a mistake and is fixed now. The round starts at usual time 19:30 MSK.

UPD2: We also thank niyaznigmatul for testing our round.

UPD3: Score distribution:

Div1: 500-1000-1750-1750-2500

Div2: 500-1000-1500-2000-2750

As you might have noticed, the scores can now be multiples of 250 as well. Let's thank Codeforces team for adding this feature!

Good luck and Have fun!

UPD4: Congratulations to the winners of both divisions:

Div1:

  1. tourist
  2. winger
  3. sankear
  4. uwi
  5. Egor

Div2:

  1. Ginger88895
  2. pwild
  3. arthurpd
  4. konmaj
  5. ezkatka

The editorial for all problems except D and E Div1 are ready and can be found here. It'll be completed soon.

We thank you all for participating and hope you had a good time.

UPD5: The editorial is now complete and can be found here.

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

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

wow :) iranian contest I love them :)

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

matrix your graph is awesome and very motivated

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

Our special thanks goes to mruxim for skipping this round just because we needed a tester

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

"Please don't note anything since the time is the usual time of contests."

»
9 лет назад, # |
Rev. 6   Проголосовать: нравится -63 Проголосовать: не нравится

Happy coding

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

hope to see a nice problem-set and rating growth :)

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

This will be excellent preparation for the USACO December Contest.

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

Zlobober has a great contribution in almost every contest. Thanks bro.. :)

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

Have fun and good luck to all of you.

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

Codeforces really should think about some additional promotion, today I've found topcoder easter egg in locker room

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

Time for dreamoon_love_AA :D

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

It will be a good contest ...

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

Hope for much [pure] math

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

    For me more interesting when anybody have more chances to hack each other(I want low pretests!!!).

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

      Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.

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

    And I thought I was the only one

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

      i hate hacking ): I like contests like ICPC, where you know if your submission is right or wrong when you submit it.

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

It will be a great contest.

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

So happy for div.1 contest)))))

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

At last after 10 days !!!

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

Врываюсь в желтые сегодня короче)))

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

    Не получилось, не фартануло.

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

      Действительно. В который раз я уже лажаю на ошибке 0 — 1 != 1000000006?

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

hope candidate master for every expert

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

Wanna be Blue.... Gonna be White... -_-

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

it is my first time for div.1.....

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

I just want get a purple handle in this round~

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

I hope this contest will bring me from unhappiness...... I even suspect whether coding is suitable for me...

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

    Well...I didn't got a purple handle, en.....when you tired or lack of confidence,look at me ~, many times I tried my best but got a bad result, but I firmly believe that one day, I can become an excellent coder, not only in ACM. A gold medal is not necessary to prove yourself.

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

Don't you think it is a good idea to announce the scoring right now? Because of I think the website will be down (hope not) in a few minutes and you won't be able to announce it just before the contest! :D It would be after the start of the contest!

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

1750 points. O_O Rly?

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

"As you might have noticed, the scores can now be multiples of 250 as well. Let's thank Codeforces team for adding this feature!" Sounds sarcastic

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

CF #282

We hack as we could

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

Problems A, B and C are easy; but problems D and E are difficult ! (in Div. 2)
There isn't any normal problem :D

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

Good Bye div1)

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

correct score distribution (div. 1): 500 — 1500 — 2500 — 2500 — over9000

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

Как решать C?

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

thanks a lot for nice problem :)

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

last 10 minutes, server was down. I could hack 10+ solutions but...

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

Woah, wasn't able submit my solution to A because codeforces wouldn't load. :(

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

A div1 / C div2:

(#(
Answer: -1
WA: 2
»
9 лет назад, # |
Rev. 7   Проголосовать: нравится +26 Проголосовать: не нравится

fail of the year

A: forgot if(b[i] < 0) ans is -1.
B: forgot if there is no S in T ans is 0.

added two ifs and got accepteds :(

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

What's the hacking test case for Div2A?

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

Server Problem,vary painful.

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

Я надеюсь, что "невозможно отправить в последние 5 минут контеста" = "раунд нерейтинговый" ? Под невозможно я имею ввиду "совсем невозможно" — увидеть не страницу "извините, всё плохо", так и не удалось.

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

What's wrong with test 6 in D, my stress test doesn't reveal any problems =(

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

    Check all modulo operations carefully, especially with negative numbers.

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

      Eh at least now my stress is giving different results, but I can't find the mistake =(

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

Преступление и наказание (одновременно взломал сам и взломали мою задачу)

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

Last 10 minutes :(

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

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

    Your avatar fits well to that pic :P.

    For me it was best round ever with regard to number of hacks (I got +6/-1) :). "(#(" ftw :D! As well as best round ever with regard to place before systests (8th), I hope it will stay that way after them :P.

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

For div2, a lot of solutions for B had bad complexity O(a) — I managed to submit only two hacks though, due to the server being down for the final fifteen minutes.

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

Sadly, this time too, Codeforces went down in the last ten minutes. solved problem C but couldn't submit :(

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

please improve the server or limit the contestants number !!!!

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

Any idea about how to solve Div-1 B?

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

    I found all occurrences of t in s using KMP, then did DP on the the position of the last substring you take.

    So dp[k] would be the number of valid substring selections where none of the substrings have any chars after the kth char, and the kth char is within one of the selected substrings. Calculating dp[k+1] would depend on whether a pattern of t ended at position k+1 or not.

    I'm not sure if this is right, but it passed pretests.

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

      I did it in the same way — probably a useful structure is >> int last_before[i] << , indicating where is the last occurence of t in s, that ends before i. Then the recurrence can be sumarized to:

      dp[i+1]=dp[i]+sumdp[last_before[i+1]]

      sumdp[i+1]=sumdp[i]+dp[i+1]

      (with edge cases and similar stuff added, of course)

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

    Dynamic programming . For each index i in array, calculate the number of ways dp[i] such that b_k is i. And then sum of all these ways.

    To do this , first find out all the occurences of pattern in text using KMP. Then recursion to calculate dp[i] for i =1 to n(size of text) would be

    dp[i] = sum( j = 0 to pat_start[i] , sum(t = 0 to j, dp[t] ) ); dp[0] = 1;

    where pat_start[i] = largest index p such that Substring[p,i] contains given pattern.

    Now this dp might seem like O(n^2) but by maintaining some additional summations, we can do it in O(n)

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

Good bye, Blue. Welcome Green, again.

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

Я один столкнулся с тем, что, пытаясь взломать, при открытии чужого решения, открывается окно с посылками, само решение не открывается, ссылку с решением, на которую можно нажать тоже нет, в итоге взламывать невозможно? Так было вначале, потом удалось таки один раз взломать, потом тоже самое до конца контеста. Поведение одно и тоже на Ubuntu (Chrome и FF) и на Win8 (Chrome).

Я конечно и сам залажал контест, но невозможность взламывать тоже как-то выбила из колеи.

Ответы жюри:

"У вас должен быть установлен Flash. Некоторые плагины могут резать Flash, считая баннером. Попробуйте так же воспользоваться другим браузером или очистить кэш/cookies."

"В итоге ведь получилось произвести взлом? Остальные участники не жалуются, проблема где-то на вашей стороне."

"Мы не можем ничем помочь."

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

    У меня каждый второй раз открывалось только окно для взлома, без решения. Firefox 34, Win7.
    З.Ы. Это нормально, что я не могу переключить у себя галочку "по-английски" на "по-русски", отвечая на этот комментарий?

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

    да, было такое. и ещё за 10 минут удалось взглянуть только на 4 решения.

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

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

It's midnight and I am facing an usual dilemma: do I go to sleep before the rating update or after? It's always a difficult decision...

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

    The answer is: yes.

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

      That's kind of a confusing answer :p 1) Yes, you should go to sleep before rating update. 2) Yes: you should go to sleep after rating update.

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

        The answer to V OR NOT V is TRUE :D

        (I'm assuming that you're unable to go to sleep exactly when the rating updates start.)

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

        I think he meant: Yes, you should go to sleep before or after the rating update.

        Because you should go to sleep at some point, right?

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

    I suppose to think that the contest will be unrated.

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

      Isn't it only me who had really slow and rare access to the website? Almost all my friends say that everything was ok and it was only my problem.

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

How to solve C? Tried to implement some DP on a tree, but answer on the 3rd sample was slightly incorrect.

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

    Yep, DP on a tree. On probabilities that the answer is (trivial lower bound + k).

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

    " but answer on the 3rd sample was slightly incorrect." — no, it wasn't.

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

      I think he means his own code's answer :D

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

        Lol, during the round there was some announcement stating that answer to third sample is really correct, so I thought that it related to that :P.

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

    The idea here is to change each # in such a way to get a correct sequence of brackets, correct sequence is "()", and then "(correct)" or "()correct" or "correct()", I think I didn't miss any.

    If we want to get correct sequence of brackets on each index i starting from 0, we should have the number of ')'-s less or equal to number of '('-s and these two numbers should be equal for the whole string. Here we should keep in mind that we should change each # with at least one of ')'. So we can replace each # with only one ')' and we can replace the right most # with such number of ')'-s that the number of ')'-s will be equals to number of '('-s in the whole string. My solution was this, I hope it will pass system testing.

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

why testing is stopped?

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

I solved E, but read it in a wrong way: I thought rectangles could not intersect. I understood I needed a segment tree, but couldn't wrote it in time. Now it's working with stress test. :( I think it made the problem worse. When you've already got the idea, got the formula for d[x][y], then for rectangle it should be ok. I don't see any difference (except the time). It could be very easy to write mathematical problem. I haven't read all the problems but I like all I've seen.)

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

Количество символов '(' должно равнятся количеству символов ')' для каждого i или для всей строки?

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

    Равняться для всей строки.

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

    Очевидно для всей строки, потому что нельзя составить правильную скобочную последовательность нечетной длины

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

Interesting question: How can somebody get runtime error on Div2-C??

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

    Well, for example non-terminated C-string, or too small allocated size for char buffer...

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

.

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

pretty hard!!! ( And challenging. )

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

Е-шечку никто не решил(

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

You really have to maintain server stability in the last 10 mins

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

Damn, failed on 47th test... Is there any way to download the tests to see what went wrong?

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

vishwacs111, thank you for hacking my C!

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

nice contest got +132 :D:D:D + hacked 5 users second problem in div2:D:D:D

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

У меня была рабочая версия задачи C, которую я не смог послать, потому что последние 10 минут сервер лежал. Оставлять этот контест рейтинговым — свинство.

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

Буду, вероятно, заминусован, но не могу не отметить, что авторы мудаки и задачи у них соответственные. Чем такое придумывать, лучше б вообще ничего не предлагали.

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

    Почему? Мне задачи показались нормальными.

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

      Во-первых, скачок сложности со 2 на 3 задачу. Во-вторых, слабые претесты допустили ситуацию, что кто-то исключительно на одних взломах обгоняет людей, честно сдавших 2 задачи. В третьих, из-за этих самых слабых претестов у меня упала 2я, что меня, конечно, слабо порадовало.

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

        бебебе

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

          На следующем таком же контесте не дадут сделать 12 взломов — по другому запоешь.

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

        Тащемта, согласен хотя бы с тем, что тест с 1000000006 можно и в претесты включить. Задача не такая уж простая, чтобы у работающих решений снимать баллы за такую фигню.

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

          Тащемта, а что тогда предлагается включать в (тесты — претесты), если не крайние случаи?

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

            У меня всегда находится, на чем упасть решению :D

            Но если серьёзно, мне кажется, обидно, когда это последняя задача из тех, которые вообще решило больше 30 человек, и она накрылась на вычислениях по модулю (которые ведь являются по сути лишь костылём над задачей для обрезания BigInt'ов, а не частью задачи).

            Конкретно здесь было и КМП и не слишком тривиальная динамика. Т.е. было, на чём свалиться решению, прошедшему претесты. Если так хочется, чтобы участники на чём-нибудь свалились, можно было второй тест не делать тестом из условия. Я уверен, он пообрезал частных случаев поболее, чем -1 по модулю MOD.

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

    И чем же Вам авторы так не угодили?

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

No luck — just skill

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

man i am going down and down and down need to come up

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

what is the difference between

long long ind = lower_bound (x2.begin(), x2.end(),i)-x2.begin(); if(x2[ind]>i){ind = ind-1;}

and

long long ind = upper_bound (x2.begin(), x2.end(),i)-x2.begin(); ind = ind-1;

?

Second one passed,first one didn't. I was trying to find largest element less than/equals to i in vector x2

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

I never understand div 1 B problem statement, could someone explain it?

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

What's worse than both your solutions failing? Your friend dropping to div-2 for 1 point.

1699 Rating! — http://codeforces.com/profile/rsunny rsunny next time macha!

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

    Haha yeah I dropped to 1697, thats mighty close too :D

    Btw cheers! We're both aspiring Indian coders!

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

This contest was excellent!!!

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

Объясните кто-нибудь почему в Div1C матожидание = 4,465.

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

    Посчитаем вероятность того, что максимум равен какому-то значению.

    Максимум точно не может быть меньше, чем 3.

    Максимум равен 3 в том случае, если первая рекомендация не выполнена (это 0.5) и среди рекомендаций 2, 3, 5 не выполнено хотя бы две, вероятность этого 0.25(1 - 0.8)(1 - 0.9) + (1 - 0.25)0.8(1 - 0.9) + (1 - 0.25)(1 - 0.8)0.9 + (1 - 0.25)(1 - 0.8)(1 - 0.9) = 0.215, итого с вероятностью 0.5·0.215 = 0.1075 значение максимума равно 3.

    Максимум равен 5 в том случае, если среди рекомендаций 1, 2, 3 и 5 выполнено ровно 3: (1 - 0.5)·0.25·0.8·0.9 + 0.5·(1 - 0.25)·0.8·0.9 + 0.5·0.25·(1 - 0.8)·0.9 + 0.5·0.25·0.8·(1 - 0.9) = 0.3925.

    Максимум равен 6 в том случае, если выполнена каждая из рекомендаций 1, 2, 3, 5: вероятность этого равна 0.5 × 0.25 × 0.8 × 0.9 = 0.09.

    В остальных случаях максимум равен 4: это 1 - 0.1075 - 0.3925 - 0.09 = 0.41.

    Считаем матожидание: 3·0.1075 + 4·0.41 + 5·0.3925 + 6·0.09 = 4.465.

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

dp'licious div 1 contest!

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

Couldn't code problem d in time and my a was buggy. I almost fell back to div2 LOL

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

What did just happen here? AC: 9122599 WA1: 9122592

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

http://codeforces.com/contest/494/submission/9117612

For some final tests, I think this should get WA.

Output

999999958.3334586600

Answer

1000000003.315735409

Checker comment

ok found '999999958.3334587', expected '1000000003.3157355', error '0.0000000'

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

    Check this. Relative error is OK.

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

    That's because the relative error is less than 10 - 6.

    I also noticed that for large inputs, even the trivial lower bound could get AC automatically... I wonder how the submissions could get affected by higher precision (and smaller ai-s).

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

judging system of codeforces is quite bad. Because in the contest time judges should provide all input/output testcases. When a coder gets Pretest Passed, he moves to other problem, but after contest he sometimes notice that the solution was wrong. If in the contest time he gets Wrong Answer he could get Accepted.

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

    How about hacks?

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

      No problem about hack. But judges should provide strong cases for every problem. After getting hack coder tries to solve it again in contest time.

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

        If they provide all testcases when judging during a contest, nobody would be able to hack other peoples solution. You have to either figure the tricky testcases on your own or pray someone will hack you. This makes contests more exciting.

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

    I can't solve a problem, so the judging system is bad.

    Cool story, bro.

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

    If for every code judge system tests all tests during the contest judging process will be too slow and it make some troubles during the contest,

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

Finally I reached EXPERT!!! :D

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

tourist 's 100th round!

Took off 2 zeros for rank!

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

Hamed and Malek two familiar people for inoi people

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

Iran contest is too hard..555555