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

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

Всем привет.

В воскресенье, 7 сентября, в 19:30 по московскому времени состоится очередной, 265-ый, раунд Codeforces. Задачи подготовил я, Михаил Тихомиров. Раунд пройдет в обоих дивизионах.

Для раунда будет использована стандартная (не динамическая) разбалловка.

Div. 1: 500-1500-1500-2000-2500

Div. 2: 500-1000-1500-2500-2500

Хочу поблагодарить Геральда Агапова (Gerald) за помощь в подготовке задач, Филиппа Руховича (DPR-pavlin) и Александра Машрабова (map) за тестирование раунда, Марию Белову (Delinur) за перевод условий на английский и Михаила Мирзаянова (MikeMirzayanov) за создание и поддержку проекта Codeforces.

Это мой третий раунд на Codeforces, и я постарался сделать задачи максимально интересными и разнообразными. Желаю получить удовольствие от раунда. Удачи! =)

UPD: раунд завершен. Всем спасибо за участие, надеюсь, вам понравились задачи.

Поздравляю победителей раунда:

Div. 1:

  1. tourist
  2. Petr
  3. rng_58
  4. al13n
  5. ecnerwala
  6. qwerty787788
  7. marek.cygan
  8. KADR
  9. Merkurev
  10. hos.lyric

Отдельные поздравления simonlindholm, единственному участнику, кто справился с самой сложной задачей Е!

Div. 2:

  1. matthew99
  2. acrrca
  3. ccdream
  4. Chameleon2460
  5. newSolars

Разбор.

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

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

Краткость — сестра таланта, да? ;)

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

Your next contest after Three years....!

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

I wish to see more Math.:)

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

I wish to see more Math.:)

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

    I think you'll get what you want.

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

      :)

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

        I hope for no math.

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

          Why both hope for math and not math problems got negative votes?

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

            Because it's spammed on each contest announcement?

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

              Then explain positive votes in this comment Edit: it's no longer up-voted (but it was +13)

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

                Oh, I hadn't downvoted that one. Fixed.

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

                  I meant if it's really spam why people in codeforces up voted that comment ? Edit: it's no longer up-voted (but it was +13)

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

                  Dunno, I provided a reason for why downvote (there are dozens of short comments like "I hope there'll X" and "GL&HF" and "thanks for X", and I stopped being interested in reading them after the first 100), not why upvote :D

                  CF voting is really strange, I have no idea why it behaves the way it does. Sometimes I'm thinking the answer could be 42.

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

                  @Xellos I will keep that in mind from next contest.:)

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

                  Hey man, I just keep repeating that because this site is not named "mathforces", and others keep making "Hope for math!" comments. (!!)

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

                  Oh yeah, I forgot that the optimal method to reduce the "Hope for math" spam is to add "Hope for no math" spam.

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

                  While speaking about math, have you noticed that the absolute value of your contribution is a perfect cube? Also the absolute value of mine is a 4th power added to 1 :o. It is a very interesting topic :o.

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

                  Here , I have made the absolute value of your contribution a 4th power added to 3 now :D

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

                  Actually, it is the absolute value of a 4th power added to 3 :D.

                  Also your contribution is a fourth power :o.

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

    why? I think Math is difficult

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

    Math is beatiful guys and haters shut up xd. If it weren't for math, there won't be competitive programming xd.

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

I hope I can do better!

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

I m going 2 rise

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

I think this announcement sets the record for the shortest announcement for a contest ever. Keep It Short and Simple! :)

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

Wish to learn new concepts ,new tricks and new things :)

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

Это будет мой первый раунд:)

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

    Твой рейтинг после раунда будет в районе 1350-1450

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

Жаль, что в 8 вечера наши (армяне) против Дании играют.

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

Why is everyone in a hurry?! Contest's blog 5 days before contest?! Once they posted it a few hours before the contest :D Oh, and no thanks to Gerald or anybody else?! What an unusual contest blog...

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

