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

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

Доброе время суток! С вами снова успевший уже всем надоесть AlTimin и я снова поднимаю себе вклад освещаю второй тур XXIV Международной олимпиады по информатике, который вот-вот должен начаться.

Условия тут

Говорят, что контест начался в примерно в 11:15 по Москве, но итальянцы снова тупят и таблички рельзультов пока нигде нет.

Пока все ждут таблички результатов, напомню про результаты первого тура. Российская сборная: Zlobober (258 баллов, 7 место), tigvarts (213 баллов, 22 место), yeputons (204 балла, 24 место), Copymaster (196 баллов, 29 место). В этом году ожидается примерно 27 золотых медалей (может быть плюс-минус одна), так что у наших есть все шансы взять четыре золота, чего не было уже восемь лет

0:15: Табличка результатов появилась. Контест начался в 11:20 по Москве.

0:18: Первый сабмит! Макс Ахмедов, 11 баллов по первой задаче!

0:30: А теперь о задачах. Их снова три. Первая: найти сумму всех попарных расстояний между клетками некоторой замкнутой клетчатой фигуры, не содержащей внутри себя дырок (то есть её дополнение тоже связно). Вторая: Есть кэш размера K и N объектов. Кроме этого, есть N запросов. При запросе некоторого элемента он должен быть пом ещен в кэш. Хочется как можно меньше раз выкидывать объекты из кэша. Утверждается, что при известной последовательности запросов оптимальное решение — выкидывать элемент, который понадобится как можно позже. Участникам же надо последовательности запросов составить себе некоторую подсказку длиной не более M бит. После этого у них будет в распоряжении только их подсказка, и по одному будут приходить запросы. Надо сделать так, чтобы решение было оптимальным. Третья: есть N рыцарей с силой от 0 до N-1. Проходит некоторое количество раундов вида "взять подотрезок с l по r и оставить только победителя (рыцаря с максимальной силой)". Последний рыцарь опоздал, и мы можем поставить его на любое место (порядок остальных мы знаем). Максимизировать количество раундов, в которых он примет участие.

0:35: Еще самбиты на 32 балла по первой задаче. Сегодня самая простая задача — третья, но она немного неприятна с точки зрения реализации. Думаю, что будет по ней много сотен, начиная примерно с часа после начала контеста.

0:55: Судя по тому, что уже 20 минут нет никаких изменений, то у них что-то сломалось. Надеемся, что только табличка.

0:56: Табличка со мной согласилась и приказала долго жить. 502 Bad Gateway.

1:00: Положил сюда условия.

1:05: Пнул SC. Табличку починили. Из интересного — сотня у Егора. Ждем еще три сотни по третьей от наших.

1:15: Леша получил 32 по первой. У Олега пока ничего, видимо занимается сотней по третьей. А Хо пока чего-то не хо-хо.

1:25: Гена и Егор получили 43 по второй задаче. Китайцы выкатили свое чудо-оружие из Шаолиня. Они совсем не палятся — чувака зовут Chao Li.

1:35: Две синхронных сотни по третьей задаче. Макс и Олег мужики. Ждем Лешу.

1:36: Сотня от британца по не особо точной второй задаче. Хм.

