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

Всем привет!

Участники финала Яндекс.Алгоритм постепенно собирались в Долгопрудном... Каждый делал это по-своему :)

dzhulgakov, pieguy, levlam и Progger оказались самыми организованными и приехали к самому началу Летней Школы, успели подружиться с остальными участниками и начали соревноваться в практической задаче по биоинформатике с использованием кластера Hadoop — молодцы! Двое дружных японцев rng_58 и wata приземлились в Шереметьево 13 июля в 17.55 и уже через час получали свои беджики. Их земляк LayCurse перепутал дату и взял билеты ровно на тот же рейс, только 14 июля :) tourist с папой приехали с утра 14 июля, а dolphinigle прилетел вчера поздним вечером и сказал мне, что я первый человек в России, которого он встретил, кто говорит по-английски :) ivan.metelsky "ворвался" сегодня в комнату организаторов, отсыпавшихся от вчерашней тусовки, в 8 утра; добрался сам, без всяких указаний :) e-maxx подъехал в Москву в 10.38 утра и направился прямиком на соревнование вместе с другими нашими саратовскими друзьями — не без приключений: ведь электрички до Долгопрудного идут с перерывом в расписании с 11.10 до 13.40. ktuan в последний момент решил, что последние универские каникулы он лучше не будет тратить на поездку к нам на финал, а Burunduk1, судя по всему, заработался, обучая школьников, и не отвечает на письма и телефонные звонки (ай-яй-яй, Сережа) — интересно, приедет ли он в последний момент? Petr подрулит к нам на машине из Москвы чуть перед обедом, а мой стажер zeliboba учится в МФТИ и постоянно проживает в том же здании, что и все участники летней школы — наверно придет последним :)

Участвовать в раунде, как всегда, могут все зарегистрировавшиеся. Все, кто не участвует в онсайт-туре, будут писать вне конкурса. При этом соревнование рейтинговое для всех участников Div-1.

Напоминаем, что время контеста сегодня необычное: начало в 16.00 Задачи сегодня непростые, посложнее обычных Div-1 — ждем захватывающей схватки!


Update: Полные результаты

Пара фотографий из жизни школы с участием наших финалистов (Progger и pieguy):
  • Проголосовать: нравится
  • +129
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Удачи всем участникам!
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
А для участников div-2 соревнование рейтинговое?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Нет. Но вы можете принять участие в раунде.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      Почему для участников Div-2 нерейтинговый?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Однако, див-2 участники обогнали некоторых из высшего дивизиона. Делать нерейтинговым контест для них несправедливо, разве нет?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Менять правила после соревнования гораздо более несправедливо.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

    > Нет. Но вы можете принять участие в раунде.
    ... и попытаться решить хотя бы одну задачу быстрее, чем Petr сдаст все
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Сдаётся мне, никто не сдаст все. Даже на обычных див-1 раундах не всегда кто-нибудь сдаёт все, а тут задачи будут посложнее...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Мой ответ следует понимать математически.

        Либо задач, посильных участникам div-2, не будет, либо Petr сдаст все.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        просто Petr не всегда участвует
        • 13 лет назад, # ^ |
            Проголосовать: нравится -28 Проголосовать: не нравится
          Ну ладно вам, CBR 77. Петр не такой уж сильный, он не как tourist среди остальных школьников.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится
            Да, и он на самом деле не Petr, а Petr
            • 13 лет назад, # ^ |
                Проголосовать: нравится +17 Проголосовать: не нравится
              на ваши ссылки я уже боюсь нажимать
              • 13 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится -31 Проголосовать: не нравится

                Вот на эту и правда НАДО. На остальные нельзя.
                • 13 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится
                  теперь ссылка выше плюсует топик
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Эй, так нечестно!
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Да почему? Этот баг не так давно нашли. Он уже известный и скоро его уберут. А пока следить надо, куда нажимаешь. Да и к тому же предупредили - не надо нажимать.
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

                    ==================================== dalex верно уловил идею.

                    А ты зачем на гугл полез, а? Я вот на 3м раунде гуглил порождение М-последовательностей (протупил, думал, они редки) => я оранжевый.

                    Яндекс-контест надо яндексом искать, вот к чему я.

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

                      ==============================
                      Шутка была бы шуткой, если не
                      <a class="topic-vote-down-2290" href="http://google.com">
                      Вы как будто не знаете, что от надписи "не нажимать" нажать хочется сильнее.
                      Я к тому, что снижать рейтинг такими методами - не есть правильно. Точнее, совсем неправильно.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

            См. топкодер. Там он по прежнему первый. Так что ты скорее всего ошибаешся.
            UPD: Приношу свои извинения, не так понял
            • 13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              Вы не поняли. Да, он первый, но не настолько, как турист первый среди школьников. Вот, например, его выступление на последнем ВКОШП
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +9 Проголосовать: не нравится
                Как мне сказали после разбора "Задача K была придумана специально для Гены".
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
А можно побольше фоток с места событий?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Однажды можно будет :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится
      Было бы классно по болеть за участников наблюдая за онлайн трансляцией онсайт раунда как на АСМ ICPC.
