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

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

Сегодня мы открываем регистрацию на чемпионат по спортивному программированию Яндекс.Алгоритм-2015. В этом году чемпионат пройдёт полностью в онлайне, на платформе Яндекс.Контест. Участником может стать каждый, кто умеет решать алгоритмические задачи и воплощать решения на одном из 13 языков программирования.

Яндекс.Алгоритм состоит из нескольких отборочных раундов, в каждом из которых нужно решить пять задач за 100 минут. В финал, который состоится 6 августа, выйдут 25 лучших по результатам отбора. Призёров ждут денежные призы: 300 тысяч рублей за первое место, 150 — за второе и 90 — за третье. Кроме того, 512 сильнейших участников Алгоритма получат футболки от Яндекса.

В отборочный этап будет приглашен каждый, кто решит хотя бы одну задачу в тренировочном или квалификационном раунде, которые пройдут 3 и 17 мая.

UPD Тренировочный раунд уже сегодня!

UPD Приглашаем принять участие в квалификационном раунде — он пройдет в формате виртуального контеста, начать который можно до полуночи с 17 на 18 мая. Финалистам ACM ICPC привет =)

UPD Не пропустите первый раунд отборочного этапа Яндекс.Алгоритма, который пройдет сегодня, 24 мая 2015, в 21:00 (UTC+3). Раунд продлится 100 минут по правилам TCM/Time.

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

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

Экспорта в календарь не хватает

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

Финальный раунд длиною в минус год — необычно.  Нужно будет накодить машину времени?

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

    Вернулась в прошлое и поправила =)

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

      Мне кажется, тут тоже косяк:

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

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

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

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

Sorry, form unavailable Need auth.

What's wrong?

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

Готовы ли вы встать в 5 утра ради футболки?

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

    готовы ли вы не ложиться до 5 утра 6 40 ради футболки?

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

      Готовы ли вы выступить на двух других отборочных раундах достаточно хорошо, чтобы не было необходимости вставать в 5 утра ради футболки?

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

        Спросил Боря, писавший первый gcj раунд в 4 утра и занявший без каких-либо вопросов 15 место

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

          Я просто пытаюсь уменьшить конкуренцию на раунде в 5 утра, только тссс...

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

    не совсем понимаю, как определятся эти 512 сильнейших, может кто-то объяснить или дать ссылку на почитать?

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

      дак это в правилах вроде написано
      сначала баллы(гран-при 30), потом задачи, потом время

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

        спасибо, даже не знаю, как я не заметил))

        кто еще не видел, вот описание:

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

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

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

В этом году чемпионат пройдёт полностью в онлайне

Странно, что эту фразу никто до сих пор не прокомментировал :).

К слову, вот тут Egor откликнулся уже через 6 минут после опубликования поста.

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

    Потому что это уже стало мейнстримом

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

    Ну там чуть другая ситуация была, людям пообещали онсайт, а потом его отменили.

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

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

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

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

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

        С другой стороны, в этом сезоне Яндекс организовал такую вещь, как спонсорский зачет OpenCup. ИМХО весьма заметное вложение в финансирование СП. И общий призовой фонд там в несколько раз выше, чем в том же Яндекс.Алгоритм 2015.

        Хотя от этого факт отсутствия онсайта не становится менее неприятным.

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

          Если честно, когда я увидел объявление об этом спонсорском зачете, у меня возник лютый фейспалм.

          Цитирую свои тогдашние мысли: "Яндекс собирается оплатить поездку на сборы таким монстрам, которым ее с вероятностью 99% и так оплатит их собственный вуз".

          А вообще, если задуматься о выражении "аффилированные стороны" в контексте обсуждаемой нами темы, то могут возникнуть весьма интересные гипотезы :).

          P.S. Углубляться дальше в эту деликатную тему я не намерен.

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

            Мы в 1%, значит. Нам никто не оплатил бы Петрозаводск, а сейчас мы бы искали спонсоров для поездки на финал — точно так же, как некоторые финалисты от SEERC в прошлом году. Хотя да, к финансированию СП в России это вроде не относится.

            Да, я догадываюсь, что в России с этим дела обстоят немного иначе.

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

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

              Мы в 1%, значит.

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

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

              Оплачивал Яндекс.

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

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

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

Will you send reminders before every round?

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