1:50: Хо нахохочил сотню по третьей. А вот британца, который получил сотню по второй, жалко. Он был одним из трех, кто получил полный балл по неточной задаче в первом туре. К сожалению, у него ноль по rings: видимо, не успел отдебагать. Жаль. :(

2:00: Два часа, полет нормальный. У Гены вторая сотня.

2:05: Макс и Егор набирают свои баллы по первой. 55 у Макса, 32 у Егора.

2:10: У Егора 55 по первой. Что-то Леша и Олег затихли.

2:15: Егор четвертый, Макс второй. В принципе, можно уже заканчивать контест прямо сейчас.

2:30: Программа-минимум для адекватных участников сегодня 55-43-100, видимо. А тем временем мы начинаем обратный отсчет.

-2:25: Как гласит известный анекдот, если у телефона на android осталось 95% заряда батареи, то его надо зарядить. Я это к тому, что мой телефон внезапно может разрядиться в ближайшее время. Но не переживайте, мысленно я с вами!

-2:20: Так просто вы от нас не избавитесь! Добрые организаторы дали нам розеток, так что мы можем вам надоедать еще некоторое время.

-2:15: Вести с полей: у Егора сотня по первой задаче. Это первая сотня по первой задаче, и теперь контест является хорошим: каждую задачу кто-нибудь решил, и никто не решил все задачи.

-2:13: У Олега 33 по второй задаче. Полезно для общего развития.

-2:10: Первая тройка: Гена, Егор, Макс. Идеально. Сейчас еще Леша с Олегом подтянутся, надеюсь.

-1:57 У Леши сотня по третьей. Ему осталось получить что-нибудь по второй для полного счастья.

-1:55: Хо, к сожалению, такой хо. Сотня по первой и первое место на данный момент.

Радио Codeforces: А сейчас для вас прозвучит композиция "Джонни Хо, Джонни Хо, Джонни Ха-Ха".

-1:50: Тем временем, Егор и Макс медленно опускаются вниз. Сейчас они на четвертом и пятом местах. Перед ними Хо, Гена и какой-то японец. Олег шестнадцатый, Леша двадцать первый.

-1:40: Наше хо-хо сильнее из хо-хо! Гена получил 77 баллов по первой. Судя по тому, что у него не прошла третья подгруппа, которая по смыслу вложена в четвертую, то у кого-то слишком хорошие тесты.

-1:35: Что логично, у Гены третья сотня за этот тур. Надеемся, что Хо его не догонит.

-1:20: 39 от Леши по второй задаче. Теперь можно с 99% уверенностью говорить, что у России четыре золота. Тем не менее, интрига сохраняется: что сделает мистер Хо и сдаст ли Макс вторую на 100?

-1:15: Хо.

-1:10: Для топа они тур перехалявили. Кроме того, сейчас первое место от 27-го(нижняя граница золота) отделяет почти 300 баллов.

-1:07: Третий полный балл. На этот раз у Егора.

-1:00: Час до конца контеста, полет нормальный. Леша сдал первую на 55.

-0:20: Конец контеста близок. Наши уже почти час ничего не делают. Тем не менее, у них все хорошо.

-0:15: Вот что мне не нравится в этом контесте, это то, что последние полтора часа никакой интриги нет. Заморозку бы для пущего интереса.

-0:10: Теперь у трех наших по 198 баллов, причем с одинаковой разбивкой по задачам. Мейнстрим!

-0:05: Как-то без огонька проходит конец второго тура XXIV IOI.

-0:00: По четыре золота у нас и у Китая, но у нас меньше сумма баллов за оба тура.

Объявление после тура во время показа результатов: "У вас есть бесконечное количество токенов. Используйте их с умом".

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

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

Обновили табличку: http://carp.di.unipi.it/

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

Появилась http://carp.di.unipi.it/

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

Появилась Your text to link here...

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

Как задачи ? Есть у Гены шансы, что у Американца макс бала не будет ?

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

    Задачки клевые. Сходу не очевидно, как их решать, так что они содержательные. Кроме этого, там есть некоторая неточка. Видимо, на ней все и будет решаться.

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

      Клево! Радует что спустя три года вновь что-то содержательное начали давать.

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

    Задачи хорошие. Мы пока не умеем решать две сабтаски во второй (35 + 39 — eps) и одну сабтаску в первой (45). Правда не сказать, что бы я сильно долго думал, не засыпая при этом. Подробнее будет в ближайшее время.

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

Запасной вариант.

Кстати, насколько правильно считаются медали?

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

Ахах, где-то я уже читал задачу про опоздавшего на турнир )))

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

    Не-не-не. Эта совсем тупая. Но легенда тоже порадовала.

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

      И правда легкая очень, там же лог можно оставить или надо линейное решение ?

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

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

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

По третьей задаче: l и r мы тоже можем выбирать сами или они случайны и тогда нам надо максимизировать мат. ожидание или минимальное количество раундов?

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

А можно задачи поподробнее? С ограничениями и более формально?

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

