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

TopCoder Single Round Match 523
Автор NALP, 13 лет назад, По-русски

Наконец, открылась регистрация на SRM 523. Напоминаю, он начнется в 21.00 по московскому времени


Для вашего часового пояса смотрите сюда.

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

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

Самый эпичный даблпост за всю историю CodeForces :) Double-blog-post.

Скрывай другую версию)

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    новый виток развития старого бага... внезапно 0_о
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Как же долго я его ждал!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Все уже заждались)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Мммм. Топкодер не знает о не переводе часов в России. Даже грустно:(
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Автору плюс за задачи, классно подходящие под челендж:)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Как и многие в 250 не учел (a > upperBound) и естественно меня взломали =(
Как решать 500?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А там двумерная динамика h*w работает?

    UPD: Да, она работает :)

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

    Я решал динамикой по w, h: когда h=0, ответ 1, иначе ответ равен

    где R(n,k) - количество разбиений n на слагаемые, не превышающие k.

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

    Я кодил динамику по профилю. Там вроде профилей всего пара-тройка тысяч максимум.
    Не сдал, правда, очень эпично: пока фиксил последний баг в инициализации, вылезло сообщение об окончании.

    UPD: Ох, я почему-то ошибочно подумал, что в див1 500-я будет 1000-й из div2.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Динамика по профилю, это видимо в див2?
      → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Для w=10 различных масок 9003 штуки.
      Я на контесте забыл, что синюю можно ставить только на ее края, а в центре пусто, и так и не сдал эту задачу.

      Да, в первом моем раунде (SRM 522) я случайно попал в div-2.

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

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


    dp[w][h][add], это кол-во способов заполнить по правилам, с шириной w+add и высотой h, так что add левых нижних точно заполнены.

    Переходы: добавление любой из k планок, т.е переходов в dp[w-i][h][add+i]
    и "пропуска", который разбивает  на 2 подзадачи [plus][h][0] и [w-1][h][0]

    → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Когда - нибудь я буду писать нормально%)

Отхачили 250, на том же в чем и всех.
Хорошо хоть медиум сдал
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Самый простой СРМ за последние не помню сколько, 3 абсолютно решаемые задачи, ну и.. как обычно:Р
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Я заподозил что что-то не так, еще сдав три задачи за 20 минут до конца. Но первая это было внезапно.
А систесты будут идти бесконечно долго.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

А что происходит в див2? Почему на третьем месте какой-то парень, который сдал только первую задачу с 151,19. При этом сумма балов у него 1222,75 ? Как такое может быть если челенджы только целую часть меняют?

Пруф:


→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Забавно. У одного чувака из моей комнаты в 250 явно переполнялся long long. Я минут десять высчитывал на калькуляторе, что же ему скормить, чтобы точно отправить в WA, - и безуспешно. А у него сейчас Passed System Test. Раз он синий, это, видимо, везение, но был бы красный - я бы назвал это троллингом.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А можно ник?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      [Alaudddin]
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Я один не могу найти его в списке?

        тьфу, не актуально 

        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А где там что должно переполняться? У него написанно вроде даже что при всем до 1018 переполняться не будет. Или я чего-то не понимаю?
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          У него сначала идёт проверка, что m до 1012, потом он его ещё домножает на d. А потом он на эту величину домножает c - вот тут и должно переполниться.
          Но вот сейчас я посмотрел внимательно и вижу, что там в любом случае это не повлияет на алгоритм. А на челлендж-фазе подбирал такое d, что 1012*d*d будет иметь выставленный 64-й бит. Хорошо, что не подобрал :)

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

        typedef long long Long;

        Таки троль.

        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Меня по-другому затроллили - хотел почеленджить переполнение интов, а после -25 увидел строчку:
    typedef vector<i64> vi;
    Не хватало ниже подписи //trollface :)


    → Ответить
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Авторский разбор тут:
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

В div1 250 надо было еще ограничения дать все до 10^18.

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Зачем?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -17 Проголосовать: не нравится

      Чтоб веселее было. А что ж я, зря заменял умножение делением (чтоб geom[i]*d , вместе в выходом за аппербаунд, и за лонг лонг не вышло)?

      Просто такое впечатление возникло, что автор специально подбирал удобные для челленджа задачи (сейчас уже прочел в блоге, что за примеры в 250 он извиняется).

      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я чтобы не париться БигИнты бы прикрутил при таких ограничениях :)
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Похоже, мне пора покупать велосипед.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин. Не получил полноценного результата. Упала 250. Прикол в том, что я учел случай с a>upperBound, но вычислял отрицательную разность при делении (a-upperBound)/b. :)
В 500 забыл поставить модуль в одном месте, в итоге ресабмит и всего 210 очков.
Но задачи были хорошие. Как кстати 900 Div 1 решать?
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

забавно, что чувак, который всех челленжил направо и налево, получил море баллов, в итоге плохо выступил

