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

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

Всем привет. Меня зовут Михаил Тихомиров, и сегодня я — автор раунда. При подготовке задач мне очень помогли Геральд Агапов (Gerald) и Артем Рахов (RAD), условия на английский язык перевела Мария Белова (Delinur), за что им от меня огромное спасибо.

Сегодняшний раунд пишут участники из обоих дивизионов. В каждом дивизионе пять задач, задачки будут пересекаться, в общем, все как всегда. Разбалловка задач в каждом дивизионе сегодня также стандартная (500-1000-1500-2000-2500). В общем, самый обыкновенный раунд. Или нет?.. =)

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

Раунд завершился, всем спасибо!

Результаты:

div1:

  1. tourist
  2. peter50216
  3. Egor
  4. YuukaKazami
  5. gchebanov
  6. kelvin
  7. shangjingbo
  8. rowdark
  9. kterry
  10. rng_58

div2:

  1. jonathanasdf
  2. Tranvick
  3. ProForward
  4. Eurekash
  5. neex.emil

Теперь полный разбор здесь.

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

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

Спасибо! Желаю всем хорошего раунда! Чтоб после раунда никто не шел топиться из-за забытого else)))

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

Thank you Endagorion~

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

Всім удалого контесту!!!

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

Господа, представьте, сколько должно было произойти случайных событий во Вселенной, чтобы кто-то оставлял здесь комментарии с целью заполучить рейтинговые очки! =)

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

    Желать удачи можно и искренне. Разве это делается ради очков

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

      Да ладно? Наверное, это вы тролите так:)

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

Заинтриговали :)

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

Wish you best of luck! ;)

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

Классный раунд, и задачи хорошие, и багов не было. Побольше б таких.

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

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

Делал D с помощью факторизации чисел через решето эратосфена и масива на N сетов. Асимптотика O(7 * M * logX) , Х — размер каждого из сетов, не могу оценить точно. Это зайдет?

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

    а размер не максимум 1?

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

      Допустим простой делитель — 2. И у нас вставляется 2, 4, 6. Тогда во втором сете у меня будет 3 элемента. Как можно было от этого избавиться? Просто если потом приходит запрос на удаление двойки, то не придумал, как запихнуть на ее место четверку.

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

        Если вставили двойку, то ни 4, ни 6 вставить не удастся.

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

          Ой, точно. Блин, как я так...

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

          Вот я... барашек)) Тем не менее, классный раунд!

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

          Тогда такой вопрос. У меня массив на 100 000 сетов. Значит он сначала вызовет 100000 конструкторов или это происходит как-то иначе?

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

            вызовет

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

              Не знаете, насколько это медленно?

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

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

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

            Это нормально.

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

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

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

    <GRAMMAR_NAZI> ахринеть — это когда в одном слове "ахринеть" две ошибки </GRAMMAR_NAZI>

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

Спасибо автору за интересные задачи,побольше бы таких! Жаль что времени мало=)))

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

Thank you Endagorion, nice problem set! Especially loved the Flatland Fencing (problem D in Div1).

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

А тесты использованные во время взломов будут в финальных тестах присутствовать?

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

В задаче D (div2) претесты можно было пройти совершенно различными решениями. Не знаю, пройдёт ли моё решение все финальные тесты, но у меня удалось сделать первый успешный взлом :)

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

в тестах С есть тесты ломающие хэши, а то весь контест просидел, думал как без них, оказалось, многие так и посдавали?

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

    Как решать эту задачу без хешей?

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

      если бы я знал, думаете, я бы не сдал?)

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

        Свой вопрос я хотел направить сообществу, раз уж появилась ветка об этой задаче =)

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

      сам решение не писал, ибо опоздал на раунд на 5 минут =_=

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

      итого точное решение за O(MlogM) с маленькой константой

      upd. что то переходы на новую строку криво обрабатываются...

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

    Я написал решение с хэшами с 3-мя модулями, но мне почему-то кажется, что есть и нормальное решение.

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

      да да, мне почему-то тоже так кажется

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

      Разве сортировка вершин по списку соседей не заходит?

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

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

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

        вроде должно заходить, в сумме же O(MlogM)

        UPD TL :(

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

        Если мы про div.1 C, то что если у тебя будет как-то так:

        6 8
        1 2
        1 3
        1 4
        1 5
        6 2
        6 3
        6 4
        6 5
        
        
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Вот же блин... Массив маленький... А такое проходить должно.

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

    В природе существуют тесты, которые ломают хэши?оО

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

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

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

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

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

      Задачу Cubes вроде нельзя хэшами пихнуть

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

        можно, я лично запихал ее туда по 5 (приврал с 10) хэшам вроде)

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

        В этой задаче спокойно заходит, если брать не по модулю INT64, а по большому простому.

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

    Оказалось, есть такие тесты :( Поподбирал основание, зашло в дорешку.

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

Один я каждый раунд плохо читаю условия,и из-за этого теряю мест 60 и более? и да раунд действительно классный,автору море лучей добра)

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

    От раунда к раунду будете читать условия всё внимательнее :)

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