Обновите Mono, пожалуйста. Используемой сейчас версии 5 лет уже =/

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

Пытался вспомнить какой у меня там аккаунт на Яндексе

@

Случайно взломал аккаунт какого-то Никиты Рипатти из Перми...

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

    ...тем временем в Яндексе:

    -- Так, уволить безопасников! И нанять Рипатти. Только не перепутайте, правильного Рипатти!

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

Where will be the final round take place?

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

    Russian post version says that the championship will be fully online :(

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

В правилах написано "К участию не допускаются организаторы конкурса, сотрудники Яндекса или аффилированных компаний, а также их близкие родственники"

А в положении о конкурсе написано "6.7. Сотрудники Организатора и аффилированных с ним компаний, иные задействованные в организации Конкурса лица, а также члены их семей могут стать Участниками, но не могут претендовать на выход в финал Конкурса и получение призов."

Чему верить?

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

    Второму, вероятно, т.к. всегда можно с фейкового акка сыграть и никто никогда об этом не узнает.

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

А почему я на главной странице вижу большую кнопку "Зарегистрироваться", хотя я уже зарегистрирован? И вообще, факт того, что я зарегистрирован, на сайте никак не показывается.

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

    И на какой странице ждать задач? И таймер обратного отсчета было бы неплохо ввести.

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

Контест начался — "у вас нет прав просматривать это соревнование" :(

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

"У вас нет прав просматривать это соревнование"

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

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

    Соревнование завершено. Отправка решений запрещена

    Уже лучше :)

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

      Соревнование еще не началось До старта осталось 00:05:39

      Ещё лучше!

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

Why am not I allowed to enter warmup round?

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

Оказалось, проблема с запретом на просмотр не только у меня.

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

Кнопка, по которой смотреть задачки, появилась с опозданием в пару секунд. И она не работает!!! Пишет, что у меня нет прав на просмотр данного соревнования.

UPD: Стало лучше: "Соревнование завершено. Отправка решений запрещена". Теперь хоть можно с чистой совестью идти спать, а не искать способ хотя бы прочитать задачи.

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

We will start the round at 22:10, thank you for your patience

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

Лида, что делать?

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

Всё, контекст закончился.. кто не успел, тот опоздал))

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

Как быстро закончился!

"The contest is over. Submissions are not allowed"

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

А соревнование тем временем завершено))

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

Мне кажется или самая сложная задача контеста, это добраться до задач?

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

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

My friend says he can see the problems but all I get is "The contest is over. Submissions are not allowed". Sounds quite unfair?

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

Я вижу это "Соревнование завершено. Отправка решений запрещена".

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

По-прежнему "Соревнование завершено. Отправка решений запрещена" хотя уже 22:13

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

Можно сделать разминочный раунд виртуальным 24-часовым — и все будут счастливы и не будут до ночи решать задачи :)

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

    Всё же перед массивным онлайном неплохо провести нагрузочное тестирование системы.

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

Позор для Яндекса :)

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

Отправил запрос через "Обратная связь" — пока тишина. Кому-нибудь поддержка ответила?

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

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

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

Кажется уже починили.

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

The countdown timer is shown now.

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

Now it says the contest will start in 3 minutes, but my friend sent me a picture of the statement already... Gonna be a fair competition I see!

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

I saw problem A and started coding it but now it says the contest has not started yet. =.=

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

Ваше решение отправить не удалось. UPD: У вас нет прав просматривать это соревнование.

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

У вас нет прав просматривать это соревнование

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

Снова "У вас нет прав просматривать это соревнование"

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

Just when you thought it's all going well — "You are not allowed to view this contest".

I'm getting Bayan flashbacks here :\

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

Можно по обсуждать первую задачу пока не исправят сервер :)

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

