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

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

Уже через три часа стартует первый раунд FHC. Напомним, что в следующий этап проходят все те участники, которые решат столько же задач, сколько 500-е место, при условии что 500-й участник решил хотя бы одну задачу. Раунд продлится 24 часа

ссылка на раунд — https://www.facebook.com/hackercup/problems.php?round=225705397509134 Не забываем что в прошлый раз были проблемы с https

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

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

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

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

Ссылку на олимпиаду киньте

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

У меня одного

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

?

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

После этого комментария я уже смирился с тем, что не видать мне Online Round 1. Но на следующий день пришло письмо — ответ на клар:

Hi Boris,
Your problem was graded correct. Good luck in Round 1.
Thanks for contacting Facebook,
Facebook
-----Original Message to Facebook-----
_From: ... _
To: The Facebook Team
Subject: Hacker Cup Feedback
Type of Feedback: error
Problem: Billboards
What's Up?: Some days ago I send solution of this problem, put had no result. I send it on https. I read on forum that it means that I had presentation error, but it wasn't showed to me, so I've no chance to correct solutions. Also I read that some submitions with same problem were corrected by jury and rejdged. So, can you make the same with my solution? Contact Email: ...
-----End Original Message to Facebook-----

Тем не менее в раунд меня не пускает. Да что ж это такое =( На главной странице не могу даже найти контактов жюри.

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

Round One: Fight!

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

So fail....

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

    So much win.

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

    Раунд еще не закончился.

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

      Конечно, однако я думаю мой комментарий не приносит ничего такого чего не видно в условии...

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

        Догадайся убрать под спойлер хотя бы. В идеале конечно надо удалить комментарий.

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

    Ты заслуженно не проходишь в следующий раунд

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

      Петросян, я не знаю кто ты есть на самом деле, но ты — мерзкий человек. К людям надо иметь хоть каплю уважения. Андрей заслужил пройти в следующий раунд.

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

Если так дальше и пойдёт, то 500ое место будет иметь все 3 задачи

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

    это да. Прошло всего 4 часа раунда, а 250 человек уже послали все 3 задачи (а остальные 250 — по 2 задачи). Так что схалявить как в квале не получиться, придётся решать все 3.

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

    Итого 1492 человека решило 3 задачи (без учета тестирования).

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

      Да, забавно получилось. У меня друг упорно до конца искал баги, и все 3 решения отсылал в последние 10 минут

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

Поясните пожалуйста мне убогому, почему в первой задаче ответ для S = 5, 6 а не 5? Мы ведь можем поместить checkpoint и goal в точку (1, 4) и тогда S = 5 и T = 5, разве нет?

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

    а все, дошло. там же написано английским по белому, что checkpint не совпадает со стартом и финишем.

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

    Во время раунда как бэ без пояснений. И скройте пожалуйста все под спойлер.

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

Ух.. вроде решил все задачи. Несмотря на постоянные их лаги, задачи у них очень интересные, по крайней мере раунд1 мне очень понравился.

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

Уверен что все 3 задачи сдаст далеко не 500 человек. Задачи простые, многие пренебрегают внимательной вычиткой условия, тестированием на крайних случаях. Оффтоп: в этой теме неоправданно много минусов.

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

    Посубмитят 3 видимо всё-таки больше 500 человек

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

Посубмитили уже больше 500 человек. Очевидно, задачи более-менее простые(конечно, узнаем на финальных тестах насколько они простые). Вот лично я считаю, что это плохо. Чисто гипотетически, если Петр ошибется в какой-нибудь задаче, он весьма вероятно пролетит мимо следующего раунда! Это не есть хорошо.

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

    Мне почему-то кажется, что 2 задачи все же пройдут в сл. раунд. В той же квале я после сис. теста поднялся с 3000 до 1800 места (+1200 мест), хотя в тех задачах (A и С) я ума не приложу где можно было набажить.

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

      А мне всё же не верится что у 400+ человек упадёт что-то из трёх задач.

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

    Или Попелышев

    Jokser, в квалификации было много дурачков которые сдавали абы что, видел исходники где на английском написано "Я не знаю как решается эта задача", а в этом раунде таких должно быть меньше. Тем более что в квалификации у многих падала третяя из-за удвоенной буквы С

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

Все. Не знаю как вы, а я молиться богам программирования что нигде нет багов. Чекерами вроде как проверил, но все-таки...

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

Самое смешное, что на самом сайте, в комментариях к туру уже давным давно выложены по несколько раз идеи решения всех задач =(

Модерация, такая модерация на мордакниге=(

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

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

    Пролистал FAQ и правила. Среди условий дисквалификации: "Communicating or publishing information concerning the content of the problems, or solutions to the problems, with other competitors, either directly or indirectly, before the end of the Round." Не понимаю, на что расчитывали те, кто там прям в комментариях на тесты отвечал или условия постил.

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

      На десяток дисквалов пару сотен людей "решивших", даже если вдруг эти дисквалы таки будут

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

    не понятна логика людей, которые пишут решения. ладно те, кто читают — читеры, они везде читеры. Но какой смысл помогать конкурентам — вот что непонятно.

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

Чё-то не круто получается: люди с закрытым проблемсетом могут не пройти в следующий раунд

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

    В смысле? Если правильно решено 3 задачи, то в любом случае проходишь в следующий, ибо это не хуже, чем у 500 места в любом случае.

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

      Ааа я не обратил внимание. Ну тогда всё норм

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

Ничерта не работает на Facebook: только что благополучно получил Time Expired по одной из задач, т.к. сабмиты у меня принимать никто не хочет — нажимаю на кнопку Submit, и ничего не происходит. Остальные две решать, естественно, не буду. (отправлял из Firefox 8.0)

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

    Надо заметить, у меня по всем трем такой вердикт, хотя с первого раза все отправилось, причем я вижу свои сорцы, вывод и md5. Сам на всякий случай написал feedback, и вам советую.

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

      Я не вижу ни сорцы, ни вывод, ни md5, ни себя в мониторе, ни причин решать остальные две задачи.

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

        Зайди без https. Так бывает.

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

          Во-первых, одна задача зафейлена, и мое отношение к facebook отныне максимально негативно, а во-вторых, я и так заходил без https.

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

            Никогда не сдавайся!

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

            Добро пожаловать в клуб "Зафейливших-из-за-багов-hacker-cup" =)

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

    Это в очередной раз говорит о том, что прежде чем проводить реальные соревнования, надо проводить тестовые контесты на своей системе. Все особенности всех браузеров и конфигураций учесть непросто, и даже если в системе не используется, простите за выражение, флеш, всё равно априори нельзя быть уверенным на 100% в работоспособности.

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

Вообще, конечно, соревнования для саперов надо проводить по таким правилам, а не для программистов %)

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

    Посмотрим. Может, все-таки окажется так что 700+ решений упадут из-за какой-нибудь фигни и народ пройдет. Всякие чудеса случаются.

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

Как решать Checkpoint?

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

    Кол-во способов дойти в (i,j) — C(i+j,j) причем стоит оно i+j. Раскладываем в произведение двух цешек (предподсчитаны) с минимальной суммой

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

      Каким образом преподсчитываются все C(i+j,j)? Я сохранял в массив все 10 миллионов вариантов. Уверен, что есть способ лучше.

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

        Я считал все C(i, j) при i до 105, j ≤ i. Но останавливался, если C(i, j) ≥ 107

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

        Можно было рассмотреть :

        1. C(i+j,j) i+j <= 5000.

        2. C(i+j,2) и C(i+j, 1) 5000 < i+j < 10000000.

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

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

          Возможно, глупый вопрос или баян, но хотелось бы узнать как можно эффективно посчитать C(n,k)? Вроде наивным способом будет цикл, есть ли способы лучше?

          for(int n1 = 1; n1 <= 10000000; n1++){
            for(int k1 = 1; k1 <= n1/2; k1++){
              long numerator = 1;
              long denominator = 1;
              for(int m1 = 0; m1 < k1; m1++){
                numerator *= (n1-m1);
                denominator *= (m1+1);
                if(numerator/denominator > 10000000)
          	continue maincycle;
              }
              long resultCombination = numerator/denominator;
            }
          }
          
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Спасибо за ответ! Получается динамика в случае с небольшими сочетаниями. Если же цифры большие , например, 10000000? Случайно нет никакого свойства, позполяющего считать быстро?

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

            Кстати, а ваш вариант, похоже, вообще неправильный ибо числитель переполненяется.

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

              В каком случае переполняется? Я не был уверен на 100%, но таки оставил так.

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

              Проверил, переполнения не происходит :)

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

                А, пардон, я не заметил что это java. Просто на С/C++ long обычно 32 бита и там точно такой же код легко переполнится.

                В любом случае, нет никакой нужды делать это в две переменные, можно сразу делать result = (result*(n1-m1))/(m1+1) ибо оно всегда целочисленно.

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

            В этой задаче можно построить треугольник паскаля с отсечением. Я так делал.

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

    Я решил так. Написал динамику по типу кол-во способов дойти до клетки, если можно ходить только вверх-вправо. Высчитывал ее через 2 строки до тех пор пока кол-во способов в первом элемент новой строки не перевалит за S. Там сложность получается меньше чем O (S * logS). Ну и соответственно обновлял кратчайшие расстояния при данном S. А далее у нас кол-во путей разбивается S = Sa * Sb. Где Sa — до checkpoint, Sb — до goal. Нужно перебрать делители S и найти наилучший ответ.

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

      Можете, пожалуйста, показать код. Не совсем ясно, каков массив состояний. Вроде, динамика на матрице имеет сложность O (N*N)

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

    Я решал так:

    Динамикой нашел точки в которые можно добраться A путями, и сохранил в массиве самый короткий путь. Теперь мы имеем массив arr[S] == T

    S общее = S CheckPoint * S Goal

    T (0,0 -> Goal) = T (0,0 -> CheckPoint) + T (CheckPoint -> Goal)

    Просто перебираем все пары множителей через массив

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

    Предпосчитаем для каждого i из [1, 10000000] минимальный периметр dp[i] такого прямоугольника, чтобы количество способов добраться из левой нижней вершины в правую верхнюю было ровно i. Сделать это можно было просто треугольником Паскаля с отсечением. Потом для каждого s будем переберем все его делители del до корня, включая единицу, и найдем минимальную величину dp[s]+dp[s/del].

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

    Там получается, что до какой-то точки можно дойти с помощью C[n,k] способами. И фактически теперь для каждого S нам нужно найти минимальное n, что найдётся k, такой, что C[n,k]=S (тогда n — это путь минимальной длины). Ну и поскольку нам нужно пройти через контрольную точку, то рассмотрим все делители S и ответом будет n1+n2, где n1 и n2 минимумы соответственно в C[n1,k1]=S1 и C[n2,k2]=S2, где S=S1*S2. Я так решал...

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