It is my first time to compete, I hope i can solve at least once.

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

Good luck and have fun! scores up, up and up!

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

How to register for the contest ? I can't find any link for registration

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

Long Waiting For this contest

Good luck everyone

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

Посмотрел на автора и сразу вспомнил ЛКШ!

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

cheer up!

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

First time above 1700 and I have a question regarding divisions. My friends take part in Div2 but I can't Register to Div2 due to 1700+ rating.

Will I be able to join as virtual something when Div2 starts without ranking or I must register in Div1?

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

What type of scoring will be use ?

Good Luck to everyone

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

Всем удачи на контесте.

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

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

    Почему кому-то не понравился контест? Уже ведь ради задачи А решать стоило, там ведь такая прикольная идея! Автор картинки наверное просто не умеет решать красивые задачи, ему наверное лишь бы какой-нибудь дфс баянный загнать!

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

      Почему если китайский контест — то это обязательно значит "не понравился"?:) Я согласен с vitux, по ощущениям — контест китайский. Не хороший, не плохой, а именно китайский:)

      Кстати, для меня полными боянами были В и С, на идейном уровне — еще и D. А "баянность" задачи сильно коррелирует с оценкой ее красоты?

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

        Буду благодарен, если найдете ссылочки.

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

          Прошу прощения, не хотел, чтобы это прозвучало как какое-то обвинение:)

          Если вдруг вспомню/увижу, то дам знать:) Но вряд ли. А пересматривать несколько тысяч задач мне, скажу честно, лень) Да и смысла в этом нету.

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

            Нет, мне правда интересно, где эти задачи могли быть, потому что я их нигде не видел. =)

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

              Из на тему/похожих/с общими чертами — задача "проверьте, образуют ли данные точки куб" более-менее популярная. Хотя и не настолько, как "проверьте, образуют ли квадрат", но эту часть решения В я назвал бы известной и сугубо технической. Конкретно такую не видел — видел задачу, где дано несколько точек, и нужно сказать, можно ли из них выбрать 8 так, чтобы получился куб. Вероятно, на каком-то из зарубежных online judge вроде TJU/POJ/ZOJ/HDU. Идея была та же — перебор проходил.

              По поводу С — в голове крутится, что где-то видел даже конкретно такую. Понятия не имею, где именно:) А общая идея "хранить остаток и длину" вроде бы далеко не новая. Только обычно ее дают в виде единичных запросов изменения, или вставки цифры, или еще какой-то такой ереси. На одном из полуфиналов было, в ПЗ когда-то было... Иногда как-то усложняют, и вместо остатка всей строки дают запросы в стиле "сколько подстрок...".

              За А спасибо:) Никогда раньше похожих не видел. Ниже пишут, что не новая — надо будет разобрать общий случай в свободное время)

              Ну и жду разбор, интересно узнать, вдруг у D есть красивое математическое решение.

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

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

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

How to solve C ? Any Idea ?

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

