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

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

Всем привет!

Совсем скоро, 7 июня в 19:30 MSK состоится Codeforces Round #187, автором которого являюсь я. Это мой седьмой раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald), Роману Фурко(Furko) и Аксенову Виталику(Aksenov239) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Разбор.

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

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

good luck everyone

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

have fun everyone

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

0

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

hopefully it won't be my third consecutive unrated round :D

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

I hope problem statement to be short & easy to understand like your Post :D

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

7 июня, 7 раунд Сергея, 18**7** контест, и при том мой день рождения(1**7** лет)! Надеюсь сегодня контест будет удачный)

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

Sereja, что ты делаешь?!...прекрати!

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

Я просто оставлю это здесь.link

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

Seventh and not the last... very impressive!

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

Sereja must be the author of the year

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

Всем Удачи и вердиктов "Претесты пройдены", а позже "Полное решение", с ПЕРВОЙ попытки!

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

Hope Djo vs Nadal will end before the contest

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

i'll try my best to reach blue!..bless everyone!..Hope everything goes smoothly

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

Какая разбалловка?

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

Do you really think that the problem statements are written in English?! I can hardly interpret what's written!!!!!

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

Почему в D неправильно делать поворот плоскости на 45 градусов, а потом искать центры масс по X и по Y и считать ответ?

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

    Казалось бы, причем тут центры масс? Скажем, во первый семпл добавим точку -1, 3. Центр тяжести сдвинется, а при этом в правильном ответе — те же 2 прямые

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

    Поворот делать правильно, а при чём тут вообще центр масс?

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

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

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

Тест 4 по С?

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

    У меня, например, искало ответ для всех подпоследовательностей, а не только для неубывающих.

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

Никак не пойму, что такого в 4-ом тесте С (див 2), что почти все, кто валятся валятся на нем.

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

    Если мне не изменяет память, то там было переполнение.

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

Really good and fast system test tonight!

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

After seeing others' submissions to div2 A, I figured out the solution immediately while still couldn't connect the solution to the obscure problem statement.

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

    I understood the statement's intention finally.

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

      Need some help here. Would someone explain the test case 4 for div2 A? Thanks.

      4

      2 3

      1 772

      3 870

      3 668

      Correct answer: 2

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

        using bottle 1, which is (2,3) he can open bottles 3 and 4, which are both of brand 3. this is because bottle i can open any other bottle j if b[i]==a[j].

        so the bottles 1 and 2 are left unopened. hence answer = 2

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

        You can use the 1-st bottle to open bottles of brand 3 (3rd and 4th). The 1st and 2nd bottles can't open. Answer:2 .

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

Did someone proofread the problem statements? At least I made many assumptions for solving D1-C and I can't understand D1-A at all before reading the example...

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

    "Pay attention to the analysis of the first test case for a better understanding of the statement."

    YOU DON'T SAY!!!

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

А в E подразумевался квадрат, или что-то более разумное?

На плюсах, то я в 2 секунды запихал, а вот то что это можно сделать на Java я не верю.

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

    Так-то капец. Дожили. 2,5 миллиарда операций укладывается в тайм-лимит 4 секунды. :)

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

      2.5 миллиарда бывают разные. У меня это просто проход по массиву подряд, с операциями прибавление + 2 присвоения на элемент. Все в кеше, так что понятно, что это очень быстро. Но пришлось действительно пихать. В частности делать все в одном массиве, чтобы по памяти идти подряд. В двух работало больше 10 секунд на сервере.

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

Быстро, codeforces радует :)

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

I am not able to find test case on which my code for Div 2 A was hacked. Could anybody help ??

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

    I am also doubtful.The first line contains integer n (1 ≤ n ≤ 100) — the number of bottles. I am bit confused by this line .. How come the answer for test case

    2

    1 1

    1 1

    isn't 2 if there are 2 bottles .

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

    Could you provide a link to your submission which was hacked.

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