так не интересно :(

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

Даже условие загрузить не успел :(

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

    А я успел и решить, но отправить не успел(

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

В Yandex код вообще тестируют, или сразу в production?

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

3 май 2015, 22:32:36

Соревнование завершено. Отправка решений запрещена

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

What can I do sometimes ?!!!!!

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

А систему отправки задач не предусмотрели? :)

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

"Ваше решение отправить не удалось"

?????

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

"Ваше решение отправить не удалось"... Вроде же Яндекс контест работал хорошо раньше. Как его так сломать то умудрились? :)

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

Whenever I try to submit a solution, it tells me:

"Your solution was not submitted."

Help?

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

I can't submit my c++ solution for A. Any clue? :D

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

Problem B is identical to a problem from Canadian OI, with minor changes to the statement and identical input format/sample data:

http://wcipeg.com/problem/ccc03s2p3

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

    I think all problems used for this round are not new. I don't see any troubles with giving old problems to the warm-up round.

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

      In the rules it says

      For all rounds, the problems will be original.

      Official Rules

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

        Problems in the warm-up (testing) rounds were used on different contests like OpenCup or local contests. Problem about cube was used on some ancient SnarkNews Series; but in there it was taken not from Canadian OI, but from some other source (dont remember precisely, which one though).

        Original problems must be for all official rounds (Qualification, three Online rounds and Online Final). Testing round(s) use selections — main goal of it is to test if the system is working ok and to remind TCM/Time rules to players, and for this goal selection from different sources works okay.

        I met problem with same idea several times in different old contests, so it was added as "classical problem"; i am surprised that number of players solving them is not that big.

        May be, first time it appeared in Canadian OI (atleast format points at it). Btw, tests were changed abit to catch some special cases.

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

Верните кнопку отправить вслепую :)

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

    постараемся вернуть её к 17 мая, она нам тоже очень нравится

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

Huge thanks for everyone who stayed with us until the normal flow of the round. We'll make sure that Qualification round on May 17 will run smoothly.

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

А на что ты готов ради футболки ?! :)

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

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

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

Как решать задачу С и D?

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

    Отражаете одну из точек относительно y=0 и выводите квадрат длины отрезка между точками.

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

      Ты забыл добавить, что выводите ответ. Потом еще выводите точку и 20-ть нулей. Досих пор бомбит от такого

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

        Неужели не очевидно, что сумма квадратов модулей разности целых чисел будет целым числом, но формат вывода никто не отменял?

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

          Про сумму квадратов конечно очевидно. Но формат вывода, эмс, обычно задача читается быстро, и форматы просматриваются мельком. в данном случае, выведите с точностью 20 знаков олололо. Не особо это прикольно вообщем.

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

          А не подскажете, с чего вдруг http://pastebin.com/srsWzmQb не прошло какой-то тест?

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

            Не влезало в int, вероятно.

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

            Если y1 и y2 с разных сторон от y=0, инвертировать y2 не нужно. y2-y1 вместо '+'

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

              Эта ситуация невозможна по ограничениям из условия.

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

                Почему? Координаты могут быть как положительные, так и отрицательные )

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

                  А, нет, извините ) y неотрицательные ) Я по невнимательности решала другую задачу )

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

      Можно код посмотреть?

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

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

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

      Ординаты точек положительны, отражать нужно всегда.

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

    Отразить точку B относительно оси абсцисс и найти квадрат расстояния между точками.

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

    D: сортируем массив и считаем гистограмму количества каждого числа. Минимальный ответ = размер гистограммы — 1. (количество различных чисел — 1)

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      n - общее количество чисел
      maxVal - максимальное количество одинаковых чисел
      ans - максимальный ответ 
      
      если (maxVal <= n/2)
       ans = n - 1;
      иначе 
       ans = (n - maxVal) * 2;
      
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Обозначим точку, первую точку через A, а вторую точку через B. Отразим точку B симметрично относительно прямой y = 0 и получим точку B. Тогда из любого пути AKB (K – это некоторая точка на прямой y = 0) можно, отразив симметрично относительно абциссы его участок BK, получить равный ему по длине путь AKB'(т.к KB' = KB), длина которого по неравенству треугольника не меньше AB'. Значит ответ это квадрат расстояние между A и B'.

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

How to solve C ?!

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

    If points are on the different sides to axis x result is euclidean distance between them. Else change y of first point to -y.

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

      It is stated, that both points are on the top side the river, so you don't have to check whether cities are on different sides of the river.

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

