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

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

Всем привет!

Как многие из вас уже знают, сегодня в обоих дивизионах состоится Codeforces Round #127, пропускать который очень не рекомендуется ;)

Оригинальные задачи для вас придумывали и готовили tourist и Romka. Мы старались сделать упор на идейную составляющую задач, поэтому надеемся, что вам придётся думать дольше, чем набирать код. Отдельное спасибо за помощь в подготовке контеста координатору Codeforces Gerald. Также благодарим Delinur за перевод условий и Alex_KPR за вычитку условий.

Надеемся, что этот раунд будет для вас не просто очередным раундом на Codeforces, а принесёт вам новый опыт и новые знания. Авторам все задачи кажутся одинаково простыми, но мы всё-таки постарались расположить их в порядке убывания простоты :)

Разбалловка в первом дивизионе: 1000-1000-1500-2000-2500. Разбалловка во втором дивизионе: 500-1000-2000-2000-2500.

Успехов!

UPD: Соревнование закончено, всем спасибо за участие. Надеемся, вам понравилось :)

В первом дивизионе безоговорочную победу одержал rng_58, решив все пять задач за полтора часа! Решить все задачи за два часа больше не удалось никому.

Победители в первом дивизионе (полные результаты):

  1. rng_58

  2. peter50216

  3. liympanda

  4. White_Bear

  5. havaliza

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

Победители во втором дивизионе (полные результаты):

  1. Leewings

  2. snow_lotus

  3. 72VanVector_SevNTU

Поздравляем победителей!

UPD2: Опубликован разбор задач.

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

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

Заранее говорю спасибо. Очень ждал контеста от Геннадия.

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

    И всё же это контест не только от Геннадия :)

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

      Не только, но и от Геннадия тоже. И я говорю "спасибо". И Роману я тоже говорю "спасибо"

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

    Серёга советую не писать)

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

Авторам все задачи кажутся одинаково простыми, но мы всё-таки постарались расположить их в порядке убывания простоты :)

позабавило)

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

Задача А — "Сокобан")

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

    Кстати, извиняюсь за оффтопик: кто-нибудь в курсе, можно ли впихнуть что-нибудь вроде решения сокобана во что-нибудь вроде кандидатской диссертации? :)

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

      Можно что-то вроде запихивания сделать)

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

        Я этот вопрос адресовывал тем, кто что-то понимают в теме, а не тем, кто будут кидать вот такие шутки.

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

          Тогда пишите получателя, как в письмах. Я ориентировался на смайлик

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

          Да просто бессмысленный вопрос. Уточни, что ты понимаешь под "что-нибудь вроде" в обоих случаях.

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

This will be my 1st participation ever on a codeforces round!! I am looking forward to it

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

As points seem to be in increasing order, it suggests that also the difficulty of tasks is increasing rather than decreasing... am I right? :)

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

"yet we tried to arrange them in decreasing order of difficulty :)"

decreasing order with points increasing?

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

    That was a mistake, sorry. It should be "in decreasing order of simplicity", of course.

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

"...we hope that you’ll spend more time thinking than coding..."

I really like the idea ;-)

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

А почему такой же пост от ilona насильно запихали в черновики, а автору сделали письменный выговор?

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

"For the authors all problems are equally easy, yet we tried to arrange them in decreasing order of simplicity :)" Nevertheless, we recommend you to read all the statements and hope you won't get stuck on one problem losing possibility to solve other problems.

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

Так, а теперь вопрос: откуда пользователь ilona узнал, кто авторы контеста?

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

I Hope Short statements ,easy to understand and more thinking.

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

ой, какая я популярная.

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

I feel it will be hot !!!

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

А то, что мне при попытке открыть страницу с условием выдаёт "Условие недоступно." это всё норм?

UPD. Уже прошло

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

Спасибо авторам за контест ,было очень интересно, жаль что я опять зеленый..

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