В последней "Squished Status" вроде было проще всего набажить — не рассмотреть какой-то случай с нулями, или с типами промахнуться (получить переполнение)

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

    А какие там случаи? Конечно, возможно, что у меня неправильное решение, но оно жутко простое, да и случаев там особо нет никаких...

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

      В моем решении могли возникать проблемы, если max значение однозначно(меньше 10)

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

      Я считал через динамику, и случаи когда нулей 3+ подряд, когда 100, и нельзя брать только 1, или только 10. Вобщем у меня осталось ощущение что я чего-то недосмотрел

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

        Там ещё один случай — 200.

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

          Да. Я имел ввиду 100 как пример, подразумевалось x0 и x00, хотя у последнего действительно только 2 вариант при данном ограничении на М

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

      Да... у меня тоже жутко простая динамика. Там может быть люди ловились на том, что в динамике новое число нужно проверить, чтобы оно не было с лидирующими нулями.

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

        Лидирующие нули необходимо было обрезать (включая 0) + опускать те сочетания цифр, которые превосходят данных max.

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

          Не надо ничего обрезать. Если в динамике очередное число начинается с нуля, то не считаем такие случаи в динамике. http://codeforces.me/blog/entry/3787#comment-76968 вот хорошо расписано. Я делал по такой же формуле.

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

            Как раз в этом разборе и написано "Таким образом, нужно учитывать, что число не начинается с нуля и попадает в интервал [1..M] и использовать заранее посчитанные значения."

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

    что вы имеете ввиду насчет "промахнуться с типами"? Использование целочисленных типов?

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

      ну я вот модуль 4+ миллиарда прочитал как 4+ миллиона. =(((

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

      использовать int вместо long long

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

        А, точно, не заметил, что надо было, Использовал не задумываясь:)

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

    Задача — баян, древний из книги Ф. Меньшикова.

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

Проверка опять производится вручную? =\

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

Решение последней расскажите пожалуйста. Мое решение по времени зашло, но может это какая-то известная задача и решается без костылей.

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

    ways[i] = количество способов прочитать сообщение, состоящие из i первых символов строки. ways[0] = 1, ways[i + j] += ways[i], для таких j = 1......, что подстрока str[i + 1...i + j] является валидным числом.

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

      +угловые случаи, например для 255 100 ответ — 1, а не 2 или 3

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

        так а что здесь углового? валидное число — это число от 1 до M, это явно сказано в условии.

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

          Например для строки 1100, i = 0, j = 1 ways[0+1] += ways[0] если str[0+1 ... 0+1] является валидным числом Но str[1] нельзя считать валидным числом, потому что нельзя разбить на строки 1-1-[00 — как ни возми, они не валидны]

          Т.е. важно не только чтобы строка str[i+1 ... i+j] была валидной, но и то что после нее остается

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

            ну так и что? давайте промоделируем i = 0 ways[1] += ways[0] (число 1) ways[2] += ways[0] (число 11) ways[3] += ways[0] (число 110) ways[4] — не добавляем,1100 — не подходит пока все ок, ways[1] = ways[2] = ways[3] = 1

            i = 1. ways[1 + 1] += ways[1] ( число 1) ways[1 + 2] += ways[1] (число 10) ways[1 + 3] += ways[1] ( число 100) получили, что пока ways[4] = 1. i = 2. ways[2 + 1] — не добавляем, ибо 0 — не валидное число. аналогично для любых добавлений дальше.

            в конце получим,ways[4] = 1, как и нужно.

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

        "валидное число" как раз учитывает угловые случаи.

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

    Решение — ДП.

    dp[i] = количество способов разбить строку до i-го символа включительно.
    Представим строку как массив чисел (0 <= s[i] < 10), пусть они нумеруются с единицы.
    dp[0] = 1
    dp[i] = (1 <= s[i] && s[i] <= M? dp[i — 1]: 0) + (10 * s[i — 1] + s[i] <= M && s[i — 1] > 0? dp[i — 2]: 0) + (100 * s[i — 2] + 10 * s[i — 1] + s[i] <= M && s[i — 2] > 0? dp[i — 3]: 0)
    Таким образом, нужно учитывать, что число не начинается с нуля и попадает в интервал [1..M] и использовать заранее посчитанные значения.
    Ответ dp[length(s)]

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

кстати я сейчас занимаю 777 место.

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

Е-мое ну сколько можно, а? У них что, реально руками проверяют все тесты? Про чекеры, валидаторы не слышали, не?

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

    Вроде результаты уже окончательные стоят.

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

      Японский городовой, у меня первая упала.

      looser:(

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

        Наверное, случай с делителем единицой не рассмотрел.

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

          Нет, все тупее. Банально забыл лонги, у меня в одном месте умножение с переполнением. Тупее не придумаешь.

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

            а где там умножать лонги? везде все кажется в инт помещается?..

            тупее — в 3й брать ответ по модулю (int)4207849484 =)

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

            Бывают и более эпичные ошибки. :-) У меня присваиванием (умышленно?) вбито значение 127 в предпросчете, из-за которого при S=1 (ну и везде, где биномиальный коэффициент равный 1 учавствует) я выдаю 254. Как, когда и зачем я это сделал — ума не приложу, сознание категорически отказывается брать на себя ответственность за epic fail. :-)

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