А как решать А? Столько жадностей перепробовал :)

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

    Коннектить две вершины с наименьшей степенью.

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

      ...но я же так и делал :(

      в чем подвох? edit: вот код http://pastebin.com/yL4K6jep

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

      ВА 21

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

        Попробуйте тест: 9 18 4

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

          ну падает. а как можно по-другому написать "выбираем две вершины с мин степенью и их соединяем"?

          vector<pt> ans;
          
          while(m--)
          {
              int mn1 = INF, i1 = -1, mn2 = INF, i2 = -1;
          
              forn1(i, n)
              {
                 if(deg[i] < mn1)
                 {
                   mn1 = deg[i];
                   i1 = i;
                 }
              }
          
              forn1(i, n)
              {
                 if(deg[i] < mn2 && i != i1 && !g[i1][i] && !g[i][i1])
                 {
                   mn2 = deg[i];
                   i2 = i;
                 }
              }
          
              cerr << "vertex == " << i1 << ' ' << i2 << endl;
              cerr << "degs == " << deg[i1] << ' ' << deg[i2] << endl;
              deg[i1]++;
              deg[i2]++;
              g[i1][i2] = g[i2][i1] = true;
              ans.pb(mp(i1, i2));
          }
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

            А сам я отправил то же, что и Fcdkbear ниже написал.

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

    Зашло такое: перебираем чувака у которого степень меньше К, коннектим к нему остальных в порядке возрастания количеста друзей у них пока степень нашего чувака не станет равна к (степень == количесто друзей). В конце если нужно добиваем количество связей до М еще неиспользованными связями

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

    Все вершины поставим по кругу. Если k — четное, то для каждой вершины ее соединяем с левыми соседями и правыми соседями. Если k — нечетное,то каждую вершину соединяем с левыми соседями и правыми соседями, а также соединяем все вершины v, u такие что . Если у нас количество ребер меньше чем M, то просто добавляем ребро между не соединенными вершинами.

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

How to change the country flag that is shown to the right of my name in the standings?

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

Кто же получили футболки?

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

    "20 футболок случайно выбранным участникам этого раунда, сделавшим хотя бы одну посылку"

    Всего 20 футболок. 637 участников. Вероятность её получить 3%. =)

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

      Было бы справедливее "решившим хотя бы одну задачу", тогда количество сократится в два раза :)

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

Как B решать?

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

    Лень регистрировать на яндекс контест, чтобы проверить идею (Может, найдется не ленивый и добавит в Тренировки?), но, кажется, такое должно пройти: проверяем все детали куба на возможность сдвинуть на одну клетку в любом направлении. Если получилось хоть с одной(хотя бы с одним направлением) — непрочный, иначе — прочный.

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

    Прикладываем силу во все 6 сторон к каждому кубику и смотрим, какое количество кубиков при этом сдвинулось. Если оно меньше, чем общее количество кубиков, то куб непрочный, если равно, то прочный.

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

      Достаточно в 3 стороны по очевидным причинам

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

Как вы решали Е про коней? Почему там бфс валится?

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

    Правильно написанный не валится :)

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

    Бфс — это правильное решение. Вот, например, мой код.

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

      Я имел в виду запустить для первого коня, потом для второго. И среди всех (i, j) | d1[i][j] == d2[i][j], выбрать нужную.

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

        поле 5 на 5. в левой верхней клетке стоит (2, 2)- конь, в правой нижней — (1, 1)

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

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

А кто получил футболки так и не отписали

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

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

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

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

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

        Михаил прав, осталось лишь немного подождать. Мы постараемся не сильно заваливать вас письмами =)

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

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

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

    Напоминание было (во всяком случае у меня) еще 30 апреля.

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

      А, да, действительно. Успелось уже и забыться.

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

I can't wait more for the editorial. Can anyone give the accepted code for problem A? Thanks.

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

    You can use Havel–Hakimi algorithm to solve the problem.

    Because there is at least one solution. You can first build a degree sequence with all degrees equal to k. The divide the rest degrees to each element of the degree sequence evenly.

    My code for reference: http://paste.ubuntu.com/10994941

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

      Is it possible to solve this problem ignoring K? I mean, create a sequence of edges based only on N, and then take the first M edges of it. (Yes, the sequence must ignore M too :)

      For a challenge I have been trying to solve A this way, but failed. I still do not know the answer.

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

Sooo, who are the t-shirt winners ?!

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

Каждый раз, когда жюри не пишет авторские решения на джаве, в мире грустит один котик.

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