how to solve Div-1 B?

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

    Bruteforce, I think. There are 6 permutations for each of 7 point (you can fix the first), so it is 6^7 ~ 300k — fast enough.

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

      Or generate all variants for 3 points, build all cube and check points.

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

      And how do you check if it's a cube?

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

        I had an idea to calculate all pairwise distances for some fixed permutation (there are 28 segments in total) and sort them. Now, if first 12 of them are equal, next 12 are equal and last 4 are equal, it's a cube. But I didn't have time to code this solution and can't prove it

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

          i'm convinced this idea is correct, but i dont know why my solution 7712723 gives TLE!

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

            Because that's incorrect idea and obviously your solution is wrong. Also, your code-style is very dirty. Learn Math and don't ask stupid questions anymore.

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

              Lol, that's pretty rude. I'd ask you to learn some good manners first.

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

                Oh, I so ashamed...

                Один стою в белом пальто красивый.

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

            Map is not so fast thing:) Try to rewrite it without map, it should pass — my solution is basically same, but with vector&sort (7708825), and it works in 0.7 seconds.

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

      my solution 7712723 with the same idea TLEd! :(

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

      Could you please explain how we can fix one point if all of them probably were shuffled?

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

It would be great if you could write problem A shorter! At the first, I was confused.

Thanks!

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

How to Solve Div -2 C ?

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

    they key observation is that if we don't have any palindromes of length 2 and 3, then we will have no palindromes at all (other than single characters, ofcourse).

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

      How did you arrive at this conclusion? Have you solved a similar problem before or was it intuition or did you think of this during the contest?

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

        intuition. any palindrome of length n > 2 has a sub-palindrome of length n - 2 as its substring (u can get this by removing the first and last characters).

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

        easy to note that we can build palindrome by add same character to begin and end of another palindrome. just consider the case of odd and even length, so we could just check every 2 and 3 consecutive letters

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

      I made this observation during the contest but do you still have to loop over all possible strings after the input?

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

      Can u explain ur solution !

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

    Suppose you have a palindrome of length at least 4. Delete the start and end characters. Now you still have a palindrome. Thus you only need to consider palindromes of length 2 or 3. Find the rightmost character that you can increment to something satisfying s[i]!=s[i-2] && s[i]!=s[i-1] (within the bound of p of course), then fill the remaining letters with the "smallest" letter possible.

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

I got my first hack on codeforces! I tried a little different strategy this round. I solved B and A quickly and then tried to solve C within the first hour. But I couldn't. Nevertheless, I spent the whole of the second hour trying to hack but was not very lucky until the last 10 minutes. About 7 minutes before the end of the contest I managed to hack a solution!

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

Nice problems!

How to solve D? I was struggling for quite a while, but didn't come up with anything faster than 100 FFTs (or 2 FFTs, but for vector with size 107) :(

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

    My solution relied on the fact that we only need 1e-9 precision. Basically, with probability 1-eps we never get to very high levels.

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

Понравилась задача В. "Пиши, деточка, if'ы, да побольше-побооольше".

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

    Хм, зачем там if'ы? Объявляем одну из вершин началом координат, перебираем единичные векторы-рёбра куба и порядок координат для них (C73 * 3!), дальше просто паросочетание. Или я чего-то не понимаю?

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

      Круто. А я перебирал с отсечением 6^8 вариантов, и те которые выживали, проверял тоже на паросочетания, но кучей if'ов, чтоб понадежней было :)

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

      Как альтернатива паросочетанию — если рассмотреть все возможные отрезки между парами вершин этого куба, и принять самый короткий из них за Х, то у нас должно быть ровно 12 отрезков длины Х, ровно 12 отрезков длины 2*Х и ровно 4 отрезка длины 3*Х.

      Upd. Cпасибо Lo_R_D за замечание, рассматриваем не длину отрезка, а квадрат длины.

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

        По-правка: у тебя рассматриваются отрезки в квадрате.

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

      Можно не перебирать, а взять 2-4 векторы в порядке длины. Вместо паросочетания можно проверить, что среди векторов есть все попарные суммы трех ребер и сумма всех трех ребер.

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

      Паросочетание здесь можно и за 4! искать, проблем с ТЛ не будет в любом случае.

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

      В теории можно было бы даже два единичных вектора перебирать, а для третьего перебирать только направление. Но на КФ нет __int128, а авторам захотелось координаты до 10^6 :(

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

I managed to find a suitable algorithm for 464C - Substitutes in Number, yet couldn't solve it because I couldn't read the input properly. I don't know yet what was causing the quite straightforward input code to fail... Here's my last failing submission : 7713194 If I add assert (c >= 0 && c <= 9); after line 43, the assertion fails...

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

This was a great contest :) Thank you for writing! I liked many of the Div 2 problems.

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

Первый раз в жизни решение C прошло претесты, но я уже без систестов знаю, почему оно завалится :) Контест великолепен, спасибо большое!

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

