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

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

Привет всем!

Сегодня состоится 106-й рейтинговый раунд Codeforces для участников Div 2. В нем могут принять участие все желающие. Вам представится возможность вместе с Петей отдохнуть от родителей, узнать несколько интересных фактов о марсианах и конечно порешать, как мы надеемся, интересные задачи для вас.

Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы выражаем огромную благодарность за помощь в подготовке раунда и переводе задач Артему Рахову (RAD), Михаилу Мирзаянову (MikeMirzayanov) и Марии Беловой (Delinur).

Распределение баллов за задачи: 500-1000-1500-2500-2500.

Всем удачи и высокого рейтинга!

UPD: Разбор задач

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

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

Люблю контесты) Без них мир бы стал унылым) Спасибо!

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

I love this normal Score distribution, last contest is really unfair ...

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

А когда уже будут Div1 раунды?

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

    думаю, фиолетовым и чуть-чуть желтым не стоит возмущаться, так как они врядли решают больше 3х первых задач

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

      Видимо, если бы не Див1 раунды, каждый был бы максимум "фиолетовым и чуть-чуть желтым".

      А так Див1 раунд позволяет "фиолетовым и чуть-чуть желтым" доказать, что они нечто большее.

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

      Прошлый раз, я решил всё за 1.15. Всё зависит от задач.

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

        Видимо он имел в виду первые 3 задачи div-1.

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

    Насколько я понимаю, на Codeforces сейчас очень странная ситуация с раундами. Только я знаю о 4 или 5 группах людей которые что-то делают, а я явно знаю далеко не о всех. При этом видимо нет ни одного раунда в более-мене готовом состоянии.

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

Может хватит присылать уведомления в 4 ночи/утра? :-)

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

    Их вам приносят и отдают лично, и это вас будит? =)

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

      Приходит на почту письмо, от которого реагирует телефон/будильник. И да, будит.

      Гораздо полезнее отправлять письма в момент начала регистрации: и не рано, и зарегаться не забудешь.

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

        а если регистрация начинается в 4 ночи/утра вы опять попросите что-то поменять?

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

          Зачем вы усложняете мою простую идею?

          Вот как будет регистрация с 4 утра, так и рассылку будем делать после её открытия, в те же 9.

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

            Выключи спам-рассылку и спи спокойно!

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

      daftcoder дело говорит!

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

good luck everybody

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

жадность по С проходит?

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

Скажите, пожалуйста, почему одно и то же решение в g++ даёт TLE, в то время как в Visual C++ заходит? UPD: Имеется ввиду задача B.

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

    Да чёрт возьми! Почему на 14-й тест ("0000P:0000E") локально ответ правильный, а на сервере ВА?

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

    Ясно, возвращается мусор. Прошу прощения за засорение комментариев.

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

Кто-нибудь взломал что-нибудь по А-С?

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • А: у одного было не понятно что, по идеи должно было уходить в RunTimeError, но 2 взлома прошли без успеха
    • Б: много ошибок на вывод -1
    • С: сортировка пузырьком
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    в моей комнате был взлом B

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

    4 взлома по А: 12 1 1 1 1 1 1 1 1 1 1 1 1

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

    Можно было ломать B на том, что некоторые проверяли системы счисления только до 35.

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

      ух е-мое... как я про это забыл... столько взломов было потеряно =(

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

    3 взлома по B: ZZZZZ:ZZZZZ, у многих было переполнения int-a при проверке систем счисления до 100.

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

    а я так удачно взломал С, сам не ожидал: начал ломать на быстрой сортировке, сгенерил 10^5 чисел, неверный тест, смотрю, числа до 10^4, а у меня числа от 1 до n, решил на 10^4 чисел попробовать, подумал что успет по времени, но решил рискнуть... по времени все ок — но ва, повезло однако)

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

Рассудите правильно, в задаче Е написано: "Более формально, марсианин выбирает четыре числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ n) и открывает все глаза с номерами i такими, что a ≤ i ≤ b или c ≤ i ≤ d. После того как марсианин открыл нужные ему глаза, он читает все видимые символы слева направо, получая тем самым какое-то СЛОВО.". У меня в голове только один акцент, на это "слово", т. е. дальше я читаю Выходные данные, где написано: "количество различных красивых СЛОВ", но где он возьмет эти слова, если перед глазами у него слово, мм?

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

    выбирать a,b,c,d он может по разному, получая соответственно разные слова

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

Подскажите идею динамики в D?

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

    я написал [L,R] динамику, еще 2 параметра: цвета на концах слева и справа

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

I like the problmsets, thank you, Gerald NALP and Polichka. Wait for the editorial.