... вобщем, у него все 3 задачи упали по Failed System Test

как говорится: не суди, да не судим будешь (c) шутка
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
40 минут безуспешного дебага 500, упавшая 250 из-за криво предусмотренного случая =( Лучшая позиция в рейтинге сменилась худшей. 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
За этот срм я видимо убил половину своих нервных клеток. Минут за 5 6 у меня была готовая 250 и... отрубился интернет: месяц закончился. Пока мой брат клал деньги на счет прошло минут 20. В итоге я сдал первую через 30 минут с компа соседа. Сразу открыл вторую и третью вернулся домой минут за 5 прочитал и написал вторую. Потратил минут 10 на включение инета. Еще за 5 минут написал третью. Итог: прошла первая на совсем мало прошла вторая на совсем мало упала третья я ненавижу МТС и небольшой плюс к рейтингу(( пичалька
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Харош Колян круто написал и теперь нормально красный
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    благодарствую) на самом деле, очень странный СРМ.
    все задачи очень простые, но написать и не пойматься на все подводные камни - это нужно иметь железные нервы))) вобщем, СРМ для челленжей)
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      Зато первый раз смог написать вторую задачу :) 

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

Не могу решить вторую. А именно: написал решение, проходящее все тесты, которые я могу проверить руками на листочке, и не проходящее большие. По коду багу найти не могу.

Вдруг найдется кто-то, кому ошибка будет очевидна.

Как решаю.

f(w,h) - сколькими способами можно получить фигню высотой ровно h, если ширина основания w. Разделяю это на подзадачи, перебирая позицию самой левой пустой клетки на нижнем уровне.

Код: http://pastebin.com/NdLCKDqL

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Пока не смог найти конкретной ошибки, но склоняюсь к тому, что у тебя неверные переходы в собирании суммы.
    Советую посмотреть мой короткий код;)
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Как только написал это, подумал, а почему бы не сделать f(w,h) - сколькими способами можно получить фигню высотой <= h. Написал это, оказалось короче, меньше асимптотика и работает правильно.

    upd: не, нифига не правильно, всего лишь последний семпл-тест почему-то прошло.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Давай код, тот что короче)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        http://pastebin.com/gjbreqH9
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Кое что мне показалось как минимум не понятно.
           ll testLeft = prec[lp]*f(lp,h-1);
           ll testRight = f(w-lp-1,h);
          Почему одна часть домножается на дополнительную константу а другая нет?)
          И вообще, мне кажется, неверно сначала собирать сумму и потом домножать на количество способов, ведь сами слагаемые можно составить разными количествами способов.
          → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Почему левое домножается, а правое нет:

            lp - позиция самой левой пустой клетки первого уровня. Значит слева от нее все клетки заполнены. Способов заполнить их prec[lp] штук. А на эти заполненные можно еще понаставить чего-нибудь высоты не более h-1.

            Справа же от этой позиции  другие пустые клетки могут быть, поэтому там просто f от той же высоты.

            > И вообще, мне кажется, неверно сначала собирать сумму и потом домножать на количество способов, ведь сами слагаемые можно составить разными количествами способов.

            Не очень понял.

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

            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              >Не понял.
              Похоже, что как раз в этом месте и ошибка.
              Когда ты собираешь сумму, с длиной lp, полоска может разбиться на несколько несвязных частей, каждую из которых нужно умножать на свой f(x,h-1), сразу все нельзя.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Несвязные части - части, разделенные пустыми клетками?

                Если да, она не может разбиться, так как там нет пустых клеток.

                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Ты прав, тут моя ошибка.
                  Ещё одна попытка:
                  dp[w][h] = (dp[w][h]+f(w-1,h))%mod;
                  Как я понял это случай с пустым левым концом, правый у тебя рассматривается в цикле.
                  Для случая w=3, h=1 расстановка с одним кубиком посередине учтётся 2 раза. То есть порядок "обрезания" пустых клеток имеет значение в решении.
                  → Ответить
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится

                    ================================

                    Расстановка пусто-заполнено-пусто?

                    Самая левая клетка пуста, значит рассмотрится только в строчке

                    dp[w][h] = (dp[w][h]+f(w-1,h))%mod;

                    В цикле она уже не рассмотрится, в цикле самая левая пустая клетка перебирается начиная со второй.

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

              Double.

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

          Triple.

          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          ll testLeft = prec[lp]*f(lp,h-1); 
          ll testRight = f(w-lp-1,h); 
          dp[w][h] = (dp[w][h] + testLeft*testRight)%mod; 

          В testLeft*testRight может быть переполнение. Попробуй в первой строке модуль поставить.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ах, как все просто.
            Надеюсь сейчас будет правильно, потому что все мои идеи неверные, и больше сомнений вроде нет.
            → Ответить
          • 13 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Да, это именно оно, спасибо.

            Adamka, спасибо и тебе за попытку помочь и потраченное время)

            → Ответить