I have a feeling that a lot of A-Div1's will fail.

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

I see some hacks on div1-C, for example Merlininice has quite a few. How can a solution to div1-C be incorrect? It looks really straightforward.

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

    Are you now scared that yours too is incorrect?! :D

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

    Some people did not take the length by module, some took it by module 109 + 7 instead of 109 + 6.

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

      But why does one need the length at all?..

      I guess you're saying that people were computing "length of expansion of digit X" instead of "10 to the power of length of expansion of digit X"?

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

        Exactly.

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

        My solution got hacked also. It was totally a straightforward dp problem. I just couldn't figure out why it was giving incorrect ans. I thought keeping the length and exponent value would do the same thing but totally forgot that if I kept the length, I would have to do modulo 10^9+6 on the length according to FLT. If only I'd kept the exponent value instead :(

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

      10^9+7 instead of 10^9+6 ????
      problem statement say 10^9+7

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

        If we store just length, we're computing 10^len at some point. Using FLT, we can just compute 10^(len mod (10^9+6)) instead, so we can just take len mod 10^9+6 instead.

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

        One should use 109 + 6 in order to keep length. Because it is the period of pows (check little Fermat's theorem)

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

      some took it by module 109 + 7 instead of 10^9 + 6.

      do you mean that if I saved the length instead of power of 10 and make it modulo 10^9+6 I will get AC?

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

    Hey Petr, didn't you make a similar mistake (taking different value for MOD) in a past contest? I remember reading about it on your blog!

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

      If I remember correctly he made a missprint (10^9+9 instead of 10^9+7 or sth similar), not a conceptual mistake like the one mentioned above.

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

    so do ztxz16 and Kostroma.

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

I had this algorithm (which I did not implement) for solving 465C - No to Palindromes!. Is this a good approach?

Treat string as a number in base p.

Let left = 0 repeated n times
Let right = p repeated n times
while(left < right)
{
    int mid = (left + right) / 2;
    if(check(mid)) right = mid;
    else mid = left + 1;
}

The function check(x) tells you if x contains no digit > p and that it contains no palindromic substring of length > 1 (both of which can be done in linear time).

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

Not the contest that I expected and hoped... BTW, Palindromes are AWESOME! Why should somebody be bad with them?!

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

Потрясающий контест! От души спасибо авторам!

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

Here's a Brainfuck solution to problem A (reads and outputs as ASCII). The cells are divided into groups of two. The first cell of the group is 1 if the index is in range 0 to n and 0 otherwise. The second one contains input for that index — either 1 or 0.

The code:

>>,-                read n
[[->>+<<]+>>-]+     prepare cells of the second type
[<<]                go to start
>>[>,>]             read input
<<[<<]>>>           go to first value cell
[
    <<[->>+<<]>>    add values from last index
    >>              go to next cell
]
<[-<+>]<            if the index cell is 1 add to the result
.                   output result
»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Weren't E div2 — C div 1 pretests very very weak?

I see naive implementation solutions pass pretests!

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

I tried to hack this solution

by this case

2 0 0

but it gives me Unsuccessful hacking attempt

with this case variable pb will be used without initialization

how this solution pass my case ?

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

    pb will have junk value, but that would not contribute to answer, just that "break" will not be called.

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

How to solve div-2 D ?? I first tried to take all 6 combinations from 24 , that is 24C6 , clearly it isn't suitable !!!

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

When A,B are too easy and others are hard (div2), this will happen: I can see about 1500 rank difference between 2 users while both of them have solved 2 problems. The rank of the participants which solved 2 problems, starts from 400 and ends after 2000. This is a huge difference! I think this shouldn't happen.

Thanks :)

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

    In this contest, if you can solve only A, B which is common with Specialists and low Experts, your score will depend on your time, which isn't kinda bad. If you succeeded in solving C, or even D, E, those tasks will tremendously increase your rating because they are simply made for coders who has ideas and knowledge.

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

2:15 ночи (за 15 минут до начала контеста): "Не, бро, извини, мне так фигово, что я не смогу участвовать сегодня". 2:25 ночи (за 5 минут до начала контеста): "Мыться под холодной водой — вот мой выбор" — "Да, это выбор чемпионов". 5:15 ночи (после системного тестирования): "Нифига себе, возможный TL по D зашел, говнокод по C не упал, 16 место ёпт! Впервые решил 4 задачи! А я еще участвовать не хотел!"

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

    Этим комментарием заставил меня задуматься над тем, чтобы все же принять участие в Ice Bucket Challenge:)

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

    просто демон :-)

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