I couldn't understand open/blind submission. What is difference ?! What are advantages of open/blind. Does blind mean : "I don't need feedback" or sth else ?!

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

    When you use blind way, you dont have feedback but you have additional bonus instead of penalty time. I.e. you choose harder way and are awarded for it with the decreasing of total penalty.

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

      hmm got it... So if my solution gets OK in open submission does it mean I have solved that problem I mean it checks all tests ?!

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

      To be precise, it's not instead of a penalty, it's in addition to penalty (so you have both penalty and bonus)

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

Where can I solve previous Yandex contests?
(of last year and last to last year)

EDIT-1 : Found 2014 in GYM

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

Is there public standings page?

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

    Not until the end of the contest. It will be unfair if contestants who haven't started yet could see someone's final results.

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

    It still would be cool to see the standings for those who are not registered.

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

Вот в правилах сказано:

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

То есть получается, чем в большем количестве раундов ты участвовал, тем лучше? Как-то это странно. Или можно участвовать в одном раунде? Не все же могут поучаствовать в утреннем раунде.

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

Можно ли кеш поменьше сделать для таблички результатов?

После сдачи задачи нужно ждать 1-2 минуты, чтобы он обновился.

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

Huh, memory limit is 64Mb ; o? Kinda completely missed that, I haven't seen such small memory limit as a standard limit for some time and it costed me one problem ; d.

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

    Same for me.

    I'll read statements more carefully. I'll read statements more carefully. I'll read statements more carefully...

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


    Like this ?!
    UPD I understood why minus. I think you you thought it doesn't calculate if your memory exceeds 64MB, but before this submission memory was around 135MB.

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

My first submission stayed with the "waiting" status for about half an hour and I had a stupid bug that I had to wait half an hour to correct. I hope this doesn't happen in the Elimination rounds.

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

А про футболки с тренировочного так в письме и не сказали(кто получил и т.п.)

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

Top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt. what does it mean "cumulative result",there is 3 round,and in each only top 30 user can earn points,3*30=90 and how 512? pls some1 explain me

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

А где можно поменять имя, отображаемое в таблице результатов?

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

What is the solution for Problem B — Optimal Playlist ?

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

    Binary search, then condense strongly connected components and topologically sort them. Components will form a chain iff the required path exists.

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

      What about finding Minimum Cost Spanning Tree in DAG? Would this approach work?

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

        No: for example, in graph (1->2,1->3) there is an oriented tree, but no path visits all nodes.

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

Ah, missed qualification again.

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

Can someone give some hints for problem C? Thanks.

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

    My approach was following. Let's store in f[d][j] j-th parameter of d-th document, in s[d] relevance for d-th document and in some structure r — sorted relevances with numbers of corresponding documents (it was set<pair<long long, int> > in my code). Then for each query it's easy to update. For 2 K it was just top K elements of set. For 1 d j v:

    r.erase(r.find(make_pair(s[d],d)));
    s[d]+=a[j]*(v-f[d][j]);
    f[d][j]=v;
    r.insert(mp(s[d],d));
    
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I used order statistics tree. I guess using STL set container would have sufficed too.

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

А была уже какая-то информация о футболчках? А то я, как оказалось, при регистрации ввел не тот email.

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

How to solve E problem ?!

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

    We need to find the number of pairs (A, B) such that A divides N, B divides M and L <= AB <= R. First generate all divisors of N and M. Then iterate over A (divisor of N). Corresponding B must be in the interval [L/A, R/A]. The number of divisors of M from this interval can be found by binary search.

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

      You may even iterate through all divisors of N and M and just check if L<=A*B<=R.

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

        Yes, it seems that the worst case is the number 223092870=2×3×5×7×11×13×17×19×23, which has only 2^9 divisors, so it's 2^18 pairs at most.

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

          i think the worst case is 931170240. this number have 1344 divisors.

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

          I am pretty sure, that your estimation is not correct (for example, you may use 2*2*2*2*2 instead of 2*23), but you may assume that the number of divisors for such small numbers is O(N1 / 3), and the total complexity of our algorithm will be O(N2 / 3)

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

I'm still unable to understand what Problem B was. Can someone please explain the output of the sample case or any other case?

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

    You should find a path in the given graph with minimum possible max edge weight.

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

Как поменять флаг рядом с ником в таблице результатов?

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

А таблица будет видна тем, кто не участвует?

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

