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

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

Добро пожаловать на Codeforces Round #134!

После более чем двух лет, я снова с большим удовольствием выступаю в качестве автора контеста на Codeforces. Большое спасибо Gerald за помощь по подготовке контеста. Я надеюсь, что вы получите удовольствие от решения задач ничуть не меньшее, чем получили мы, пока готовили эти задачи для Вас.

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

Всем удачи!

P.S. Данный пост является переводом оригинального поста на английском языке. Комментарии на английском приветствуются.

Update: Контест закончился! Результаты:

First division:

  1. rng_58

  2. panyuchao

    pieguy

  3. tourist

  4. Petr

  5. ACRush

  6. Zhukov_Dmitry

Все участники из top 7 решили по 3 задачи. Обратите внимание, два участника заняли 2е место.

Second division:

  1. dsbuaa

  2. hqztrue

  3. Gullesnuffs

Во втором дивизионе 17 участников решили по 4 задачи. Никто не смог сдать задачу E, которая так же была задачей C в первом дивизионе. Эта задача оказалась достаточно хитрой, даже для "прокаченных" участников из первого дивизиона.

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

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

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

Анонс как-то слишком заранее сделан... Давно такого не было.

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

    А CFR129 давно был? И в нем анонс еще раньше сделан.

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

    Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).

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

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

Неплохо было бы сделать регистрацию не с часа ночи, а с вечера, например, часов с 6.

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

Thanks for your hardwork,and I must say that I love the sentence "but the problems will be ordered by their expected difficulty, from easiest to hardest" most.Hope to solve as much as I can.

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

ждем)))

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

Registration duration is diffirence,only 9 hour and 30 minutes, will be start 01:00AM,will be end 10:30AM

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

And the score distribution is… :-?

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

Good luck, everybody!

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

I'm so happy, that round start 5mins after full hour :D

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

На чем ломали B?

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

Объясните, пожалуйста, D div 2) Больше часа на ней просидел( Explain , plz , D div 2)

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

Great contest! All tasks were very interesting, even A(Div 2)!

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

Что представляет собой тест №9 в Е?

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

Сорри, поспешил.

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

2028500 — Не является ли это нарушением правил?
upd. Я просто спросил) Ибо второпях на контесте мне показалось, что это сделано именно для того, чтобы мне помешать поломать) Если все в порядке, то ладно, простите, ложная тревога.

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

    Это просто комменты на русском языке в непонятной кодировке. Обфускации тут нету.

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

    С чего вдруг? У человека кодировка другая, комментарии вообще тебя не должны касаться.

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

    See this one and this.

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

      This is dsbuaa, who took 1st place, and their codes are look so same.

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

      Question to admins: will smth apply to contestants who copied?!

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

      В бан обоих!

      UPD: Всех троих, а насчет которые заканчиваются на "bua" надо еще посмотреть.

      UPD: Задачи A div 2 и C div 1 также у этих "bua" совпадают, просим бана

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

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

        В прошлом контесте было абсолютно также domain и dsbuaa, код совпадает с точностью до знаков препинания. Дальше лень смотреть, но кажется тут с ними все ясно.

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

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

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

Великолепнейший контест! Я в восторге! Спасимбо автору! Задачи, на мой взгляд, были сразу понятны и не требовали знаний каких-либо сложных алгоритмов (в первых 3-х задачках, просто другие даже не читал). Требовали от участника немного поразмыслить и хорошо реализовать.

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

Problem B is fine. Solution is easy but I could not guess it during the contest...

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

черт, моя С упала из-за одного криво перебитого из таблички байта. поправил — зашло =_=

UPD. контест, тем не менее, понравился. особенно когда после конца допер таки до решения B...) спасибо.

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

Nice problem-set but two 500 pointers in div 2, and no 1500 or 2000 pointers in between 1000 and 3000 seemed odd.(Though it happened due to dynamic scoring)

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

It's a nice contest!Well done problemsetter meret!

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

How soon will the rating be refreshed?

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

Nice problems.I'm looking forward to tutorial because nobody solved all problems.

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

Nice problem C div 2. I was studying Graph Theory some hours ago and I got AC in this problem with a DFS.

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

Объясните мне, пожалуйста, ответ на 6-й тест в задаче B div1.

Ответ выглядит вот так: 6

TBBTBBBBBTBTBTTB

Теперь, приписывая снизу "правильную" последовательность:

TBTBTBTBTBTBTBTB,

я вижу расхождения в 10 символах, а не в 6.

Что я не так понял в условии?

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

    Количеством ошибок считается кол-во пар рядомстоящих символов, которые одинаковы.

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

    Вы не поняли, как авторы определили понятие "ошибки"

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

    ответ это количество пар одинаковых соседних символов, а не количество расхождений с правильной последовательностью

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

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

      >> К сожалению, Байтек иногда ошибается и повторяет операцию два или более раз подряд.

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

        И где противоречие между этими двумя условиями?)

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

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

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

Problem E is so Hard..

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