I misunderstood Div1-C problem statement :-( But problems are very interesting. Thank you for preparing this round :-)

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

Да ну вас, злые тесты по D div2, куб из одной точки тоже куб) На таком упало...

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

    Нужно внимательнее читать условие:

    Точки должны являться вершинами куба с ненулевой длиной стороны.

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

      Понимаю что надо внимательнее. это эмоции, из-за разочарования, что на такой ерунде упало.

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

For Div2, a and b was easy and c d e was hard. I have solved A and B but I got rank 1100... To many contestants solved just 2 problems and very big difference in same, two problem solvers.

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

Who else forgot to check if the cube side length is greater than 0? High five!! :'(

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

I got wrong for DIV 2 D , because I used float instead of integer while printing the cordinates , my programs prints the cordinates in exponent form in one of the test case and is judged wrong.

Did someone else also failed system test in this way before ? Link : 7710844

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

Предполагались ли в решении задачи D проблемы с денормализованными числами, или это я такой везунчик, что меня это затронуло?

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

    Не думаю, что мое решение предполагалось, но в нем нет никаких операций, кроме умножения даблов при добавлении к ответу.

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

      Я запустил твое решение на макстесте, и оно отработало 2100мс в запуске — видимо, тебе повезло на систестах :) А если сделать ифы, обнуляющие переменные, когда они станут меньше какой-нибудь константы (типа 1e-20), то оно ускоряется в три раза.

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

        Нет, я хорошо проверил на запуске и выставил константу 750 с запасом :) Во время контеста, если сабмит получает ТЛ, то он перепроверяется на отдельном ядре. Если же нет статуса ТЛ, то остается прежнее время выполнения (в таком случае на этом же ядре проверяются еще какие-то решения).

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

          Да, я не прав, я под g++ запускал, под студией, действительно, все хорошо.

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

      Я наоборот думаю, что именно оно и предпогалалось. А денормализованные числа там вылазят как раз из-за умножения чисел, меньших единицы. Добавил ровно одну строку if (f[j] < 1e-30) f[j] = 0; к твоему решению и оно прошло за 0.2с вместо 1.8с, как на контесте: 7714718.

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

    У меня ни в одном из решений такой проблемы не возникло, потому что у меня была единственная динамика — мат. ожидание ответа, а вероятности никак не использовались. Весьма неожиданный эффект.

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