Couldn't understand the purpose of problem X — Fake testing problem.

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

    People were asking for some way to be able to test code on the server in case of compiler configuration problems. I think this solution proposed.

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

    You can build your source file on Testing server and run it. e.g. you can debug TL for your solution.

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

    it's as codeforces's custom test

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

How to solve problem B (Elimination round 1)?

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

    My solution — in cycle pick every city as a center.

    Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.

    After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).

    I bet there are easier solutions but this one got ACed and I am happy with that.

    For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(

    Moved to: Proper thread for discussion

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

      You can use orientation in integers, but use atan2 in doubles?

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

        With coordinates limited by 1,000, double precision should be more then enough for all angles. Though I already see that it was bad solution — over complicated. Costed me 15-20 minutes of my time.

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

          coordinates were limited by 2⋅104
          and with good tests no solution with bad-written doubles should pass imho

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

            If so, I defy you to show us test where atan2 is not sufficiently precise (on long doubles, why not?)

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

              of course it's difficult to construct such test. And in this problem I think atan2 is sufficiently precise
              so maybe using orientation everywhere is paranoia, but a good one ;)

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

          This is overcomplicated? I think that your solution is the simplest possible one. What can be even more simplified?

          I used more complicated approach where I maintained array of prefix sums of possible divisions when sweeping points with line of a fixed inclination and updated it appropriately when rotating this line.

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

            I liked idea of taking pairs of dots and drawing lines between them. I think if this idea struck my mind I would finish this question in 15 minutes, not 35. But I often experience that — coding more complicated solution.

            But thank you for admitting that red coders sometimes do complicated things too. :)

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

              What do you mean by that idea?

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

                Found it in this thread above. I just realized that it is O(n^3), to test all pairs of cities and calculate population on each side. So maybe not good idea. Ok, my solution is not over complicated :)

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

    It isn't real solution, but here's some magic!

    http://ideone.com/YeLtmM

    Rotate point around origin by , and try all possible y axis, as a "divide line". Do it K times.

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

How to solve Problem F — To Saw or Not to Saw?

I got 2 formulae by using similarity of triangles:

  • d * (c - a) / c, when >
  • b * (a - c) / a

Got WA on testcase 3.

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

    ans = gcd(a, c) * min(b / a, d / c)

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

      It may sound really stupid.. but how can one get to this formula?

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

        Let me rewrite it a bit:

        ans = gcd(2a, 2c) / 2 * min(b / a, d / c)

        The first part d = gcd(2a, 2c) comes from the following observation. Let's assign integer numbers to each peak of the saws and let's put two saws so that 0-th peak of the first saw will be exactly above the 0-th peak of the second saw and denote this coordinate as X = 0. If you plot the rest of the peaks then peaks of the first saw will have coordinates xi = 2a * i for each integer i, similarly peaks of the second saw will have coordinates yi = 2c * i. Then you plot all those peaks as points on X-axis and the question is what is the smallest distance of first saw peaks and second saw peaks. In other words what is the min(dist(xi, yi)) = min(abs(2a * i - 2c * j)) for any integer i and j. If you solved enough number theory problems it will be clear to you that this is equal to d = gcd(2a, 2c) = 2·gcd(a, c).

        Now you have this d number. If you plot peaks again you should see that the optimal solution would be to move one of the saws d / 2 units left or right and then move them towards each other as much as possible. How much you will be able to move it depends on the "sharpness" of the saw's teeth (i.e, b/a ratio). Then if you know d already the result is simply l = d / 2 * b / a. Then you replace b / a with min(b / a, d / c) because you need to consider the case when first saw has "sharper" teeth.

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

    well and if a = c ? I put min(b,d) but it's WA on 4th

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

D решил, B не решил. Нормально.

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

Just my luck. Picked the weird looking problem earlier on only to realize there was an easier one waiting. Started solving and couldn't submit by 5 seconds. Submit in upsolving mode and get Accepted.

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

Как решали задачу B?

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

    Задача с очень боянистой (но не очень приятной для кодинга) идеей

    Искомая прямая "почти" проходит через две любые точки (то есть она как бы проходит, но сдвинута на epsilon).

    Решение за O(N3). Перебираем две точки, образующие прямую, для всех остальных смотрим с какой они стороны. Наши две точки пробуем кидать 4-мя способами в одну из двух сторон. Вероятно, это ТЛ, но помагает понять АС идею.

    Решение за O(N2logN). Перебираем первую точку, остальные сортируем по углу относительно нее. Далее интересующие нас суммы можно пересчитывать двумя указателями.

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