Задачки были супер! Лично мне очень понравились вторая (на реализацию) и третья (я делала системой непересекающихся множеств). Спасибо авторам за чудесный контест!

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

is there any other way (other than graph theory) to solve the problem C(div 2)?if yes,can anyone provide a hint..

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

А когда появится разбор задач? :о

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

С (div2). Я никак не могу понять одного момента.. Пусть нам дано n не связных между собой "сугробов". Разве есть случай такой расстановки этих "сугробов", что для их связывания необходимо создать минимум n, а не (n-1) дополнительных ?

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

    Чтобы соединить n вершин в целую компоненту связности, нам же надо n-1 ребро. А, ставя сугроб в этой задаче, мы, как бы, проводим ребро. Значит ответ на ваш вопрос : "нет"

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

    Нет, такого случая не существует.

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

[user:meret]will someone write the editorial???

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

In Problem B Div.1 (Blackboard Fibonacci), I try to run the large test case (999997 999997) in www.Ideone.com and my laptop then I got runtime Error. But when i submit it to Codeforces system, it accepted :-o (Although the final test has the same test case :-o)

My submission:

Can anyone tell me why?

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

    Maybe problem is in stack size, because you use recursion.

    Here, on CodeForces, stacksize is increased for g++ using compilation string

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

      Thank you!

      Upd: Another Online Judge don't increase stacksize :-(, so my solution can't get AC in some problems. Is it possible to increase stacksize in C++ source code :-(.

      As far as I know #pragma comment(linker, “/STACK: 268435456”) works only in MS Visual C++.

      How about G++ compiler ?

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

        AFAIK, there no way to do in G++, but you can write your problem not recoursively(or use MSVC++, of course)

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

I don't know if DIV I — C was so hard or DIV I — B was hard enough that people spent a lot of time in that problem and didn't have enough time for problem C.

BTW... My solution for DIV I — B was hacked during the contest and I couldn't fix it... The test case? 1 1... I hardcoded it as

T

instead of

0 T

EDIT: Fixing that case passed system test after contest was over.

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

Как решалась С div2 (A div1)? Почему с-1 (где с-количество компонент связности) неправильно? upd: Если это правильно, то как их тогда считать? Почему не работает такой подход: заведем 2 массива bool по 1000 элементов (назовем их ax,ay — в них будем хранить в i-ом элементе true если на этой горизонтали(вертикали) есть вершина), пусть теперь добавляется вершина (x,y), если ax[x]==false и ay[y]==false — увеличим счетчик; потом установим ax[x]=true, ay[y]=true

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

    Это правильно. Нужно лишь правильно найти компоненты связности.

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

    (1, 1) (2, 2) (2, 1) (1, 2)

    Если добавлять по очереди, алгоритм даст 2 компоненты.

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

    Ломал похожее решение, выше уже ответили, почему это не так. Количество компонент связности нужно было искать как количество компонент связности в графе, в котором ребра имели сугробы с одинаковыми x или y, то есть построить граф, а затем пробежаться несколькими поисками в глубину, или же как количество различных множеств в системе непересекающихся множеств, построенном по аналогичной схеме, что и граф, что почти тоже самое, но немного по-другому реализованное — здесь ты сразу все вершины из компоненты объединяешь во множество и таким образом тебе, как в первом случае, не придется бежать по этому всему поиском в глубину, а можно сразу выдавать ответ.

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

    Вроде бы это верно. По крайней мере верно такое решение: считываем x, y. Если не было такого x, то увеличить ответ на 1, если не было такого y, то увеличить ответ на 1. И в любом случае вычесть 1. Если я понял, ты это и имел ввиду. Но только массивы нужно сделать размеров в 10000 элементов, а не 1000. Потому что координаты до 10^4.

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

Thanks for holding a match at a different time than usual. I enjoy Codeforces contests but have a hard time competing at the usual time. I enjoyed these problems and hope I don't have to wait so long before my next contest.

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

    To the opposite, it was really hard for me to compete here, in Russia, because of that awful Saturday morning:( I wish next time morning-contests would be held one or two hours later — just to have a good sleep... please!:-)

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

      Oh, common, 11am is not a problem, SRM at 5am is :)

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

      Please think about other countries.For example,the usual contest time(7:30PM Moscow Time) is 11:30PM in China.So I think we should have more contests at times like this one.

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

Could anyone tell me how to solve Problem E of Div1?Thanks.

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