Хо тоже нахохочил 3ю на полный балл.
Остаётся надеяться, что только Гене покорится 45 по 1й.

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

    Наверное, имелось ввиду 43 по второй :) Но по ней у всех будет сильно больше, еще больше половины контеста осталось.

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

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

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

        Тогда 55, а не 45. Там нет ничего особо сложного, Гена эти баллы получит. Я думаю, что по первой сотня у него будет. А вот насчет второй не уверен.

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

          А я уверен)

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

          Очень красиво будет, если Гена наберет 55 по первой, а Хо — 43 по второй.

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

            Получить по первой 55 для Гены (1,2 — просто напиши BFS; 3 — просто посортай координаты и выдай ответ) — дело 10 минут. Думаю, он пишет 100.

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

      Думаю, имелось в виду именно то, что написано. Просто 55 по первой заходит у многих.

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

#alex_kpr_рекомендует?

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

Жалко. У Хо есть шансы обогнать Гену.

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

Суворов затащил первую.

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

Это первая сотня по первой задаче, и теперь контест является хорошим: каждую задачу кто-нибудь решил, и никто не решил все задачи.

Надеюсь, товарищ Хо не испортит контест

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

Задача А, похоже, вполне решаемая на 100 по такой идее:

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

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

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

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

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

random.johnnyh доминирует.

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

    Неужели можно так (что Гена будет ниже в рейтинге хотя бы на 17 минут) за два года прокачаться?

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

      Это один, отдельно взятый контест. Причем с очень строгими правилами применимости задач. В любом случае, В — задача на придумку, а А — "стандартная" задача, так что мало сомнений, что у Гены этот тур 300, но есть, что у Johnny 300.

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

        Утверждается, что B не очень интеллектуальна. Решение от Burunduk1: для каждого запроса храним, доживет ли этот элемент в кэше до того, как про него спросят следующий раз. N бит.

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

          Да, действительно.

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

          Ну, все же N+K (нам же про начальные элементы тоже это знать нужно). Этого все равно хватает на 100

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

У Гены по А:

1 — OK 2 — OK 3 — 0 4 — OK

это как?

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

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

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

      Канделябр вполне в моем вкусе. Интересно, применит ли Гена кулхак "если выполняется условие задачи 3 — решать халявой"? :)

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

        Судя по скорости, он просто нашел у себя багу.

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

          Причем, раз тесты группы 4 не поймали, простую. В духе числа в int помножил, упало на каком-то вытянутом случае.

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

            Ну это называется "какого лешего"? Почему этого частного случая нет в четвертой подгруппе?

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

Осталось Гене закрыть последние 32 и может идти мешать Джонни отдыхать

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

НЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕТ!

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

600 у Джонни. Да уж.

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

#Геннадий_не_одержал

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

Хо-то таки торт

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

=(

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

Кто-нибудь ещё видел это? В середине контеста по первой задаче первого дня (odometer) в табличке организаторов было три сотни, причём третья у кого-то из глубины таблицы (может быть, Marco Keller?). Теперь опять две. А вчера сотен было тоже две?..

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

    Три сотни сегодня видел.

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

    Говорят, что у них был "Analysis Mode", т.е. после тура во время просмотра своих результатов можно было посдавать решения. Сейчас они, естественно, это отрубили нафиг.

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

      То есть это дорешивание просочилось в табличку?

      В общем, если организаторы знают, в чём было дело — скорее всего, всё хорошо.

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

Вот так всегда. На соревнованиях по программированию решает все программирование автомата без памяти.

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

Ладно, Гене соболезнуем, но наша сборная-то сейчас просто молодцы! Li Chao немного сливает, и у нас на текущий момент по медальному единоличное первое место.

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

    27 золота. Пока у Китая тоже 4.

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

      Да, Li Chao очнулся, теперь, вроде, от 4 золотых никуда не денемся ни мы, ни они.

      Upd. Счет по сумме баллов 1751-1742 в нашу.

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

Егор красавчик) Три сотни это именно то, что было нужно)

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

Ура, молодцы наши, 4 золота)))

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

Я думаю, что Хо просто вовремя использовал эту карту. И мои искренние поздравления Егору, за которого я болел.300 это самое оно)