Откройте секрет 7 теста задачи А!

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

    3

    Ответ — 5

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

      100 010 001 upd. да. действительно

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

        Не симметрично.

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

        матрица должна быть симметрична по вертикали и горизонтали. если есть 1 не в центре — то и еще в 3 точках. потому 3 на матрице 3х3 не получишь.

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

          Не совсем так. Еще может быть в центре боковой стороны, тогда можно получить 2 единицы. Но да, при этом блокируется диагональ.

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

    x = 1 -> ans = 1 x = 3 -> ans = 5, x <= 5 -> ans = 3; x <= 13 -> ans = 5; x <= 25 — > ans = 7; x <= 41 -> ans = 9 x <= 60 -> ans = 11; x <= 85 -> ans = 13 x <= 100 -> ans = 15

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

    So Ivan won't accept that problem for Torcoder? :)

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

      I don't think the SRM's problem contains a permutation of the codeforces's problem as a subsequence :)

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

    Turns out it wasn't a brand new problem [:|||:] :)

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

    We're really sorry that this happened. We both missed that SRM, so there was hardly a chance for either of us to find that out.

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

      I know it's impossible to completely avoid "duped" problem. I'm just a bit surprised.

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

Подскажите как С решать плиз

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

    Ответ по рядам не зависит от ответа по колонкам

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

      Это вы про Б наверно?

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

        Ох, да

        В С динамика — сколько концов пути слева от нас (0, 1 или 2). Если 0 или 2, то мы берем четное число ребер, если 1 — то нечетное (максимально возможное). Если ребро 1, то 0 и 2 присваиваем 0 (так как тогда весь наш путь лежит по одну из сторон). Ну и на каждом шаге делаем ans = max(ans, dyn[2]) и dyn[1] = max(dyn[1], dyn[0]), dyn[2] = max(dyn[2], dyn[1]) (назначаем один из концов в этой вершине)

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

          Спасибо за подробное разъяснение.

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

What is the logic behind Div-2 Problem C ??

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

    just try it out wid some input values and observe the pattern....look for dependencies if any cell is 1..u wil find cells dependent in groups of 4, 2 and 1..so each square of size n gives some 4 pairs, some 2 pair and 1 one. now all possible combinations of sums from these pairs can be reached with square of size n. max sum dat can be reached using square of size n is sum of all pairs of 4, 2 and 1.

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

      Why is the output of x=3 is 5 ..Cant we have something like:

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

        it is not symetric.

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

          Oh..I just read "Let's call matrix A symmetrical if it matches the matrices formed from it by a horizontal and/or a vertical reflection" and skipped the formal description.. From that statement I had made the conclusion that if we place a mirror on the bottom or the right and take the reflection and match then if we get the same array ,Its done..

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

          y not..

          0 1 0

          0 1 0

          0 1 0

          for x=3...??

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

Задачи понравились, спасибо за раунд!
В E Div 2 верно считать 4 dp — сколько наберём уйдя влево и вернувшись, и не вернувшись, тоже для правой стороны?
Как делать D Div 2?
UPD: да, верно, жаль не успел отладить

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

    D div2 (B div1):
    Заметим, что можно решить отдельно по X и по Y.
    Далее за квадрат: перебираем позицию для текущего измерения, для каждой за линию ищем сумму произведений квадратов расстояния до столбца/строки на сумму этого столбца/строки (суммы предподсчитать)
    В ответ сумму минимальных сумм для строк и столбцов, и номера строк и столбцов, в которых достигается минимум.
    P.S. Мне одному нужно в комментариях <br> для перевода строк ставить? Или это нормально?

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

      Спасибо! Пора бы уже научиться видеть боянистые идеи ><.

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

      можно еще в конце строки ставить 2 пробела

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

        Тест двух пробелов
        (раньше всегда <бр> ставил)

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

      Тут комментарии форматируются Markdown'ом, в нём между двумя параграфами должна быть пустая строка, чтобы они считались двумя отдельными параграфами.

      Я ведь прав, да?

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

        Похоже оба способа работают, но мне как-то не нравиится дыра между абзацами в случае пустой строки между абзацами, поэтому два пробела.
        Спасибо!

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

    Надо минимизировать . Дифференцируем, получаем формулу, находим дробные x и y, смотрим точки по соседству.

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

      подобное решение я взломал

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

        Да, моё решение тоже упало. Есть даже гипотеза почему. Но скорее всего падает из-за кривой реализации. По крайней мере ошибки в теоретической части я не вижу: минимум квадратичного функционала на целых числах должен достигаться на одном из соседних к точному минимуму чисел. Или нет?

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

          Если 20 тест то это тест из всех нулей, при попытке посчитать x0, y0 будет деление на 0

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

            Нет, это я как раз предусмотрел отдельным условием. Упало на 11м тесте.

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