Как решать (D(div2), B(div1)) и (E(div2), C(div1)) ?

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

    C (div1):

    Основная сложность этой задачи, это найти, при каких условиях можно определить вид каждой колонии, а при каких нельзя.

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

    Если первый вариант не выполняется, то рассмотрим более общий. Колонии можно определить, если выполняется следующее условие:

    f (x1, x2, .. xn) != f (!x1, !x2, .. !xn), где x1, x2 .. xn — некоторые значения литералов (0 или 1), f — наша функция.

    Допустим, существует такие x1, x2, .. xn, удовлетворяющие условию выше. Мы можем записать следующее:

    f (0, 0, .. 0) = f (1, 1, .. 1) = f (x1, x2 .. xn) != f (!x1, !x2, .. !xn).

    Мы можем предположить, что все x = 1 это одна колония, а все x = 0, это другая колония. И перебирать все комбинации двух колоний. Тогда у нас может получится один из 4-х вариантов, описанных выше. Если мы получили значение функции f (!x1, !x2, .. !xn), то мы сразу же можем определить вид наших двух выбранных колоний, а определить вид остальных колоний уже дело техники. Ну и следует заметить, что значение n нам вообще не важно, главное что оно >= 2 и что не все колонии одинакового типа.

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

    Теперь, как непосредственно технически решить задачу. Нужно распарсить наше выражение в дерево разбора, вершина это либо литерал, либо операция. У каждой вершины у нас будет не более двух сыновей. Мы можем запустить динамику по нашему дереву следующую [номер вершины][значение вершины при f (x1, x2 .. xn)][значение вершины при f (!x1, !x2 .. !xn)] = может такое быть / не может такое быть.

    А пересчитывать совсем просто. Нужно брать значения двух наших сыновей у вершины и делать ту операцию со значениями f левого сына (x1 , x2 .. xn) и f правого сына (x1, x2 .. xn), f левого сына (!x1, !x2, .. !xn) и f правого сына (!x1, !x2, .. !xn), которая и стоит в этой вершине.

    Ну и если мы в итоге можем получить в корне: d[корень][0][1] = true, или d[корень][1][0] = true, то очевидно, мы сможем подобрать f (x1, x2, .. xn) и f (!x1, !x2 .. !xn)

    Рассматривать отдельно первый вариант с заменами всех литералов либо нулям, либо единичками не нужно. Он просчитается в динамике корректно сам.

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

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

      А можно пояснить, почему условие f (x1, x2, .. xn) != f (!x1, !x2, .. !xn) является необходимым и достаточным?

      По-моему, возможна ситуация, когда f (x1, x2, .. xn) == f (!x1, !x2, .. !xn), но при этом f (x1, x2, .. xn) != f ( x1, !x2, .. !xn) и т.д.

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

        x1, x2, .. xn это просто комбинация из 0 / 1, которые заменяют все '?' !x1, !x2, .. !xn это обратная комбинация.

        Если такая комбинация существует, что f(x1, x2 .. xn) != f (!x1, !x2 .. !xn) еще при условии, что f (0, 0, .. 0) = f (1, 1, .. 1), то ответ можно найти. В задаче не важно какая это конкретная комбинация (можно сказать ученые могут найти все комбинации сами), их может быть несколько, нам важно только, что она существует. Ее и нужно использовать для определения колоний.

        Мы перебираем и рассматриваем 2 колонии. Есть 4 варианта, какие конкретно виды бактерий находятся в этих 2 колониях — (0; 0), (0; 1), (1; 0), (1; 1). Вот мы и вставляем в x = 0, значение первой колонии, а в x = 1, значение второй колонии. И тогда все эти 4 варианта покрываются. 3 из них дадут одинаковое значение, а 4-ый даст противоположное. Вот как раз (0; 1) или (1; 0) даст нам наше противоположное значение и мы сразу же можем определить их вид.

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

          спасибо за пояснение, буду дальше осмысливать..

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

Друзья, кто нибудь знает, появится ли разбор контеста от автора? Очень жду)

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

Could anyone tell me how to solve Problem C of Div1 (Problem E of Div2)? I have seen some codes but I still can't understand them. Who can give me some hints or useful conclusions to solve this problem? Thanks very very much!

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

    It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {c1, ..., cn}.

    Replace each '?' by either ci or cj, i and j being arbitrary for now. Look at the values in the four cases (ci, cj) = (0, 0), (0, 1), (1, 0) or (1, 1).

    For example, for (ci&(ci&cj)) we would get 0, 0, 0, 1. Note that there's only one way to get 1.

    • If a "3 versus 1" or "1 versus 3" can happen, then choose the right i and j, and the answer will be "YES".
    • If a "2 versus 2" of the form 0, 0, 1, 1 or 0, 1, 0, 1 or 1, 1, 0, 0, or 1, 0, 1, 0 can happen, you can deduce ci or cj, the answer will be "YES".
    • If none of those situations happen, the answer will be "NO".
    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you very much.Supose that F(ci,cj) is the result of permulation,what is the inital value of F(0,0) F(0,1) F(1,0) F(1,1)? Thank you.

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

        You can compute the values taken in the four cases recursively. Look at this submission for a better idea: 2032900

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

      Could any one can explain why "not all colonies are of the same type" is so important ? ..

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

      Could anyone provide some tricky test cases for Div1-C? I am failing case 13 and its huge :/ (all the tests after 13 are huge too..) Thank you.

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

why the editorial is not uploaded yet ?

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

It looks weird to have 7 people in top 6 when the "6th" place is non-tied. If there is a 2-way tie at place n, I believe the standard way is to denote the next place (n+2), not (n+1).

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

    This is how I did it in the code of the message, for some reason the system replaces it with the enumeration that you see.

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

No editorial yet ... :/