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

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

И снова здравствуйте! На связи с вами из города Монтикьяри, где проходит первый тур 24-й международной олимпиады по информатике успевшие всем надоесть AlTimin и PavelKunyavskiy.

Тур должен был начаться в 11:00 по московскому времени (в 09:00 по местному), но его начало отложили на полчаса. Приношу свои извинения за то, что трансляция от нас началась так поздно: организаторы обещали интернет, но на самом деле его не оказалось, и мне пришлось топать в центр города за симкой.

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

В первой задаче (с самым длинным условием) участникам предлагается написать программы для машинки, которая катается по клетчатому полю 256x256, умеет оставлять в клетках камни. Более формально: в каждой клетке в любой момент времени не может быть больше 15 камней, машинка умеет выполнять команды move, left, right, put, get (если при выполнении какой-то команды машинка пытается выполнить некорректное действие, то команда просто игнорируется). Кроме того, в тексте программы можно ставить метки вида L: и, соответственно, бывает безусловный переход на метку (jump L) и два условных перехода (pebble L и border L), которые совершают переход на метку L в случае, если в текущей клетке есть камень или машинка упирается в стенку. В этой задаче есть несколько подзадач, в которых требуется написать разные программы. В первой подзадаче надо остановится в той из клеток (0, 0) и (0, 1), в которой изначально было больше камней. Во второй все то же самое, но количество камней в этих клетках после выполнения программы должно остаться таким, как было. В третьей надо попасть в середину отрезка. В четвертой нужно было собрать все камни в клетке (0, 0). Балл за подзадачу зависит от количества действий машинки. В пятой нужно найти глобальный минимум на доске, причем менять конфигурацию камней запрещено. Балл за задачу зависит от длины программы.

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

Третья задача: есть строка, бывают операции двух видов: "добавить букву в конец строки" и "отменить последние K операций" (да, можно отменить отмену команды!). Кроме этого, в произвольный момент времени приходят запросы вида "узнать K-тую букву строки".

На данный момент осталось два часа до конца контеста. Табличка результатов лежит тут. На первом месте, как ни странно, tourist с 272 баллами из 300. Среди россиян лидирует Егор Суворов (yeputons), находящийся на шестом месте c 204 баллами. Максим Ахмедов (Zlobober) и Олег Иванов (tigvarts) c 148 и 140 баллами занимают 21 и 26 места. У Леши Гордеева (Copymaster) на данный момент всего 9 баллов, видимо он завяз в дебаге довольно неприятной с технической точки зрения второй задачи. Мы надеемся, что он сейчас разберется и получит свои законные баллы по всем задачам.

-1:30: Леша получил 37 баллов по второй задаче. Мы надеемся, что это значит, что он написал стресс-тест и вскоре получит по ней полный балл. Олег превратил 40 в 58 по первой задаче и написал решение на 20 баллов во второй, что подняло его на 19 место. Макс чуть-чуть прокачал первую и вторую задачу, оказавшись на 21 месте. Ждем ответа от Егора.

-1:20 Леша продолжает нас радовать, сдав третью задачу на 34 балла. Тем временем тут произошел небольшой подрыв устоев: какой-то американец китайского происхождения сдал третью задачу на полный балл и вышел на первое место (временно).

-1:00: Час до конца контеста. У Леши по третьей задаче появилось 60 баллов. Он большой молодец: у него получилось собраться в нужный момент, что очень тяжело.

-0:50: Битва титанов продолжается. У американца китайского происхождения 297 баллов, в то время как у Гены всего 287. Болеем за Гену! Леша продолжает нас радовать, набрав 100 баллов по третьей задаче. Немного странно то, что Егор очень давно (больше часа) ничего не посылал. Остается надеяться на то, что он кодит какую-нибудь вундерваффе (и то, что он успеет её докодить до конца тура).

-0:45: Сервер с табличкой периодически ругается страшными словами типа "Internal server error". Надеемся, что у участников никаких проблем с сервером нет.

-0:40: Ахтунг! С табличкой происходит что-то странное, видимо реджадж.

-0:35: Нет, это был не реджадж. Видимо просто глюк таблички.

-0:30: Больше хороших новостей для бога хороших новостей! Сто баллов у Макса по второй, 21 у Леши по первой.

-0:20: Макс и Леша сделали сорок по первой задаче. Тем временем у Johnny Ho 300 баллов, а у Гены день рождения, с чем мы его и поздравляем.

-0:15: У Леши 57 по первой задаче. Не хватает только сотни от Егора по второй для симметрии Вселенной и Высшего Блага и сотни от Гены по первой.