контест сложный, но задачи отличные

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

    Лично мне понравилась только задача С div 1.

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

The Div1-E has been mentioned on Topcoder before (check SRM 484 Div1-Hard editorial) for reference). EDIT: Too slow

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

Спасибо за контест!
Боян очень порадовал (в т.ч. формат вывода :)
[:||||||||||:]

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

    :))) До меня только дошло, что это рисунок бояна. :)))

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

      Всё-таки, это рисунок бАяна.

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

        Даже не знаю, кому верить: википедии или авторам задачи :)
        Ибо в условии написано «боян» :)

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

          В условии написано "обидное слово". Обидное слово могло быть хоть "фывапрол" ;)

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

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

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

          Думаю в данном случае значение имеет [:||||||||||:], а не его название:)

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

Вопрос снят

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

Отличнейший контест, пишите ещё!!!!

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

Слова из описаний всех задач содержат не более 10 строчных латинских букв. Гарантируется, что суммарная длина слов в описаниях всех задач не превышает 500015.

с чем связанно именно 500015?

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

    15 слов (однобуквенных для уменьшения размера теста) в задаче Лёши + 500000 слов в задачах в архиве

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

Ну зачем переопределять существующие понятия??? (задача А, определение симметричности) Задача B — гуд, но я почему-то несказанно тупил весь контест и вообще всё слил. Когда хотел почитать задачу C, загрузилась страничка что сервер занят, а потом страница с сообщением "Условие недоступно." ... И тут я понял — всё против меня.

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

в задаче А 100 тестов из 100 возможных, not bad!

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

    да ладно? николас_кейдж_фейс

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

    А чего мелочиться :)
    Тем более каждый тест генерится за O(1) :)
    И в идеале за столько же проверяется.

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

    Отличный шанс заддосить тестер :)

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

      Только если специально :) чего каждый участник обещает не делать при регистрации на контест :)
      Лично мне разумного решения медленнее чем за квадрат в голову не приходит.
      Итого тестирование за O(N^3), что при таких N более чем быстро :)

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

Спасибо за отличный контест))))

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

Никогда не ставьте максимум 12345678912345ll. До — 1842078. После — 1844086.

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

Like the problem set! e.g., for problem C, after analyzing a bit we can actually come up a very simple DP algorithm. Problem A (the easiest one) is too tricky to trap me for a long time...

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

Какая будет матрица в задаче A при x=6?

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

Задача B, тест из всех нулей, деление на 0, жесть!

-100 мест и фиолетовый...

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

    Задача B: тернарник вместо очевидного O(m * n) — потратил 49 минут времени. Задача А: написал правильный брутфорс, но тупо не заметил, что на тест 3 ответ 5 — итого все еще фиолетовый и не сильно быстро приближаюсь к оранжевым...

    В-общем, беда у нас с Вами одинаковая.

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

Any one Can tell me the Connection between Problem E with NumberMagic? ( SRM 484 Div 1 1000 ? ..

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

In Div2-C, how does the square look like for x = 3 ?

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

Somebody can tell me the value of n for x = 2 in problem C (div 2) and how the matrix looks like? Thanks.

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

I really dint want to do this.But I am facing a strange trouble in the submission of the problem-B of div 2. It gives wrong answer on pretest 11 but when I run the program in my system for the same input it is giving correct answer. Here is the link http://www.codeforces.com/contest/202/submission/1844228

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

Задача Div2-A порадовала :) жаль ограничения не 105.

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