13 лет назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

Две опции: либо стать оранжевым, но потренироваться, либо остаться красным, но остаться без тренировки. Мне первое больше по душе :)
  • 13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится -31 Проголосовать: не нравится

    Если слить станешь. Я гарантирую это :)

    Сам так сделал.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Что за ерунда, как сложность задач влияет на вероятность падения рейтинга конкретного участника? Задачи - они ведь для всех одинаково сложные.
      Сам участвовать не буду, но по другой причине: раунд слишком рано, я только с работы пришёл, а мозг у меня как винда - при большом аптайме оперативка мусором забивается и всё тормозит. Уже так фиолетовым становился, больше не хочу :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится -9 Проголосовать: не нравится

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

        Самое близкое к истине, наверное, модели вроде задач Триатлон и Турнир Джедаев (ссылки безопасны, я гарантирую это)

        • 13 лет назад, # ^ |
            Проголосовать: нравится -9 Проголосовать: не нравится
          Это-то так, но мы ведь не знаем, будут задачи сложнее, чем обычно, в идейном плане, в реализационном или в обоих. Если в обоих - то они всё-таки в примерно равной мере сложнее для всех.
          • 13 лет назад, # ^ |
              Проголосовать: нравится -15 Проголосовать: не нравится
            Прошлые туры яндекса были с достаточно сильной идейной составляющей. Так, например, до 3 раунда GCJ я сдал все, а на раунде 1 яндекса лучше не вспоминать.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится
    Паша - глупый, Паша ошибся.
13 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
Очень круто, что можно писать онсайт соревнование вне конкурса (если не прошёл на финал). Жалко не на всех онсайтах есть такая возможность
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Что-то долго ожидается. Или задачи будут тестировать по одной, под вздохи всей аудитории ? :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    написано в топике: "Внимание: контест закончен, но результаты будут известны сегодня вечером, не позднее 21.00, после награждения на онсайте."
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      К чему такая конспирация интересно, почему бы сразу не показать результаты.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Затем же, зачем и заморозка монитора на ACM ICPC. Интрига перед награждением :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Только жалко "болталку" отключили, хотелось почитать сообщения болеющих=)
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          А еще организаторы наверняка добавят все взломы (на это нужно время)
13 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится
На мой взгляд условие задачи В написано несколько некорректно. Я (как и, не сомневаюсь, авторы) знают, что в множестве по определению все элементы различны. И в условии 5 раз сказано, что дано множество. Но в конце всё же написано, что гарантируется, что все точки в нём различны. А про вывод такого несказано. Это приводит, как минимум, к двусмысленому понимаю условия: можно подумать, что в выводе точки не обязаны быть различными.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Да, я с Вами согласен, но в ответе вывести только различные точки вроде несложно:) Хуже ответ точно не станет.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Ну да. Но я сначала решил, что точки в выводе могут быть одинаковыми и получил минус =(
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Ну а если так было-бы, то можно вывести продублировано набор точек, и все условия будут выполнены и все просто выходит. Сам сначала оправил такое и получил ВА 1.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Поддерживаю, тоже не понравилось - заслал задачу за 40 с до конца и получил ВА 1. Хоть решение (как потом выяснилось) и было неверным - нервы то свои:)
13 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится
Pending system test?! Who won?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Div2-комнаты выглядят печально.

В следующий раз, когда задачи будут такие сложные, предлагаю что-нибудь поменять. Либо комнаты делать без разделения на дивизионы, либо сделать Div2-комнаты существенно большего размера.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    да уж.

    Да я не думаю, что второе поможет. Из див-2 комант считаные сабмиты прошли претесты.

13 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится
Если кому то будут интересны результаты с финала, то могу побыть инсайдером и писать сюда что там происходит. Стоит?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    думаю, да)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    Открыли столовую. Начался ужин для участников. Предполагаю, что основное мероприятие начнется после приема пищи.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    пошел систест, на сайте его видно ))
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Хочется уже послать решение в дорешивание - когда будет открыт архив?
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Наконец-то началось тестирование
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Петр чемпион :).
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Представляю, как Гене обидно... D свалилась на последнем тесте :(.


UPD. Гена молодец, в отличие от тех, кто мне минусы ставит.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Глядя на результаты тестирования я подумал, что если решение Гены протестировать 10 раз, то в 5 из них оно зайдет, а еще в 5 будет TL.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мы не знаем сложность 72 теста... А так, у меня тоже была такая мысль. И еще появилась в голове мораль для новичков "Don't write in Pascal, write in C" :).
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Посмотрите на тесты чуть более внимательно. Тесты 71 и 72 очень похожи. На одном у Гены что-то типа 3950мс, на другом 4000 и TL. Что-то мне подсказывает, что на этих двух тестах решение Гены делает одно и то же количество операций.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Подождите, где посмотреть? По тому огрызку я не могу сказать абсолютно ничего.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится
            Ну в общем я просто взял и 10 раз отправил код Гены. Он 5 раз упал на 71 тесте и 5 на 72 и ни разу не прошел :).
  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    Ну не всегда же с запасом в 25 мс заходить.

    P.S. Знаю что заминусуют. Не смог удержаться.
13 лет назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

Something is wrong! What is this : ftiasch took 12 place and got only 78+ to the rating...

Edit.: It looks like you accidentally switched div 2 rating mode.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yeah, Petr got +58 for winning Yandex Round 2, but only +22 for winning Yandex Finals, not very logical indeed.

    Perhaps it is because the participation rate is low today.

    Maybe some scaling could be introduced in the formulas for rating changes.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      There should also be some scaling over time, so that rating graphs will be less erratic, and ratings will be more accurate.
13 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

У меня одного такое впечатление, что ограничения по времени выставлены довольно жёстко?...

Моё решение задачи A слегка не уложилась по времени, а в задаче C решение показалось мне медленным и я сделал меньше вершин, чем нужно=( Надо было всё-таки подумать головой, сколько вершин нужно, а не ставить в зависимости от времени работы=)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А у кого-нибудь прошёл чистый перебор в А? Т.е. без домножения ответа на 5040. А то я долго думал пройдёт или не пройдёт и написал с быстрый вариант.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    У меня домножение на 7. Прошло за 310мс.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Круто! Я про оптимизацию в 7  не 7! раз не думал..
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да я тоже не подумал. Хотя писать примерно одно и то же нужно
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну писать в обоих случаях не много.

          Если в 7 раз, то там просто 1 иф добавить: если мы стоим в самом первом квадрате, то ставим в него 0.

          Если в 7!, то надо за порядком следить, чтобы первые встречи каждого числа по возрастанию шли, что включает в себя предыдущую оптимизацию.

          Я на самом деле не подумал про 7!, так бы его написал.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    У меня в дорешивании прошел чистый перебор без всяких домножений за 450 мс.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Диман ну в том, что ты всё что угодно можешь запихать я не сомневаюсь)) Вопрос другой у тебя с плюса прошло?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Petr, grats :)
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Будет ли опубликован разбор задач?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

The problems were nice and challenging. Is somebody going to write an analysis?
13 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится
Why it's not rated for Div-2? When I was registering, it showed me nothing about this.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    It seems discrimination to me as it wasn't some kind of Div-1 contest.
    Either previous rounds shouldn't be rated for Div-2 or rated/unrated thing should be same for both Div-1 & 2 (except the finalists). 
    Moreover, if it suppose to be unrated for Div-2, it should be written in registration page.
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
How to make check program for problem B?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is there a contestant who is not on-site ranked 2nd? I see Petr is 1st and dzhulgakov is 3rd in their information pages.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The problem D... I haven't read it yet, but: it has 4s time limit and 72 tests...

Test 71 and 72 (apparently) are similar (same n, m, k) so it is very sad to see that a solutions passes the 71-th test (on the edge of the 4 seconds limit) but not the 72-th...

from 1 to 70: ok
71-th: 3980 ms (ok...)
72-th: TLE

I think tourist's reaction was something like this. (Especially because he sent the solution just 25 seconds before the end of the contest)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Off-Topic:
In the top photo, who are the contestants wearing white T-Shirts?
Are they twins?

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что за макака на последнем фото (на бумаге) ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я так понял, это Чебурашка
    а чуть ниже крокодил Гена
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
At the last string russian letter is lost =)