Топ 3 сдали задачу в последние две минуты. Хорошо, что я рефрешил таблицу без чая во рту.

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

    Ну я дописал минут за 8 до конца, и тестировал до последней минуты. Сорри :)

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

    У eatmore особо циничное штрафное время, конечно.

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

Can someone start a new thread with editorial to the problems of Elimination Round 1.
I think I can learn a lot from the editorials of this round. Problems were a lil tough for a beginner like me.

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

B — избитый баян. Сколько она мне попадалась, столько я и сидел весь контест дебажил. В итоге не сдал.

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

    same here.

    Зачем она нужна в контесте? То есть я не спорю, что я сам рак и прямую покрутить за час сорок не смог. Но задача же просто делит участников на две группы: уже крутили и сидят учатся крутить.

    P.S. Поделитесь реализацией хорошей, пожалуйста.

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

      Ну, я не крутил, затолкал O(N3logN) с отсечкой по времени.

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

        Классно, что тут скажешь.

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

        Подарите мне кто-то ровные руки. У меня асимптотически верное решение 1.6 секунды работает.

        Кстати если кто-то скажет, почему так медленно — буду благодарен. Код

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

          Может быть atan2 нужно посчитать заранее, а не внутри компаратора.

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

            Да, спасибо, это ускорило решение до 165 мс (в 10 раз на этих тестах, ничего себе).

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

      Отличная реализация. Мне впадлу было крутить, я перебирал (пока TL позволяет) направление прямой и двигал её за O(n).

      Enjoy

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

      Это конечно не крутилка, но все равно.

      http://codeforces.me/blog/entry/18080?#comment-229640

      Тупо куб с branch-prediction хаком.

      cpp — 0.79 sec java — 1.3 sec

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

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

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

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

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

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

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

    Там ещё куб с отсечением по ответу легко проходит (у меня куча посылок, но это WA).

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

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

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

My code (for Elimination Round 1 problem E) gets TLE in test 9 with 2.093s. How can I improve it? What's the problem?

Thank you in advance!

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

Кстати, теперь все раунды должны быть такой же сложности, иначе в борьбе за футболочку возникнет несправедливость

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

    Почему? Раунды же суммируются. Разве что несправедливость в зависимости от таймзоны.

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

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

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

        Скорее наоборот, на более лёгком раунде можно решить больше задач, поэтому тот, кто его пропустит, окажется в проигрышном положении.

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

          Да, точно. В очередной раз убеждаюсь, что мне нельзя писать комменты после часа ночи :)

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

    Таким ходом организаторы убьют сразу двух зайцев: 1) обеспечится турнирная справедливость 2) уменьшатся расходы на футболки ;)

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

My opinion is that problemset was very nice! C, D and F were very interesting in my opinion! B and E were also OK. Unfortunately A was tedious, any deeper thought, just a lot of cases to consider.

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

    You can write A with almost no special cases

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

      How? My solution has about 10 ifs.

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

      OK, that sounded like a challenge, so I went for it and managed to get this accepted by this code: http://ideone.com/kFdFxb It doesn't contain that many ifs (only 5), but it is still tedious >_>... I think that analysis of those cases is nonomittable (case when cur_wid == l[hor] is especially nasty xd) and if you have more elegant solution I would like to see it.

      During contest I didn't give that task a deeper thought, because I haven't even read it, because in half of the contest I have to made a choice which problem to do next — A, C or D. A had least amount of ACs within top people (but now I see that it had much more ACs that time :d) and had longest description, so I disregarded A and choose D since I quickly got and idea how to do this. After contest I thought that it's all about cases, so I didn't think about this much :P.

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

    Are you implying that you haven't seen about 10 problems which are basically equivalent to B? Those half-plane things appear over and over and over again.

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

      Uh, OK, indeed it is not very innovative problem, but at least there was not anything which will cause me to complain about something, for example no restoring result, no collinear points etc.

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