Excellent contest. It was not very suitable time for me but I don't regret that I tried to compete.

Output format in D was ridiculous (bad that non-Russian speakers won't get it).

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

Я один писал в А динамику по профилю с изломом, а потом забивал ею массив констант?

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

Will it have an editoral?

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

Может кто нибудь, пожалуйста, объяснить, как в таком тесте тесте в С получить 48:

9

9 2 8 7 1 4 10 9

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

    3210101010123232323(влево)
    434343456787656787878767676765(вправо)
    0 — based

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

    в итоге остаются первое и последнее ребро. А весь обход такого вида: начали с 4-й платформы, сделали 3 шага влево, потом до противоположного края и 3 шага влево (по ходу нужно ходить туда-сюда по ребрам, если есть возможность).

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

FAIL:(
Minor mistakes (less than 5 chars of code each, one per task) in tasks B and C and I am 221th instead of ~90th.
I need to exercise more often.
Good contest anyway!
I have had a lot of fun!

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

4 a b c d 1 11 b c b a d d d a a c b for this test in B problem i am getting wa when in my pc i am getting the correct ans. code can anybody explain?

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

what is test case 11 in Div2 B?

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

what is test case 11 in Div2 B?

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

    4

    a b c d

    10

    20 d c c c c c b b b b b a a a a a a a a a

    20 d c c c c c b b b b b a a a a a a a a a

    20 d c c c c c b b b b b a a a a a a a a a

    20 d c c c c c b b b b b a a a a a a a a a

    20 d c c c c c b b b b b a a a a a a a a a

    20 d c c c c c b b ...

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

Когда будет разбор?

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

Редкий контест, когда у Гены не было шансов победить.

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

When will editorial be available?

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

I didn't understand the definition of "clear" matrix in "Clear Symmetry." "Clear" means that no two or more adjacent "1"s never appear? Thank you in advance.

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

Мое решение 1843679 задачи D требует примерно 500000 * 2^15 * 15 операций в худшем случае (такой случай существует). Но за счет эвристики против случайных тестов получает Accepted.

Не каждый день удается подловить UPD: все-таки Рому, а не Гену :)

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

    перепутал кое-что, написал глупость :)

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

    Во-первых, эту задачу делал я :)
    Во-вторых, тесты там далеко не случайные
    В-третьих, у нас было около 5 неправильных решений на эту задачу с разными эвристиками/жадностями/отсечениями, и против каждого были тесты

    Всех эвристик, разумеется, не предусмотришь — а в этой задаче их можно выдумать не один десяток. Тем не менее, я хочу сказать, что умение написать качественную эвристику тоже не у каждого есть, и человек, написавший достаточно продуманную и обоснованную эвристику тоже в какой-то мере заслуживает поощрения в виде АС.

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