How to solve problem D and E? Would someone give me a hint? Thanks.

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

    D: f(i,j,x,y) = number of possible coloring sequence i..j, with i having color x and j having color y

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

      How to deal with the conditions? condition 2: A matched pair can have exactly one color. condition 3: No two neighboring colored brackets have the same color.

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

        In short: when you found some neighbor brackets, check them. When you found 2 matching brackets, check them.

        A bit more details (I may forgot some cases): When i and j are matching brackets, f(i,j,x,y) = sum( f(i',j',x',y') )

        --> you consider x & y, x & x', y & y' if they satisfies conditions

        When i and j are not matching brackets, f(i,j,x,y) = sum( f(i,j',x,x') * (f(j'+1,j,y',y))

        --> you consider x' and y' if they satisfies conditions.

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

    for D, my idea was a DP. Scan from left, chose matching brackets. Color them in colors which are allowed, Now rest of string are divided in two parts. Solve them recursively.

    Example : (()()()())()()()()(()) gets divided into ()()()() and ()()()()(())

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

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

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

    Аналогично. Только совсем такое же самое решение ведь не даст отправить — я добавлял пустую строку.

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

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

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

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

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

Как такое теоретически может работать? Динамические массивы инициализируются неинициализированой переменной.

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

this contest I have the same problem, as last div2: after I submit my hack, nothing happens, and even page doesn't reload, but hack is submitted well

Firefox 10.0, Ubuntu 11.10

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

    Same here (Firefox 11.0 beta, Windows 7).

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

    I failed to submit solution to A at the first time, i.e. I did submit but it seems the server didn't receive it.

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

Most points from hacks in this round (800)? =D

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

    You were lucky with the room.

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

      Really? I see 10 (more than my successful challenges) unchallenged solutions for problem 2 which failed the system tests (including yours) in your room =)

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

        You are right, I'm just kinda dumb :\

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

          Hey, I didn't mean it like that =/ Also, there were 6 solutions that failed system tests in my room, so I missed a large number of them, I can say I had some luck to have 14 wrong solutions in my room, in that specific problem.

          Btw, at first I submitted a solution that gave the wrong answer for 0:10 but it passed pretests, that's why I managed to make so many hacks, because I knew where to look for a specific mistake =)

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

            No, I'm seriously, also, I failed A and B because of time pressure.

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

              Yeah, that happens. It's important to keep calm to make sure we don't slip on the "easy" problems.

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

    What tricky cases (not covered by the pretests) were there in B?

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

      00:10

      Not a few people overlooked the fact that the maximum possible base is 59.

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

      I did all my 8 challenges in problem B, the most common one was 0:10 for people that output -1 when it works for base 36 (or some other base < 60). There was one person in my room that checked minutes <= 60, that wasn't covered in the pre-tests either.

      EDIT: evima beat me to it =P

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

отличный раунд (хоть я и посвятил его взломам). отличные задачи. спасибо автору!

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

Контест непройденного финального тестирования

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

можно было в Е и не включать в претесты случай, когда одна из красивых строк длины 1. было бы весело :)

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

Two bugs: 1. After hacked i got javascript alert "Undefined" instead of "your solution have been hacked" 2. When i tried to hack other solution nothing happened after giving input and after 10-15 seconds it showed "the solution have been hacked or resubmitted", later in hack page i've seen that my hack was successful.

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

    I experienced the second bug twice. In my case, the first hack was successful, but the second one was ignored (someone was faster).
    I got the same message "the solution have been..." regardless of whether the hack was successful.

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

    I got bug1 too. It happened to me last round too I posted it on my blog and nobody replied to me and now same problem still exists.

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