-0:05 Пять минут до конца контеста. Макс продолжает отжигать: 58 баллов по первой задаче, 258 в сумме и седьмое место, с чем мы его и поздравляем.

Контест окончен. В целом сборная написала тур хорошо, но впереди еще второй тур. Пожелаем участникам удачи и хорошего отдыха перед следующим туром.

Репортаж с места событий, для вас ведут PavelKunyavskiy и AlTimin. KOTEHOK должен был приехать, но, к сожалению, в последний момент не смог.

Проживание участников организованно в месте под названием Sirmione Grand Village в двух часах езды от Милана. Участников расселили в бунгало по 4 человека в комнату. Комнаты достаточно большие и удобные. Даже с кухней. Единственное, что немного удивляет --- это две кровати, одна из которых двухэтажная, другая двуспальная. Но вроде говорят, что двуспальная раздвигается. Руководителей и гостей (формально мы visitor'ы) поселили в такие же бунгало по два человека в другой части отеля. К каждой команде приставлен гид. Организаторы в этот раз смогли найти русскоговорящего гида, за что им большое спасибо.

Передовой опыт России в деле поселения участников на значительном удалении от места проведения туров успешно перенят заграницей: соревнования проводятся в Montichiari, где-то в 45 минутах езды от отеля. В результате много времени уходит на трансфер туда и обратно, и еще больше времени на ожидание опоздавших на этот трансфер.

Сегодня (24 сентября) прошло открытие и пробный тур. На входе в здание, где будет проведен тур, на большом экране транслируют красивую анимацию из слов "welcome" на разных языках. К сожалению, гугл-транслейт не оправдал ожиданий организаторов, и вариант на русском звучал как "приветствовать". На открытии не смогли найти мест на всех присутствующих, поэтому visitor'ам предложили или посмотреть видео-трансляцию в соседней комнате. Открытие было довольно скучным и проводилось в формате "длинные пафосные речи" и "игра на скрипке/пианино/...".

Организаторы олимпиады написали (прим. автора: снова) (прим. автора: PavelKunyavskiy говорит что не "снова", а "опять") новую тестирующую систему. Она опенсорсная, и Zlobober уже успел с ней поиграться. Так как практически ни одного цензурного комментария от него мы не получили, мы были готовы к худшему. На деле, все оказалось не так плохо. Из замеченных проблем было несколько неадекватных вердиктов системы (access forbidden for the file вместо memory limit), несколько мелочей, которые достаточно быстро правили на месте. Особенно поразило то, что не работала комбинация клавиш Alt+Tab. Как они этого добились мы не поняли, но они обещали исправить до завтра. Еще одну из задач пробного тура было нельзя сдать. Задача output-only, т.е надо послать ответы на данные тебе тесты. При этом размер правильного ответа превышал лимит размера файла. Со временем это тоже поправили, хотя долго отказывались это делать. Еще из веселых событий: yeputons'у по ошибке принесли распечатку чужого кода. После выяснения обстоятельств оказалось, что у него был идентификатор I04, а ему по ошибке принесли код участника l04 (буквы L и I различаются. Наверное).

Первый тур пройдет завтра и достаточно скоро мы уйдем переводить задачи. Мы постараемся в режиме реального времени транслировать происходящее завтра. По расписанию начало тура в 9:00 по местному времени (11:00 по Москве).

Задача 192A - Модные числа

Кратко о решении: перебор

Подробно о решении: Нетрудно заметить, что это числа положительны, следовательно каждое из слагаемых меньше N. То есть всего различных возможных слагаемых порядка . Это значит то, что мы взять и одно из слагаемых перебрать. Тогда нам нужно научиться проверять, является ли какое-то число треугольным. Заметим, что если мы заранее выпишем все слагаемые в порядке увеличения то мы сможем с помощью бинарного поиска в массиве искать наше число. Это даем там решение за . Если перебирать первое слагаемое в порядке увеличения, то можно использовать два указателя, что дает нам решение за .

Задача 192B - Прогулки под дождем

Кратко о решении: динамика.

Подробно о решении: динамика d[i] — количество дней, в течении которых плитка номер i доступна. Пересчет: d[i] = min(a[i], max(d[i - 1], d[i - 2]))

Асимптотика решения: O(N)

Задача 191A - Династические головоломки

Кратко о решении: динамика

Подробно о решении: динамика d[i][j], i — первый символ в имени династии, j — последний текущий символ. d[i][j] — максимальная текущая длина. Переход: для слова с первой буквой l, последней буквой r и длиной s для всех возможных первых букв i состояние d[i][r] может быть улучшено значением d[i][l] + s.

Ответом будет являться максимальное значение d[i][i] для всех i.

Асимптотика решения: O(N * alpha), где alpha — это размер алфавита.

Задача 191B - Митинг

Кратко о решении: конструктив

Подробно о решении: заметим, что на последнюю площадь никогда не выгодно подавать заявку (денег мэрии не потратим, ничего не изменится, мы просто потеряем ход). Переберем площадь, на которой мы хотим провести митинг. У нас есть k - 1 ход на то, чтобы потратить деньги мэрии (один ход нам нужен на подачу заявки на искомую площадь). Тратить деньги выгоднее всего на самых дорогих площадях, за исключением последней. Осталось научиться быстро выбирать k - 1 максимум из всего массива, за исключением данного элемента. Для этого сначала отсортируем массив и получим k максимумов (последнюю площадь мы не должны рассматривать). Проверяем, лежит ли наше текущее значение в k - 1 максимальных (бинпоиск и не только). Если лежит, то искомые k - 1 максимумов — это максимальные k элементов без нашего. Если не лежит, то это просто максимальные k элементов.

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

Асимптотика решения:

Задача 191C - Дураки и дороги

Кратко о решении: lca

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

Асимптотика решения:

Задача 191D - Схема метро

Кратко о решении: снова динамика

Подробно о решении: динамика d[v][rest][cycle] — количество линий, которое требуется для того, чтобы в поддереве вершины v все покрасить, в v остаются rest незамкнутым, cycle — правда ли, что нам надо обрабатывать цикл, в котором мы находимся.

Если мы находимся не в вершине цикла, то обрабатываем всех детей, говоря что мы хотим, чтобы в них было по одному незакрытому пути. Пусть у нас есть s сыновей, нам надо взять и замкнуть все лишние линии, а недостающие нагенерить. То есть ответ это , если s > rest, и в противном случае.

Если мы находимся в вершине цикла, то либо мы покрываем этот цикл кольцом и это стоит нам , где u — это вершина на цикле. отличная от v. Другой вариант — покрыть все участки кольца радиальными линиями. Утверждение: это всегда можно оптимально сделать ровно двумя радиальными. Пусть это не так. Тогда рассмотрим некоторую вершину, в которой радиальные линии <<подвешиваются>> к кольцу. От неё по кольцу в разные стороны уходят два тоннеля, принадлежащие этим линиям. Так как различных линий на кольце сейчас не менее трех, то мы можем перенаправить радиальные линии следующим образом: соединить куски вне кольца друг с другом, а кольцо замкнуть. На кольце останется не менее двух кусков, следовательно все линии останутся валидными, а их число не изменится.

Теперь надо выбрать две станции, из поддерева которых будут выходить радиальные ветки, покрывшее кольцо. Стоимость такой станции это d[u][2][0], а обычной — d[u][0][0] (d[v][rest][0] в случае той вершины, которую мы сейчас обрабатываем) . Соответственно, нам надо выбрать две станции с максимальным значением d[u][2][0] - d[u][0][0].

Асимптотика решения: O(N)

Задача 191E - Разгон митингов

Кратко о решении: бинарный поиск по ответу

Подробно о решении: Сделаем бинарный поиск по ответу. Нам надо посчитать количество отрезков, на которых сумма больше нашего некоторого значения. Как мы это будем делать: будем обрабатывать все отрезки в порядке увеличения правых концов. Отрезки с одинаковыми правыми концами будем обрабатывать пачками. Более подробно: мы будем поддерживать некоторую структуру данных в которой будут храниться суммы всех отрезков c фиксированным правым концом.

Для того, чтобы быстро пересчитывать, нам нужно всего добавить в множество некоторый элемент ( 0, если точнее) и добавить ко всем элементам множества некоторое значение (a[i], если быть точнее). Еще нам нужно уметь отвечать на запрос <<количество элементов, больших данного на отрезке>>. Все это умеет быстро реализовывать, например, декартово дерево. Но нам придется дополнительно хранить некоторую величину X, означающую <<надо прибавить к элементу из декартова дерева X, чтобы получить реальное значение>>. Тогда при добавлении элемента a в нашу структуру надо будет положить в декартово дерево величину a - X, а прибавление некоторой величины ко всему множеству реализуется простым изменением X.

То есть у нас есть структура данных, которая умеет все эти операции выполнять за . То есть одна итерация внешнего бинпоиска работает за , следовательно весь алгоритм работает за

Асимптотика решения: