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

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

Завтра, 6 августа 2015 года в 13:00 МСК. состоится финальный раунд Яндекс.Алгоритма, в котором 28 лучших участников будут соревноваться за призовой фонд в размере 540 000 рублей.

Следить за ходом соревнования можно будет на сайте Яндекс.Алгоритма.

UPD И мы поздравляем tourist с убедительной победой! Второе место занимает Petr с третьим местом поздравляем eatmore!

Результаты

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

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

Будет ли онлайн зеркало?

Если и не одновременно с финалом (мало ли, чтобы не упало ничего), то было бы круто сразу после него, пока финалисты не успели заспойлерить в обсуждении все, что можно.

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

    Обязательно начнем сразу после окончания раунда!

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

      заходите на страничку соревнования и вы сможете поучаствовать виртуально

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

Когда ждать разморозки?

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

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

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

      Нда, у меня E по ТЛ упала и F по WA.

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

        Не очень понятно, как может упасть F. Я пробовал вносить в своё off-by-one баги — сразу первый сэмпл становился SHUFFLED.

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

          Есть набор багов, которые можно допустить в решении с перебором seed-а, соответствующего числу. Например, неправильный wrap-around для uint32 или (как раз и случившееся) неправильное округление при целочисленном делении. Тесты 61-72 ловят как раз такие ошибки.

          Ещё можно написать вероятностное решение с недостаточной вероятностью правильного ответа.

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

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

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

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

              Эти баги происходят, когда результат вблизи ( ± 1) от сида равен 0 или 99999999, так что вероятность 10 - 8. На случайном тесте, даже если это делать в каждой из 105 точек, получается всего лишь около 10 - 3 вероятность напороться.

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

                Хм, извини за тупняк, но всё ещё не понял, что особенного происходит рядом с 0 или 10**8-1. Можешь привести пример кода?

                Если неправильное округление при целочисленном делении, то вероятность порядка 1/43, так как ошибка при любом сиде может случиться?

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

                  Из пойманных багов:

                  1: x1 = s·108 / 232, значит, . Можно написать s = (x_{1} << 32) / 100000000 + 1 в целых числах и поймать баг, когда делится нацело (а это происходит, когда x1 = 0).

                  2: Можно завести переменную s типа uint32, перебирать, пока s ≤ (x1 + 1)·232 / 108 - 1, и получить вечный цикл при x1 = 99999999.

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

      А как C решается?

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

        Стартуем с дроби со знаменателем 2 и всякий раз будем брать знаменатель, равный наименьшему простому делителю числителя предыдущей дроби (если такой знаменатель уже был на i-м месте, то ответ — цепочка от i-го места до текущего). И не позднее, чем через P(N) простые числа закончатся, так что повторение неизбежно. Максимальная длина цепочки — P(N).

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

        Будем рассматривать только дроби с простыми d, заменим каждый u на любой простой делитель. У нас получилась функция, в ней надо найти цикл

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

    Еще минут 5

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

Как-то в три часа ночи правильно прочитать уведомление пе получилось. Увидел "можно выводить произвольное число, а не ровно N/10", подумал "ну в условии же так и написано: любое не больше N/10, ничего не поменялось". FAIL. Правда, не очень-то и помогло бы.

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

When did tourist not win onsite finals?

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

Возможно я что-то не понимаю, но 31 июля мне пришло письмо такого содержания:

Hello Jacob Dlougach!

The final round of Yandex.Algorithm-2015 is sheduled for August 8, 13:00 MSK and will last for 100 minutes.

С тех пор больше писем не приходило, и я был в полной уверенности, что контест будет 8-го...

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

    Мне такого письма вообще не приходило. Враги какие-то прислали

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

    Хо-хо-хо. А в русской версии так:

    Здравствуйте, yeputons!

    Финальный раунд Яндекс.Алгоритма-2015 состоится 6 августа в 13:00 и продлится 100 минут.

    Удачи! Команда сервиса Яндекс.Contest.

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

      Это просто отсеивание нерусскоязычных участников, как на VKCup :D

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

    Привет! Действительно, произошла опечатка с моей стороны. Мне очень жаль, что так произошло. Подложенная под дату и время ссылка на timeanddate даже указывает на правильное время (я действительно сделала эту опечатку непредумышленно)

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

      Я конечно заинтересованное лицо, но если все так и было, то казалось бы однозначно контест нужно переигрывать?

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

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

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

          Кажется, не подписать его как раз можно: в правилах и в согласии упоминание этого согласия есть только в разделе 10 правил про призы. Предоставить подписанное согласие надо в срок до 14 календарных дней после подведения результатов. С другой стороны, рассылали и просили его подписать до конца июля, конечно, но именно что "вежливо просили", а не "по правилам надо".

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

The finals problemset authors:

GlebsHP A,D

Endagorion B

snarknews C

misof E

Gassa F

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

For those who don't read Russian comments and didn't notice: there's virtual participation available now.

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

How to solve C if you can choose at most N/10 fractions?

I was wondering why this constraint was removed.

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

    First version of the problem had no constraint related to powers of prime as denominators, instead it had N/10 and N was between 10^5 and 2*10^5 (and no readable sample, because of this limitation). For these N number of primes P(N) is not exceeding N ~ N/10.

    With both of these constraints for small N, when P(N)<N/10 exists sets of fractions where such a selection is impossible.

    Unluckly, some necroediting happened and constant was returned in the new version.

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

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

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

    уже совсем скоро в блоге Яндекса на Хабре

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

      В разборе по A какая-то нереальная жесть написана.

      Отсортируем точки по иксу, а при равенстве по убыванию игрека, и сложим в обычное одномерное дерево отрезков по этому порядку, которое умеет находить левый максимум на отрезке. Дальше просто поддерживаем множество активных точек в хипе по приоритету, и при удалении точки достаём новые точки на границе с помощью дерева отрезков, всё в сумме за O(nlogn).

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

        В разборе написано решение жюри. Твоё решение проще и быстрее, но о нём мы узнали только из твоего сабмита :)

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

can anyone tell the difference between check sign and plus sign (on standings) ?

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

как там дела с футболками? 2 месяца назад было письмо с просьбой заполнить форму с адресом в течение месяца, и с тех пор тишина...

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

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

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

It seems that for third year in a row Petr failed one of his "blind" submissions preventing him to claim the first place: 2013, 2014, 2015.

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

How to solve problem A?

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

I find a tutorial in the site:https://habrahabr.ru/company/yandex/blog/264253/,however it's in Russia.The English version translated is not clear.