BTW, there is an O(n log n) algorithm for E. I see that most passed solutions are O(nm). Waiting to see which one is in the editorial ;)

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

    Can anybody please tell more about your O(n log n ) approach for E ?

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

      Let me sketch both approaches.

      Let's call the long word s. For every short word w: we are to say whether there is an i such that w[1..i] and w[i+1..end] both occur in s, and w[1..i] occurs before w[i+1..end] (so that they don't overlap). It only makes sense to consider the leftmost occurence of w[1..i], and the rightmost occurence of w[i+1..end]. So we are interested in the values f[i] and g[i], where f[i] is the position of the leftmost occurence of w[1..i] in s, and g[i] is the position of the rightmost occurence of w[i+1..end] in s. Once we have f and g, we can easily check whether there exists an index i such that g[i]-f[i] is large enough (larger or equal to i, I think). And if we have a method of computing f, then we can use it to compute g (it's pretty much just f for both strings (s and w) reversed). So we're left with how to compute f.

      The O(nm) approach: search for every word w in s, using KMP. During matching, we virtually get the f[i] array as a byproduct (this is clear if you know how KMP works).

      The O(n log n) approach: we use a Suffix Array for s (and s reversed to compute g). There are fast algorithms for SA construction (even linear-time). We also precompute a Range-Minimum-Query structure for the SA. Now how to compute f: for every prefix (starting from i=1), we find the range [a,b] such that sa[a..b] corresponds to the indexes in s which begin with w[1..i]. We compute this range from the previous one using a binary search. We then run an RMQ query on sa[a..b] to find the minimum index (which is the f[i] that we want).

      The details can be seen in my solution ;)

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

    You must have come from a parallel universe. Most accepted solutions I saw so far has O(M+N) complexity

    Edit: Sorry, I miscalculated :(

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

    suffix array?

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

    O(N*logN) is also not a feasible solution since you HAVE to examine the words. So it is at least O(N*logN + M) or more likely O(N*logN + L), where L is the sum of characters in all M words :) (yeah, I know M is usually much smaller than N*logN, just making a note). My solution uses hashes instead of Knuth-Morris-Pratt and also has time complexity of O(N * M). To be honest I'm also curious about the logarithmic solution.

    Also, if you use suffix array and then do a binary search in it for each word wouldn't you get time complexity of O(N + M * logN * 1000) or something?

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

      Yes, my algorithm is actually O((n + L) * log n). I'm just treating the value in parentheses as n, since in the problem, L is also <= 100000 ;)

      The algorithm can even be made linear-time using very advanced techniques. Not that it would run faster ;)

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

Задача B почему на тест "0:1N", ответ "23 24 25 26 27 28 29 30 31 32 33 34 35 36 37" — неверный? в тест кейсах ответ "24 25 26 27 28 29 30 31 32 33 34 35 36" не догоняю...

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

    N = 23 -> минимальное основание = 24

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

    Потому что основание системы счисления должно быть строго больше самой большой цифры(а N = 23)

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

    Я дебил просто... в алфавитной строке пропустил 'J' -> и у меня N = 22... UPD: и это закосячилось только на 63м тесте... кто бы мог подумать...)

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

deleted

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

Y U NO HACK ME :(

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

Thank you to the codeforces team for that contest. This contest has very good questions and very well pretests.

»
13 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится
Two complaints:
1. Why Am I getting logged out again n again?.
2. Problem C, was not good. Any idiot can also guess that answer without proving.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi...my submission ID for problem B is 1168221. My program gave correct output for 1st pretest on my system and also on Ideone.com but it is judged wrong on pretest 1. It is giving an additional output of 23 in the end. Please resolve the issue. :( :(

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

кто-нибудь может подсказать почему в VS у меня ко второй задаче ответ верный выдает на 11 тест, а тут нет?

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

игнор

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

@admin . Hello, My submission for Problem B whose id is 1167928 gives correct answer for pretest 1 on my system as well as on ideone.com. My my submission has been judged to be wrong on pretest 1 itself. On codeforces for pretest 1 it outputs an extra 23, but 23 is not printed for the same input on my system and not even on ideone.com. Please look into the matter ans resolve the issue.

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

I got Judgement Error on my first try (1166157) of 149C - Division into Teams and after I submitted again the same answer, the two submissions were judged as Pretests Passed and I got a -1 because of the resubmission. Can anyone fix the score please?

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

Марсианские часы: 0000F:0002G

Ответ: 17 18 19 20 21 22

Почему 22?

G = 16 2 = 2; 2G = 22*2+16 = 60

22 не подходит!!!

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

    это ваш ответ. ответ автора на этот тест

    17 18 19 20 21

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

      Ой, извините перепутал строчки) И знаки в 2-х местах) Эхх внимательнее надо быть в следующий раз)

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

@admin:My submission id : 1168245 : It is failing for Pretest1 for Problem B. I am getting correct answer on my machine (using g++ compiler) but when solution is submitted, '23' is additional printed in codeforce's compiler resulting in wrong answer of pretest 1. I see same thing has happened to other person also, who have complained in this forum. Is there bug in codeforce's compiler.Please check

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

    I think it caused by roundoff errors and/or c++ optimization. Those who complained this problem in the forum use the cmath function pow(double,double), which can cause roundoff error in some environment, even though the parameters are integers.

    And, when I ran dragonfire's code with some additional std::cout for debug, then extra '23' is disappeared (see my submission: 1170942).
    This is sooo strange, but probably it suppressed the compiler optimization and the calculation became correct

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

What's the proof that makes the solution of taking the odd indexes in a team and the even in the other -after sorting the numbers- work in problem C?

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

    Let a1 >= ... >= an. Then the difference between teams' strength is a1 — a2 + a3 — a4 + a5 — a6 + ... <= a1 — a3 + a3 — a5 + a5 — a7 + ... <= a1.

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

When will the editorial be available? I'm in very need to it :(

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

Is it possible to arrange some contests on weekends? Looks like the upcoming ones are either on Friday or Monday. Thanks.