Как решать Е? Я так понимаю, там нужно что-то быстрее, чем 100000MlogM/32?

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

    Видимо, решается так. Будем хранить числа в персистентном дереве отрезков. В каждой вершине будет хеш соответствующего ей подотрезка. Тогда чтобы сравнить 2 числа, нужно найти первый бит в котором они различаются и сравнить его в двух числах. Еще нужно уметь прибавлять к числу степень двойки. Для этого нужно находить для заданного бита предыдущий, который равен 0. Выходит, мы числа можем сравнивать за O(log(MAX)), где MAX — максимальный показатель степени двойки. Тогда сложность решения O(M * log(M) * log(MAX)).

    UPD: Конечно, нужно Дейкстрой искать ответ, просто вместо чисел будут деревья.

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

    Может я неправильно понял условие задачи, но что если предпросчитать 2^(x) динамикой и запомнить для каждого x целую часть и по модулю, а потом алгоритм Дейкстры за m*log(n)(может это не дейкстра, но он на основе set'a), суммировать путь будет не сложно(прибавлять целую часть и по модулю), а потом просто вывести ответ.

    UPD: понял ошибку

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

      Если (a + b) % MOD < c % MOD, то отсюда не следует, что a + b < c.

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

Why ratings update is delayed too much in codeforces after system test is finished? (while it's fast in topcoder)

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

    the relation between system tests and rating update is inverse. i don't know why .

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

    My guesses:

    System tests are delayed — because they need to add the newly added hacks to the final tests.

    Rating updates are delayed — because they are figuring out the cheaters in the contest.

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

Задача A сильно смахивает на эту: 196D - Следующая хорошая строка, только ограничения намного меньше. Это было сделано специально?

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

    Нет, случайно получилось. Прошу прощения.

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

      А ведь ты играл тот раунд, я помню :)

      Я сейчас скопипастил свое решение, поменяв 'z' на (char) ('a' + p - 1) и проставив d = 2, и получил Accepted.

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

        Ты помнишь, что я играл этот раунд два год назад? о_О

        Ну вот да, была опасность, что будет много копипаст решений, в том числе, чужих. Но как-то обошлось.

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

        "Играл" — лол)

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

          Так больше нигде не говорят, что ли? Все пишут и участвуют, и никто не играет?

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

            Я никогда не слышал. Я обычно пишу.

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

Good question, thanks ^_^ waiting for editorials...

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

Обновите рейтинг пожалуйста, завтра в школу просплю :(

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

"Editorial will be up in an hour or two" is a statement for Infinite Loop :P

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

"Editorial will be up in an hour or two." is a Infinite Loop statement.

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

Can someone give some hints for Div1 C?

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

div2 probC

int n, p;
cin >> n >> p;
char *data = new char[n];
cin >> data;

runtime error. changed to

int n, p;
cin >> n >> p;
char *data = new char[1010];
cin >> data;

accepted. life sucks :(

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

Looks like tests in Div1-B are weak — I mean overflow. I have just written an int64 solution, which use values like maxCoord^4 (euclid length of vector product). And it's full solution. Is it difficult to create test to crash this solution?

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

    I think technically you have calculated a hash of the vector's length (have calced it modulo 264) and then you are only interested if two hashed values equal or not, so it seems OK.

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

These submissions are very much alike, aren't they? This 7704944 and that 7706248 And this 7713468 and that 7713301 too!

I'm a policeman:)

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

Oh my rating :))

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

Огромное спасибо за такой прекрасный раунд!

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

very happy to get 284 point

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

can somebody explain div-1 C it is not so clear from editorial

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

    Didn't read editorial, but may be can help

    First of all, we can notice that after all transformation behind every digit will stay some sequence. Suppose we know these sequences for every digit [0..9], and for digit d sequence has length len[d] and value val[d]. Now, to compute result for input s, go though s and result = result * (10 ^ len[s[i] — '0']) + val[s[i] — '0'].

    Now we need to compute len[] and val[]. Let's use DP technique. Consider len[] and val[] calculated for some suffix of transformations queries [k..m-1]. How compute them for suffix [k-1..m-1]? Use similar ideas were used to compute result. Take query d->t, go through t and value = value * (10 ^ len[t[i] — '0']) + val[t[i] — '0']; length += len[t[i] — '0'];

    val[d] = value; len[d] = length;

    All these formulas come from Horner's method.

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

Country wise standings are updated. Sorry for the delay.

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

The contest & Codeforces both are awesome .. :)

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
»
15 месяцев назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Why my submission in queue for so long?