For problem C,I find the fomula: dp[n][k]=dp[n-1][k-1]*(n-k+1)+dp[n-1][k]*k (1<k<n) using bruteforce.But what's the logistic in it?

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

    (I guess that you meant problem C). Don't tell me that it's true :o!? That looks very mysterious for me. I got AC (after contest) using much more complicated DP with n^3 states, some binomials and stupid trick allowing me to fit in O(n^2) space ;__;.

    UPD: Yeah, it looks that it's true, however I don't have time now to wonder why is that. Here's my code: http://ideone.com/GdOSTe but compared to your solution I guess it can be mainly used to make fun of me :P.

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

      Can you explain more about your idea?I really can't understand it.

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

        I consider similar type of game. When we delete only the smallest card, not smallest or largest. Observe that game when there are n cards and we want to end up with k-th card is a sum of two independent games of that type (one with cards 1..k, one with cards k..n) when we delete last card in turns of the same number — this is key observation to whole solution (one of them (k..n) is reversed, that means that we delete the largest card instead of the smallest one).

        Given that I compute dp[a][b][c] which tells how many of such games are that we are given a cards, largest card is on b-th position and we delete it c-th moment we see it. pref[a][b][c] = sum dp[a][1..b][c]

        Fitting in O(n^2) space is little tricky. Given formulas for dp I can compute dp for dp[a][..][..] given only dp[a-1][..][..], I do not need previous values of a, but when counting answer I have to combine games of sizes k and n-k+1, so I either need to separately count this for dp[k] and run everything once again for dp[n-k+1] or observe that analogous property holds for number of checks and when combining games I always combine two games with the same number of checks (I used second approach).

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

          I think the c-th moment factor is also the hard and key point to solve the problem.And it really needs observation.

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

    This formula is also number of permutations with k-1 rises (position such that a_i < a_i+1). It's easy to see why it's correct but I still haven't found connection between that and C problem. Maybe there is a bijection?

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

Как решать D?

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

    Понятно, можно считать l = 0.

    Будем набирать x начиная с младших битов (они идут справа налево). Рассмотрим немного неправильное решение: динамика dp[сколько разрядов прошли][верно ли, что готовый суффикс числа x  ≤  суффикса r][есть ли перенос при сложении k + n]. Проблема такой динамики, что она считает количество подходящих k, а не x.

    Тогда сделаем так: dp[i][gr][маска переносов (1, 2 или 3)] -- сколько таких x, что их можно получить на таком суффиксе, при этом они будут больше/не больше соответствующего суффикса r и все переносы, которые вообще возможны при получении такого x записаны в маске. Тогда все x разбились на не пересекающиеся классы.

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

    Код

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

    Я решил так. Перепишем уравнение в виде (k XOR x) — k = n. Пусть x = 2a1 + 2a2 + ... + 2am — двоичное разложение. Тогда возможные значения левой части — это ±2a1±2a2±...±2am. (Остальные биты от ксора с иксом не меняются, а эти m меняются либо с 0 на 1, либо с 1 на 0.) Если обозначим через a сумму членов с плюсом, а через b — с минусом, то условие перепишется так: a-b=n, a+b=x, a&b=0. Или, избавляясь от переменной a, b&(n+b)=0, x=n+2b. Последнее условие нам дает ограничение на b (x<=r <=> b <= (r-n)/2). То есть нам нужно найти f(n, b) = количество b<=r таких, что b&(n+b)=0.

    Будем строить b начиная с младшего бита. Если n=2n' четно, то и b должно быть четно (=2b'), и при этом n'&(n'+b') = 0, то есть получаем f(n, r) = f(n', r') = f(n/2, r/2). Если же n нечетно, то младший бит в b может быть как 0, так и 1. Аналогично разбирая эти 2 случая, получаем f(n, r) = f(n/2, r/2) + f(n/2 + 1, (r-1)/2). (Деления целочисленные; +1 во втором слагаемом из-за переноса разряда.)

    Тут можно заметить, что 2 рекурсивных вызова в последнем равенстве очень похожи (весьма вероятно, что на следующих уровнях рекурсии они будут вызывать f с одинаковыми параметрами). Кроме того, если n оканчивается на много единиц (плохой случай — много ветвлений), то n/2+1 заканчивается на много нулей (хороший случай — нет ветвлений). В общем, у меня зашла рекурсия с мемоизацией всего за 2 миллисекунды: http://pastebin.com/C1vBnHFs

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

this was hard