У одного из моих друзей эпичная ошибка в третьей:

static final long MOD = 0xfaceb00c;

Числа в Java знаковые, буквы L справа от константы не стоит, значит она 32-разрядная и, ВНИМАНИЕ, отрицательная.

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

    В эклипсе компилятор автоматически подсвечивает, что число выходит за границы инта, если в конце не стоит l и число представлено в десятичной форме 4207849484.

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

      Да везде подсвечивает, если именно в 10-ной форме. Иван вел речь как раз про hex.

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

    Как правильно сказал -dp-, раунд был для саперов. Увы, несколько человек наступили на мину. При том на коровью.

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

    Передайте ваше другу, что надо быть проще :) Если бы написал по-простому, в десятичной системе счисления static final long MOD = 4207849484;, то это бы даже не скомпилировалось бы.

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

      Оно, конечно, да, но мышка оказалась ближе к 16ричному варианту :(

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

    Это был Egor?

    PS: так за что минусуете-то?

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

"This round has ended. Feel free to use the problems for practice though!" Кто подскажет как их использовать если возможности скачать input нету ? :) Кстати когда были представлены даты этого года, сказали можно попробовать решить задачи прошлого года, и ссылка на неработающую систему проверки :)

P.S. было бы неплохо по окончанию писать причину Реджекта по задаче (какой тест например). Или решили и дальше гнуть линию абсолютно молчаливых организаторов ? :)

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

    Какой тест например

    Тот, что давали вам :)

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

    Качаешь любое правильное решение из таблицы, запускаешь на своём тесте и сравниваешь ответы. Кэп передаёт пламенный привет)

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

      я для всех задач использовал 1 интуп файл, так что у меня только для последней, а упала первая

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

        Его можно скачать, вроде как.

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

          output, md5 и исходник :)

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

            Могу скинуть свой инпут и оутпут

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

              Давай :) Для третей, если кому-то нужно input output

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

                Checkpoint input output

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

                  Есть 1 отличии, и что характерно на 13ом тесте :)

                  У меня разложение 9699690 дает S1 = 2002, S2 = 4845 и T1 = 14, T2 = 20

                  У тебя получается 28 в сумме. Хм

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

                  Оказалось условие остановки динамики срабатывало немного раньше чем нужно было. Отсюда неполная таблица

                  Спасибо за инпут

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

              Кстати, может кто-нибудь красный на cf:тренировках выложит? Могу еще свои инпуты/аутпуты выдать для коллекции.

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

                Кстати да, было бы прикольно. Мне друг скинул свои инпут/аутпут по первой задаче, и моё неправильное решение с этим инпутoм прошло бы ) 20 тестов, видимо, маловато для отлавливания большинства багов