Странно. Все C (про симметрию единичек) циклами решали, а я прямую формулу на бумажке вывел. Т.е. у меня самое короткое решение и еще O(1), lol.

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

    Понятно. "Не смог написать эффективное решение – заминусуй того, кто смог". Я думал, тут умные люди собрались, а оказалось словно на хабре. Дети.

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

      Я лично Вас не минусовал, но пост прокомментирую.

      Во-первых, опытные СПшники, если им моментально приходит в голову решение с циклами и если позволяют ограничения, пишут именно его, а не тратят драгоценное время на вывод формулы.

      Во-вторых, Вы в данном посте де-факто выпендриваетесь: "Все тупые, пишут решение с циклами, а я умный, написал решение с формулой". Еще раз см. пункт выше.

      Пример того, как можно было бы написать то, что Вы написали, но "по-нормальному": "С-шку можно решить циклов одной формулой за О(1) без всяких циклов. На Ruby это вообще вмещается в две строчки.".

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

        Я уверен на 99%, что ваш вариант комментария получил бы ровно такую же оценку. Он по сути ничем не отличается – если решение является д'Артаньянским, то как ни пости, вызовет баттхерт.

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

      я вас плюсанул, только не плачьте

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

      и кст, я думаю здесь все решившие ее циклом, знают, как сделать это формулой, просто не захотели еще и формулу выводить, так что понт по этому поводу не уместен, вот если бы вы Д див2 решили за О(1)

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

        Формула была написана в две попытки, менее, чем за минуту даже без черновика, могу хоть фотку бумажки прислать. Где тут "тратить время на выведение вместо того, чтобы написать цикл на 10 строк и накосячить в куче всяких i и j", я не понимаю, как ни крути. (если у кого-то возникнет вопрос, почему введение i и j вызывает ошибки, пусть не спрашивает меня, а идет сразу на википедию читать о функциональщине)

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

          какой цикл на 10 строк, наркоман что ле?
          цикл пишется так же быстро, как формула

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

            Если ты не смотрел чужие решения, значит я наркоман?

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

              ну просто понимаешь, решил ты за О(1), ты молодец, ну это не повод для понта

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

                А тут и не было понта. Тут был массовый баттхерт

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

                  ну все расценили это как понт, и вполне справедливо, на мой взгляд

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
          int n;
          cin >> n;
          if (n == 3)
          {
            cout << 5;
            return 0;
          }
          for (int i = 1;; i += 2)
            if ((i*i+1)/2>=n)
            {
              cout << i;
              return 0;
            }
          

          где тут можно ошибиться? и это долго писать?

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

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

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

              Много кого ты тут научишь наверно. Ладно бы также легко решил D и E вот это было бы круто, да еще бы без i и j, чтобы ошибок не наловить.

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

          После таких сообщений хочется вспомнить Ферлона, его мнение насчет "я красный, а ты — синий, вот и молчи". Я решаю ненамного лучше вас, но, все же, нелепо обвинять всех участников, что "решают они неоптимально". Есть мнение, что оптимальным нужно считать решение которое придумывается и реализуется максимально быстро и получает АС.

          И разводить холивары по таким глупостям — как-то нелепо. Да еще и детьми всех называть :)

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

            Нелепо было минусовать коммент только за то, что в нем утверждается, что задача была решена за О(1), а теперь можно утверждать, что я везде неправ, если каждый мой комментарий вырвать из контекста.

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

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

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

    Я смотрю, тут некоторые перешерстили все мои коммиты, и даже детально изучили время их отправки. Коль уж я вызвал у них такой большой интерес, потыкал в их ники тоже. Чего и следовало ожидать: все брызжущие пеной ненависти эту задачу сами-то и не решили )

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

Очень порадовала задача D. Не форматом вывода, который тоже хорош, а именно тем как я её выдумывал, пришлось поломать мозги некоторое время. Идея моего решения в том, что ДП нужно вести последовательно по массиву слов слева направо, в состоянии кроме позиции в массиве слов присутствует маска и текущее число инверсий. Если у нас ранее (на более ранней позиции массива) была обработана пара (число инверсий, маска) то теперь нет смылса снова считать её снова, вроде как выходит 15 * (500 000 + 2^15 * (15 * (15 — 1) / 2). Интересно увидеть авторское решение, жду разбора.

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

    Можно другое ДП делать: номер позиции в которой может заканчиваться такая маска и кол-во инверсий, там еще нужно будет предподсчитать для каждого символа номер следующего каждого цвета. Тогда отсечения не нужны вроде, и сложность легко считается.

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

А разбор будет?

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

А почему никто не заметил, что в задаче 202B - Инновационно новая простая задача пример с копипастой из мультфильма 12oz Mouse

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

Div 1. A 201A - Четкая симметрия: "Назовем матрицу A симметричной, если она в точности совпадает с матрицами, образованными из нее горизонтальным и/**или** вертикальным отражением.". Зачем писать "или"?

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

omg tourist round