Неприятное (для меня) новшество в системе: когда в коде есть "%lld" в любом месте, посылать очень неудобно, так как выскакивает предупреждение в стиле «вы, вероятно, не умеете выводить int64», перезагружается страница (то есть Back к задаче придётся идти на одну страницу дальше), нужно опять выбрать файл и опять нажать на кнопку. Ещё почему-то при этом иногда лочится посылаемый файл на диске (браузер Firefox), а иногда при нажатии на «Отослать» выскакивает страница с текстом «Access denied».

С таким кодом

\#ifdef WIN32
\#define INT64 "%I64d"
\#else
\#define INT64 "%lld"
\#endif

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

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

    Можно попробовать

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

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

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

        Кстати, в VS2010 проблемы больше нет (да и в одной-двух предыдущих версиях, похоже, тоже), равно как и в последнем MinGW. Дело остаётся за малым — обновить софт на Codeforces и/или убрать предупреждение о I64. А тогда уже можно будет навсегда забыть про всё это и писать код так, как указано в стандарте.

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

        А если сдавать под вижак? Вроде оба варианта должны работать

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

В задаче B(Div 1) нужно было считать, что пока №1 работает — нельзя включить никакие другие?

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

    В условии: "два числа взаимно просты, если их наибольший общий делитель равен 1". Так что нет.

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

    Нет(т.к НОД(1, а) = 1)

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

    По данному определению 1 взаимно просто с любым числом.

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

    Эм, почему? 1 взаимно прост с любым числом, так что его можно включать/выключать когда угодно и при нём можно тоже включать (если не противоречит остальным).

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

Хм... Какие-то опасения у меня. 2й див начал тестироваться, а 1й ещё нет... Вероятно какие-то проблемы в 1 диве.

UPD. Ок, успокоили. :)

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

    да вроде как обычно

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

    На прошлом контесте так же было — сначала див 2, потом див 1, это наверно сделано специально, чтобы система меньше глючила.

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

I must say, C of Div.1 is very very unusual for me > <

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

    Anyone could explain the hash-based solution to problem C? It seems to be very intersting.

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

When will the system test start?

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

    After div2 testing finished I think. Today div2 got test first :)

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

OK, still far from being red. Nice problem set, anyway I hoped I could do it better.

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

I just opened solution of zzy_troy for 155D - Colliders. And his solution happened to be the same as resubmited solution of dnc1994 after I challenged him.

Check it out: 1225624 1228387.

I think "someone" has multiple accounts.

UPD: also check out the hacked solution of dnc1994 1226917

UPD2: during the contest it seemed very suspicious to me that he resubmitted using pascal, since the first submission was written in C++

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

Ну вот, был всё время в топ-20, а прошло в итоге только 2 задачи. :(

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

-7500 in Div 2 ?

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

When will my rating be update?

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

Как это решение решение задачи В в div2 1224894 могло выдержать такой тест-кейс ? 7 1 10000 2 10000 3 10000 4 10000 5 10000 6 10000 7 10000 На локальной машине выдает Seg. fault, на сервере дало корректно 28.

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

Chapeau :)

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