Can anyone tell the intended solution for div2 D ??

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

    you can calculate the max match between a{1...a_size} and c{i...c_size} in advance,record the match times and the c's very last match position . then do b times and count the occurrence of c . finally divide by d is the result . sorry for my bad english.

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

      i don't exactly understand what you mean by "max match".

      I think it'd be better if you give some example.

      Let a = "abab" and c = "baa"

      Can you explain how you operate, choosing suitable values b and d ?

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

        let [a,b] = ["ababab",3] and [c,d] = ["baa",2] .

        we preprocess NextMatchPositionOfC[1...c_size] and OccurrenceOfC[1...c_size] .

        1. for a[1...6] = "ababab" , c[1...3] = "baa" , we can get NextMatchPositionOfC[1] = 2 && OccurrenceOfC[1] = 1 . (a' = "baab")

        2. for a[1...6] = "ababab" , c[2...3] = "aa" , we can get NextMatchPositionOfC[2] = 3 && OccurrenceOfC[2] = 1 . (a' = "aaba")

        3. for a[1...6] = "ababab" , c[3...3] = "a" , we can get NextMatchPositionOfC[2] = 2 && OccurrenceOfC[2] = 2 . (a' = "abaab")

        then we can set a pointer ic = 1 and do loops for b times.

        { MatchTime += OccurrenceOfC[ic] , ic = NextMatchPositionOfC[ic] . }

        we can get MatchTime = 1 + 1 + 2 = 4.

        finally MatchTime / d = 4 / 2 = 2 is the result .

        and i think this problem is just a deformation of http://poj.org/problem?id=1936 .

        hope this helpful .

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

wow system testing and rating updates completed really fast today! :) thanks Sereja!

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

I read the problem statement the negligence led me Div2 A FST it. Next must not commit such a mistake!

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

задача B DIV2 много кто на 11 тесте превысил лимит времени,мало того что код написать,так и надо над оптимизацией думать...хотя логика верна

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Мало того, что код написать,так и надо над оптимизацией думать
    

    Как и в любой другой хорошей задаче :)

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

      будем дальше тогда учиться,хорошая задача — это как раз необходимо для развития

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

hope the tutorial will be published soon.

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

I spend much time on C's debug, but I couldn't... And my C failed because of the matter of modulo, my solution output -(1000000007-x) instead of x... So sad...

Anyway, thank you for interesting problems!

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

Будет ли разбор?

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

Admin , look at both of the submissions . They appear to be almost same .

http://codeforces.net/contest/315/submission/3841333

http://codeforces.net/contest/315/submission/3841920

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

    I would like to clarify that I code a lot of times on windows and use Ideone for the purpose . So,its very possible that the code is manipulated not by one but a lot of people and since in this case the time remaining was very less , I forgot to make it a private. It won't happen from next time I will take care of that .

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

      Can you also explain the following:

      1. How did he submitted his code 7 minutes before you?

      2. How come that, while you did not use any marco for your previous submissions, for problem C you suddenly start using marcos in a style that is very similar to the coding style of aman181993's? From the submission history one can see that aman181993 started using F(i,a,n), FD(i,a,n) all the way back from May 19.

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

Why this solution has been skipped?? http://codeforces.net/contest/315/submission/3837849

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

Problem D was the best in div2

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

разве это решение нельзя сломать на ТЛ http://codeforces.net/contest/315/submission/3840568

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

It seems that both AC solution of Div 1 — E is O(n^2). It should not have been the expected solution.

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

    It is expected solution. Its O(N^2), but to solve this task you should make many optimization that makes O(N^2) --> O(N^2 / big const, near 32).

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

When writing English version of announcement, please link to codeforces.com for the tutorial -- codeforces.ru automatically changes language to Russian, which is somewhat annoying. But anyway, good round!

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

Раунд был достатычно интересным. Спасибо!

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

Can anybody tell me how to solve the pro.E of div1

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

Where can I find a discussion forum for this topic? I wanted to see the solutions for this Codeforces Division Match. :)

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

My submission for div1 — D ( 4401712 ) passed lots of test case where it should not:

ok found '85784037.0000000', expected '85784036.5000000', error '0.0000000'

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

    The relative error here is less than 1e-6.

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

      The correct relative error is 0.5. My program always output an integer where it should not.

      Edit: Seems like I had some confusion between relative & absolute error. But using relative error in this problem doesn't make sense to me. The answer is always N or N+0.5 (where N = integer). Allowing relative error < 1e-6 may allow incorrect submission to pass. E.g. If I used different algorithm for small N, my wrong solution would have passed.