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

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

Доброе время суток! С вами снова успевший уже всем надоесть 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
  • Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У Гены по А:

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

это как?

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

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

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

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

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

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

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

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

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

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

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

=(

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

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

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

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

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

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

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

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

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

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

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

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