Не понравилась C. Какая-то безыдейная и больше подходит для ACM, где есть шанс ее запихать. Допустил 3 ошибки (использование 3 хэшей для перестраховки, вследствие этого использование отдельного класса для хранения этих хэшей, ну и последняя крышка в гроб — использование мапы вместо сортировки).

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

    Тоже поТЛился? Но мы сами виноваты.

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

    А что вам на С мешает сортонуть?

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

    У меня прошло с тремя хешами типа long long — так что задача так сдается. А вот использование map в подобной задаче, это, простите, ваш косяк, причем очень грубый.

    В конце концов генерите макстест и тестируйте на стороне сервера.

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

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

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

        У меня решения с использованием map/hash_map дают ТЛ (3.0 сек), при том, что решения без них работают 0.9 сек.

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

          Ну, да, им, конечно, учитывая, что оба варианта близки к ТЛ, стоило аккуратно пользоваться (например n раз сделать ++ в одном мэпе, а потом, n раз сделать [] в нём же). Если сделать не 2 миллиона операций (у меня на джаве 3 миллиона за 2.5с ), а 10, то ТЛ вполне логичен.

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

I am getting TLE in Test Case 30 for the problem Colliders.Can someone tell me where to optimize it.Here's the code ->Link .I cant get it.Thanks in advance.:)

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

Подскажите пожалуйста, а как массивы вида long[][] a = new long[n][] в Джаве работают? Куда он тут мои 256мб съел? http://codeforces.net/contest/154/submission/1230351 На плюсах то же самое решение меньше 100мб: http://codeforces.net/contest/154/submission/1230846

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

Hey i'm curious as to how solutions to C handle cases like aaaabbbbaaabbba I tried a few correct solutions out but they give TLE or 0 as the answer o.O

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

Ненависть! Я задачу B сдал со второй попытки, потому что вначале я писал не "Conflict", а "Confilct". Потом минут 10 искал, где ошибка. Правда, она всё равно в итоге заТЛилась на 30 тесте :(

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

The solution of problem c in div1 is using "hash" ? It's so unusal... And "map" will get TLE?

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

    What exactly do you mean by "map" and how do you know that map is too slow only by a constant factor? At least I could imagine that in some cases map compares people with many friends too often. (As an extreme example: Let's not use a map but sort the people (I guess this doesn't make a huge difference). The runtime depends on the internals of the sorting algerithm: The sorting algorithm might be "stupid" and first compare the two persons with the most friends with each other n times and then do quicksort. This sorting algorithm works in O(n log(n)) if comparison could be done in O(1) but it can take O(nm) when persons have to be compared lexicographically.).

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

Задача Д класс! Жалко, что написал неправильный перебор для определения выигрышности/пройгрышности позиции(забыл поставить случай ничьей).

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

    мне тоже понравилась, но только она попроще обычной D конечно :)

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

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

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

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

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

I think there must be many participants ignored the vital constraint in problem A:

Also, each pair has different letters and each letter occurs in no more than one forbidden pair.
It is guaranteed that each letter is included in no more than one pair.

I think writer should make it bold. It's codeforces, not readforces...

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

    That happened to me. But he did write it twice....

    If you take out that restriction and allow letters to be in more than one pair, can it be solved with DP?

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

      Most of the solutions that I read during the round ignored that restriction and used DP (so does mine). I was surprised when I tried to challenge solution that used the restriction and my test turned out to be incorrect %)

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

Interestring, my rating on the contest just went up, now I am 10th DIV2, I was 11th when contest ended. Also, may I know how soon will editorials be posted ?

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

This contest is my favorites... Every problem are clearly presented... Thank you very much Endagorion

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

I think all problems is nice.Thank you Endagorion!Finally,pray for myself not to make mistakes.

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

Is there any way to solve div1-C without hashing?

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

    I think I found an O((n+m)log(n)) solution without hashing. Unfortunately it seems to be too slow by a constant factor. It works as follows:

    (1) Let v(i) be the list of friends of i.

    (2) Sort v(i). Create the list 1..n. Sort it by length(v(i)).

    Then sort each chunk of this list with constant length(v(i)) by v(i) (lexicographically). , so this step takes at most time O((n+m)log(n)).

    Afterwards you can easily divide this list into chunks with equal v(i) in time O(n+m).

    This gives the number of doubles (i,j) which are not friends.

    (3) Add i to v(i) and repeat step 2. This time you get the number of doubles (i,j) which are friends.

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

      Lost of hashing cost about 1s, and time limited is 3s. Many solution in div1 got TLE, because of the big constant factor.I hacked by someone's big test , and got TLE too.. :(

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

    It can be solved using trie that should implemented using hash-table (it is not hashing:) ).

    You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex.

    So, we have exact solution in O(MlogM) time with small constant.

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

Are the editorials coming before the next round??

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

Отличный контест ;)