Третий отборочный раунд и его разбор были подготовлены Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews и Gassa.

В третьем раунде турнира «Яндекс.Алгоритм» хотя бы одну попытку сделало 265 участников, хотя бы одну задачу из них решило 177. По задаче A было сделано 559 попыток, из них 137 успешных, по задаче B — 127 попыток (47 успешных), по задаче C — 111 попыток (64 успешных), по задаче D — 64 попытки (15 успешных), по задаче E — 45 попыток (20 успешных) и по задаче F — 606 попыток (129 успешных).

Задачи третьего раунда в среднем оказались проще, чем задачи первых двух раундов, и по ходу тура стало понятно, что победитель, по всей видимости, решит все задачи. Действительно, на 72-й минуте шесть задач сдал Petr, правда, все задачи были сданы «в открытую». За пять минут до конца турнира на второе место с шестью задачами выходит KADR, у которого также все задачи сданы «в открытую». Но практически сразу шестую задачу сдаёт nkurtov (Николай Куртов, Швейцария) и выходит на первое место, так как у него сданы «втёмную» три задачи. За две минуты до конца турнира на второе место выходит winger, у которого две задачи в начале турнира были сданы «втёмную», а остальные — «в открытую». И наконец на последней минуте задачу Е «втёмную» сдаёт s.quark (s-quark) из Китая и выходит на первое место: из шести решённых задач у него «в открытую» сдана только B. Итого до системных тестов все задачи решили пятеро участников. Лидирует s.quark, за ним — nkurtov, за ним — winger, Petr — на четвёртом месте, KADR — на пятом.

После системных тестов выясняется, что у s.quark не прошла задача F, которую он сдавал «втёмную» на 25-й минуте, у nkurtov не прошли сразу две задачи — С и D. У winger прошли обе сданные «втёмную» задачи, таким образом, он занял первое место в третьем раунде. Второе место занял Petr, который уже обеспечил себе выход в финал по итогам первого раунда. KADR остался на третьем месте, ainu77 (ainu7) из Южной Кореи переместился на четвёртое, а s.quark даже после того, как у него не прошла задача, оказался на пятом месте и попал в число четырёх финалистов по итогам раунда.

Задача A (Конфетное настроение)

Подсчитаем количество невкусных конфет. Пусть их будет M. Тогда если M = 0, то ответ равен . Иначе рассмотрим, какой ожидаемый вклад в изменение настроения даст i-я конфета, если она вкусная. Она может находиться равновероятно в M + 1 позиции относительно невкусных конфет, и только в одной из них вкусная конфета будет съедена. Значит, ожидаемый вклад в изменение настроения от одной вкусной конфеты A_i равен . Для невкусных конфет ожидаемый вклад в изменение настроения равен , так как первой невкусной конфетой может оказаться равновероятно любая из невкусных. В итоге математическое ожидание изменения настроения равно .

Задача B (Шарики)

Для определенности будем считать, что N ≤ M.

Рассмотрим случай, когда N = 1. Пусть на фото находится k шариков. Заметим, что можно оставить любые k шариков. Однако не любое их относительное расположение может быть получено, потому как невозможно поменять их относительный порядок. Но при этом на любых k позициях можно разместить оставшиеся шарики. Следовательно, всего различных фото можно получить .

Пусть N ≥ 2. Тогда если на фото k = N·M шариков, то такое фото можно получить только одно, так как мы не делали ни одного хода (первый ход обязательно убирает один шарик с поля). Если k = N·M - 1, то после первого хода можно ходить только в свободную клетку на поле — это эквивалентно известной головоломке «Пятнашки»; в этом случае ровно половина перестановок будет достижима (см. ссылку выше). Если k < N·M - 1, то рассмотрим две любые пустые клетки, первым делом получим конфигурацию, в которой пустые клетки стоят рядом. Тогда относительно одной из них головоломка «Пятнашки» разрешима (требуется четность суммы количества инверсий в перестановке с номером строки и столбца, а у выбранных пустых клеток сумма номеров строки и столбца отличается на 1). Далее, выбрав в качестве пустой клетки подходящую, остается только собрать головоломку.

Таким образом, общее количество фотографий .

Задача C (Размещение болельщиков)

Наиболее простой способ решения этой задачи заключался в генерации всех возможных относительных перестановок болельщиков. Зафиксируем некоторый порядок болельщиков, к примеру, снизу вверх, и пусть i-й по счёту болельщик имеет исходный номер p_i. Понятно, что если каждому болельщику не мешает тот, кто сидит непосредственно перед ним, то все болельщики видят поле. Рассмотрим все пары подряд идущих болельщиков. Если h_pi ≤ h_pi + 1, то никаких ограничений на рассадку эта пара болельщиков не накладывает: где бы ни сидел болельщик с номером p_i + 1, ему никогда не будет мешать сидящий перед ним болельщик номер p_i, поскольку он меньше ростом. Если же h_pi > h_pi + 1, то появляется следующее ограничение: болельщик с номером p_i + 1 не может занимать следующие h_pi - h_pi + 1 мест после болельщика с номером p_i, иначе ему не будет видно поля. Соответственно, эти h_pi - h_pi + 1 рядов нужно убрать из рассмотрения для данного зафиксированного порядка болельщиков. Проделав эту операцию для всех пар болельщиков, сидящих друг за другом, нужно прибавить к ответу количество сочетаний из оставшегося количества мест по K, где K — это общее количество болельщиков. Для того чтобы быстро выполнять эту операцию, нужно заранее рассчитать таблицу значений C_n^k для n и k, не превосходящих 1000.

Сложность решения: O(n² + k!·k).

Также при желании задачу можно было решать и более сложным способом, а именно методом динамического программирования, где состоянием являлась тройка «сколько рядов рассмотрели, маска уже посаженных болельщиков, номер последнего болельщика». Переход в данном случае заключался в переборе «предпоследнего посаженного болельщика». Для быстрой работы этого решения параллельно с подсчётом таблицы ДП нужно было сохранять таблицу кумулятивным сумм, чтобы избавиться от вложенного цикла по рядам.

Задача D (Интересный язык)

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

Для того чтобы посчитать для каждого суффикса такое количество пар, воспользуемся бором (для справки см. алгоритм Ахо-Корасик на сайте e-maxx, раздел «Бор. Построение бора»). Построим по входному набору слов два бора: один будет содержать все слова, как они заданы во входных данных, а другой будет содержать перевёрнутые слова. Обойдём бор, содержащий перевёрнутые слова. Каждый раз, когда мы будем заходить в терминальную вершину, поднимемся из этой вершины вверх до корня, параллельно спускаясь по таким же символам в боре, содержащем исходные слова. Если в процессе этого подъёма/спуска мы попадаем в терминальную вершину в боре с исходными словами, то мы должны увеличить на один счётчик для суффикса, в котором сейчас находимся в боре с перевёрнутыми словами. Если в процессе подъёма мы вышли из бора с исходными словами, подъём можно прекратить.

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

Сложность решения: O(sumL), где sumL — суммарная длина всех слов.

Задача E (Дорожный вопрос)

Давайте посмотрим, что нам даёт уплата налога в некотором городе. После того как мы заплатили налог в городе A, некоторые города мы теперь можем посетить бесплатно. В число этих городов входят те, которые, во-первых, достижимы из города A, во-вторых, из которых достижим город A. Если перейти от городов к теории графов, то можно сказать, что мы теперь можем бесплатно посещать все вершины, которые входят в ту же сильно связную компоненту, что и город A. Таким образом, если разбить исходный граф на сильно связные компоненты, то налог можно платить только на въезде в каждую компоненту. Поскольку въезд в компоненту сильной связности «открывает» для бесплатного путешествия всю эту компоненту, а все налоги неотрицательные, то никогда не будет выгодно добровольно платить налог в каком-то другом городе этой же сильно связной компоненты.

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

После того как новый граф построен, нужно найти в нём кратчайший путь между теми вершинами, которые соответствуют сильно связным компонентам, содержащим вершины 1 и n исходного графа. Это можно сделать либо алгоритмом Дейкстры, либо методом динамического программирования, учитывая то, что полученный в результате сжатия сильно связных компонент граф не имет циклов. Также отдельно нужно рассмотреть начало путешествия, поскольку налог можно по условию задачи платить только в момент въезда в какой-то город.

Задача F (Место под столицу)

Если угол между радиусами больше двух радиан, то минимальное расстояние — сумма радиусов. Иначе, разность радиусов плюс длина дуги окружности, проходящей через точку с меньшим радиусом. Это следует из того факта, что в «криволинейной трапеции», составленной из двух радиальных рёбер и двух дуг, кратчайшим расстоянием между противоположными вершинами является путь по радиальному ребру и дуге меньшего радиуса.

Остаётся просто аккуратно провести все вычисления; использование функции atan2() позволяет обойти большинство «подводных камней». Без использования atan2() проблемы с точностью возникают в случае двух близких точек с большими радиусами; в этом случае помогает вместо арккосинуса во избежание потерь точности использовать арксинус.

Второй отборочный раунд и его разбор были подготовлены rng_58, snuke, snarknews и Gassa.

Во втором раунде турнира «Яндекс.Алгоритм» хотя бы одну попытку сделало 495 участников, хотя бы одну задачу из них решило 425. По задаче A было сделано 503 попытки, из них 73 успешных, по задаче B — 11 попыток (2 успешных), по задаче C — 472 попытки (76 успешных), по задаче D — 846 попыток (386 успешных), по задаче E — 42 попытки (16 успешных) и по задаче F — 624 попытки (182 успешных).

Результаты тестового прорешивания позволяли надеяться на то, что количество участников, сдавших 5 задач, будет выше, чем в первом раунде, и что победители сдадут по 6 задач. Однако оценка оказалась завышенной. Ближе к середине раунда определились двое лидеров — tourist и eatmore, сдававшие все задачи «втёмную». Далее шла целая группа преследователей, у каждого из которых было сдано не более двух задач «втёмную». Первым сдал 5 задач cgy4ever из Китая, у которого задача C была сдана «втёмную»; на 75-й минуте по 5 задач сдали maciej.klimek (maciejk) из Польши, Jedi_Knight (ivan.popelyshev) и burunduk3. На 77-й минуте пятую задачу сдаёт tourist и выходит на первое место с пятью задачами «втёмную». На 80-й минуте свою пятую задачу, причём также «втёмную» сдаёт eatmore; это оказывается задача B, которую до этого не сдал ни один участник. Тем не менее, tourist удерживает лидерство. За минуту до завершения контеста задачу E, ставшую для неё пятой, сдаёт natalia и с четырьмя задачами «втёмную» из пяти выходит на третье место.

После системных тестов выясняется, что в первой тройке сумел удержаться только tourist, у которого прошли все 5 «тёмных» попыток. Впрочем, он уже обеспечил себе участие в финале по итогам первого отборочного раунда, так что «проходным» становилось пятое место. У eatmore не прошла задача E, которую он сдавал предпоследней; у natalia — задача F, которую она также сдавала предпоследней. Зато последние отправленные задачи — решённая только двумя участниками (кроме eatmore, это s-quark из Китая) B для eatmore и отправленная на 1:39 E для natalia — системное тестирование прошли.

В результате второе место занял vepifanov, третье — yeputons, сдавшие «втёмную» только задачу D на 5-й минуте. Все последующие участники сдавали все задачи «в открытую». Четвёртое место занял Jedi_Knight (ivan.popelyshev), пятое, последнее из «проходных»,— peter50216 из Тайваня.

Задача A (Степени вершин)

Заметим, что если сумма всех d_i не равна 2(N - 1), то d не может быть последовательностью степеней вершин дерева, поэтому нужно вывести «None». В противном случае, несложно доказать, что всегда существует дерево, для которого d является последовательностью степеней вершин.

Пусть c — количество таких i, что d[i] ≥ 2. Есть несколько случаев:

1. c = 0. В этом случае d = {1, 1}. Очевидно, ответ — «Unique».
2. c = 1. Дерево должно быть «звездой». Ответ снова «Unique».
3. c = 2. Есть две вершины степени  ≥ 2. Обозначим их s и t. Должно быть ребро, соединяющее s и t, а все остальные ребра соединяют одну из вершин {s, t} с листом. Таким образом, ответ снова «Unique».
4. c = 3. Есть три вершины степени  ≥ 2. Обозначим их s, t и u. Рассмотрим три пары вершин {s, t}, {t, u} и {u, s}. Ровно две из них должны быть соединены ребром (если все три соединены ребром, то в графе образуется цикл; если одна или менее пар соединены ребром, то граф становится несвязным), поэтому есть три способа их соединить. Если степени вершин s, t, u все совпадают, все три получающихся дерева изоморфны, поэтому ответ — «Unique». Иначе ответ — «Multiple».
5. c ≥ 4. Если последовательность степеней, отсортированная по возрастанию, имеет вид {1, 1, 2, ..., 2}, то дерево должно быть цепочкой, поэтому ответ — «Unique». Иначе есть хотя бы одна вершина степени  ≥ 3. Можно построить два неизоморфных дерева, используя эту вершину: один способ — это составить цепочку вершин степени >=2 и прикрепить к ним листья, а другой — соединить три цепочки в одной общей вершине. В этом случае ответ — «Multiple».

Задача B (Лягушки)

Пусть f(t) — позиция лягушки k в момент времени t. Нас просят найти минимальное такое t, что t - f(t) ≥ d. Заметим, что t - f(t) — неубывающая функция, так как для любого t значение f(t + 1) - f(t) — это 0 или 1. Так как t - f(t) монотонно, мы можем использовать бинарный поиск. Основная часть решения состоит в подсчете f(t).

Предположим для простоты, что k = 2 (в противном случае мы можем повторить аналогичный алгоритм k - 1 раз). Назовем число n хорошим, если сумма высот между кочками 1 и n делится на m. «Хорошесть» имеет период m(p - 1), то есть n — хорошее тогда и только тогда, когда — хорошее. Рассчитаем и запомним в таблице для каждого n ≤ m(p - 1), является ли оно хорошим. Получается, что f(t) — это (количество хороших чисел между 1 and t), поэтому мы можем быстро вычислить его, используя таблицу.

Задача C (Зеленый треугольник)

Мы хотим посчитать сумму ориентированных площадей треугольников pqr для всех троек (p, q, r), перечисленных по часовой стрелке. Если зафиксировать точки p и q, ориентированная площадь треугольника pqr будет линейной функцией координат точки r, поэтому нам достаточно знать сумму всех абсцисс и сумму всех ординат всех точек в одной полуплоскости относительно прямой pq.

Зафиксируем точку p. Отсортируем все остальные точки по часовой стрелке относительно точки p и обозначим их в этом порядке p₀, ..., p_n - 2. Тогда мы можем использовать алгоритм двух указателей: будем поддерживать два индекса i и j. Здесь j — это наибольший индекс, удовлетворяющий условию «три точки p, p_i, p_j перечислены по часовой стрелке». Мы растим i от 0 до n - 2 и поддерживаем j. Когда мы увеличиваем i, j никогда не уменьшается, поэтому суммарное количество изменений i и j ограничено O(n). Суммарно алгоритм работает за время .

При указанных в задаче ограничениях на координаты возникают проблемы с точностью во время вычисления площади: точности double в случае треугольников малой площади, но большого периметра не хватает. Особенно эта проблема актуальна для Java, где тип long double отсутствует, а при использовании встроенного типа BigInteger решение не укладывается в Time Limit.

В качестве варианта рекомендуется при вычислении хранить сумму площадей для фиксированного основания треугольника как в double, так и в 64-битном целом: тогда по double определяются старшие 52 бита результата, а в 64-битном целом хранятся младшие 64 бита.

Задача D (MathWorlds)

Это самая простая задача. Нужно перебрать все операторы и посчитать количество операторов, удовлетворяющих условию «x <оператор> y = z». Особо надо рассмотреть случай y = 0, например, вообще исключив при y = 0 проверку оператора деления. Вариант «привести деление к умножению» не работает, например, для теста 0 0 1, который создал проблемы многим участникам.

Задача E (Маленькие циклы)

Свойства в условии задачи эквивалентны следующему:

1. У G есть остовное дерево. Зафиксируем какое-нибудь остовное дерево T и назовем ребра T «ребрами дерева», а остальные — «внешними ребрами».
2. Если e = {u, v} — внешнее ребро, то расстояние между u и v в T равно двум.
3. Для каждого внешнего ребра e = {u, v} покрасим путь между u и v в T. Тогда никакое ребро не покрашено дважды..

Исходная задача сводится к следующей: дано дерево, и некоторые ребра в нем покрашены. На каждом шаге можно выбрать путь длины 2 и покрасить его (при этом нельзя красить ребро, если оно уже покрашено). Какое максимальное количество шагов можно сделать?

Эта задача может быть решена жадно. «Подвесим» дерево за какую-нибудь вершину и найдем самое глубокое неокрашенное ребро e. Если у ребра e нет соседних неокрашенных ребер, то его покрасить невозможно — проигнорируем его. Если у ребра e есть соседнее неокрашенное ребро (обозначим его e₂) из той же вершины-родителя, то нужно покрасить e и e₂ одновременно, иначе мы не сможем покрасить оба ребра. Если у ребра e есть только соседнее ребро, ведущее в вершину-родителя e в свою очередь из ее вершины-родителя, то нужно покрасить e и родительское ребро одновременно. После того, как мы либо покрасили e, либо проигнорировали e, снова находим самое глубокое неокрашенное ребро и повторяем процесс.

Задача F (Шарообмен)

Если ответ для (p, q, r, s) — «Yes», то ответ для (p + 2, q, r, s) — тоже «Yes». Это верно, потому что если выполнить одну и ту же операцию два раза подряд, то ничего не изменится. Интуитивно понятно, что если p достаточно большое, то ответы для (p, q, r, s) и (p + 2, q, r, s) совпадают. На самом деле можно доказать, что если p ≥ 48, то это верно. Используя эти наблюдения, можно предполагать, что p, q и r малы, поэтому можно использовать динамическое программирование для решения задачи (dp[p][q][r][s]: можно ли переделать s в «RGB», используя операции p, q, r раз соответственно?).

Вот формальное доказательство. Построим граф из 48 вершин. Каждая вершина соответствует набору значений: (четность p, четность q, четность r, s). Последовательность операций соответствует пути в этом графе. Если этот путь достаточно длинный, то в нем есть циклы. Если цикл содержит p', q' и r' раз соответсвтующие операции, то эти числа четны, и мы можем удалить цикл и показать, что ответ для (p - p', q - q', r - r', s) — «Yes». Мы можем повторять этот процесс, пока p, q и r не станут не более 48.

Оказывается, можно заменить число 48 на число 3, если поэкспериментировать на компьютере.

В первом отборочном раунде 609 участников послали хотя бы одно решение и 396 послали хотя бы одно правильное решение. Задачи Неквадраты и Раздел королевства были довольно простыми, по обеим было примерно 300 правильных решений. Задача Столбики монет была относительно простой, ее решило 145 участников. Три оставшиеся задачи оказались сложнее. Задача Стикеры могла бы быть очень сложной задачей на строки, но маленький размер входных данных позволял решать задачу с помощью динамического программирования — задачу сдали 22 участника. Задачу Ассистенты решило 13 участников; в ней требовалось использование бинарного поиска, жадности и некоторых известных структур данных. Никто не смог решить за время соревнования задачу Государственные дороги, которая была изящной задачей на теорию графов с решением, которое было легко запрограммировать, но сложно придумать.

Поздравляем Kenny_HORROR, единственного участника, решившего 5 задач. Также поздравляем Petr, tourist и eatmore, которые решили 4 задачи с отрицательным штрафным временем и прошли в финал.

Задачи этого раунда подготовлены польской командой: Tomasz Idziaszek ( Раздел королевства ), Jakub Łącki ( Государственные дороги ), Marcin Pilipczuk ( Ассистенты ), и Jakub Radoszewski ( Неквадраты, Столбики монет ). Отдельное спасибо профессору Costas Iliopoulos за идею задачи Стикеры.

Решения, тесты и разбор были подготовлены marek.cygan, monsoon и jakubr.

Задача A (Ассистенты)

В этой задаче нам нужно найти минимальное количество дней, за которые можно завершить n исследовательских задач. Профессор может выполнить i-ю задачу за p_i последовательных дней, либо передать ее ассистенту, который выполнит ее за a_i последовательных дней. Каждый ассистент может выполнить только одну задачу, и профессору требуется один день на поиск ассистента.

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

Легко видеть, что существует оптимальное расписание, в котором профессор сначала ищет ассистентов, а потом выполняет задачи, которые никому не передал. Кроме того, это означает, что нам не нужно беспокоиться о том, чтобы профессор выполнял свои задачи в последовательные дни. Формально говоря, если есть некоторое оптимальное расписание, в котором профессор передает подмножество задач ассистентом и выполняет остальные задачи сам (но необязательно в последовательные дни), то существует оптимальное расписание, в котором профессор передает задачи из подмножества T в течение первых #T дней, а потом выполняет все оставшиеся задачи сам, каждую задачу — в непрерывную последовательность дней. Таким образом, если профессор передаст задачи из T, он закончит оставшиеся задачи в срок тогда и только тогда, когда .

Теперь приведем алгоритм, который будет проверять, существует ли такое T. Рассмотрим дни d = k, k - 1, ..., 1 в обратном хронологическом порядке, и в некоторые из этих дней мы будем передавать задачи ассистентам. Предположим, что на день d мы уже передали подмножество задач за дни после d. Пусть — множество задач, которые могут быть переданы в день d таким образом, что ассистент успеет выполнить их в срок. Главное наблюдение состоит в следующем: если непусто, то мы можем в день d жадным образом передать задачу , которая максимизирует значение p_i.

Теперь докажем, что алгоритм работает правильно. Предположим, что существует расписание S, которое в течение дней после d совпадает с нашим. Если в расписании S задача i передается ассистенту в день d, то все хорошо. Иначе в расписании S в день d профессор либо передает задачу j ≠ i ассистенту, либо выполняет задачу j сам (в последнем случае, возможно, j = i).

В первом случае профессор передает асистенту задачу j ≠ i. Тогда (так как ассистент выполнит задачу в срок) и (мы предполагаем, что расписание S совпадает с нашим планом после дня d). Благодаря нашему жадному выбору имеем p_i ≥ p_j. Если в S профессор передает ассистенту задачу i в день d', то d' ≤ d (так как и S совпадает с нашим планом в последующие дни), и мы можем в S переставить дни, в которые мы передаем ассистентам задачи i и j. Иначе, если в S профессор выполняет задачу i самостоятельно, мы можем изменить S следующим образом: мы передаем ассистенту задачу i в день d и выполняем задачу j в те дни, в которые профессор ранее выполнял задачу i (мы можем так сделать, потому что p_i ≥ p_j).

Во втором случае профессор выполняет задачу j в день d. Если j = i, профессор может вместо этого передать ассистенту эту задачу в день d (так как ). Иначе, если j ≠ i, профессор может передать задачу i в день d и вернуть пропущенный день, выполнив задачу j в момент, в который профессор работал над задачей i (передавая или выполняя ее) в расписании S.

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

Как быстро мы можем реализовать данный алгоритм? Выбор максимума в множестве может быть реализован с помощью бинарной кучи, отсортированной по p_i. Переходя от дня d + 1 к дню d, мы добавляем элементы из в кучу (то есть задачи с a_i = k - d; для этого нужно отсортировать задачи по a_i) и удаляем максимальный элемент (и добавляем его в T).

Заметим, что нам не нужно проходить по всем дням, мы можем начать с дня d = min(k, n), так как нет нужды передавать задачи ассистентам после n-го дня. Таким образом, все решение (с фиксированным k) работает за время .

Мы можем улучшить его, если будем перебирать не дни, а задачи, отсортированные по невозрастанию p_i. Каждый раз мы будем пытаться передать задачу i в самый последний день из {1, 2, ..., d_i}, где d_i = min(k - a_i, n)}, в который еще ни одна задача не передается. Несложно видеть, что полученное множество T будет таким же, как в предыдущем алгоритме. Эта операция выбора последнего свободного дня может быть выполнена за почти линейное время, используя структуру леса непересекающихся множеств. Каждое множество содержит свободный день d и все дни после него, в которые какие-то задачи передаются. Теперь выбор последнего свободного дня сводится к нахождению множества, которое содержит d_i, получения минимального элемента d' в этом множестве, передаче задачи i ассистенту в день d' и объединению данного множества с множеством, содержащим элемент d' - 1.

Давайте теперь оценим окончательную временную сложность. Так как одним из решений является передача всех задач ассистентам, ответ всегда будет меньше, чем n + A, где A = max_iai. Добавляя бинарный поиск, мы получаем решение, работающее за время .

Задача B (Раздел королевства)

В этой задаче нам нужно разделить сетку n × m на максимальное количество частей различных размеров, являющиеся связными компонентами, состоящими из единичных квадратов. Мы должны представить пример такого разделения, используя буквы из множества для обозначения получающихся частей. Решение этой задачи получается в три шага.

На первом шаге мы забудем на время про требование связности и определим, какие размеры частей приведут к максимальному результату. Ответ прост: части должны иметь размеры 1, 2, 3, ... Если последняя часть меньше требуемого, мы объединяем ее с предпоследней частью.

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

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

Одно из возможных правильных решений состоит в том, чтобы пометить каждую часть наименьшей буквой из тех, что еще не встречаются среди пометок ее соседей (и помечать части змейки по порядку). Другая идея состоит в том, чтобы помечать части в первом ряду буквами A и B, во втором ряду использовать C и D, в третьем — E и F, в четвертом снова A и B и так далее (см. картинку справа). Начиная с момента, когда каждая часть покрывает хотя бы один ряд целиком, мы можем начать использовать только две буквы, A и B. Во втором способе мы используем только 6 различных букв.

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

Вышеприведенный алгоритм может быть легко реализован с временной сложностью O(nm).

Задача C (Неквадраты)

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

Общий подход к задаче — динамическое программирование по множеству делителей n. Все делители n можно найти за время . Пусть D(n) — число делителей n. Оказывается, для n ≤ 10⁹ верно D(n) ≤ 1344.

Мы вычислим двумерную булеву матрицу , где — истина если и только если делитель d может быть представлен в виде произведения j неквадратов. При вычислении используется следующая булева формула, которяа работает при j ≥ 1 и :

Временная сложность этого решения составляет (логарифм появляется из-за использования структуры map или аналогичной для хранения делителей n. Сложность по памяти составляет O(D(n)k).

Можно улучшить время работы этого решения, если заметить, что параметр k ограничен сверху числом , что в нашем случае не более 29. Действительно, для ответ всегда «NO» (доказательство следует из следующего решения).

Есть также гораздо более простое решение, которое рассматривает разложение n на простые множители. Пусть n = p₁^α₁p₂^α₂... p_m^α_m, где p_i — различные простые числа. Тогда решение состоит в следующем:

1. Если α₁ + α₂ + ... + α_m < k, вывести «NO».
2. Иначе, если m > 1, вывести «YES».
3. В оставшемся случае m = 1. Если k - α₁ четно, вывести «YES», иначе вывести «NO».

Обоснуем это решение. Ответ в случае (1) следует из того факта, что у любого делителя-неквадрата есть простой делитель. Для m = 1 нам нужно просто проверить, может ли α₁ быть представлено как сумма k нечетных целых чисел, что возможно тогда и только тогда, когда четность k и α₁ совпадает. Это дает пункт (3) алгоритма.

Наконец, рассмотрим пункт (2). Нам нужно показать, что, если α₁ + α₂ + ... + α_m ≥ k и m > 1, то существует неквадратное представление n. Давайте возьмем в качестве первых k - 1 неквадратов простые делители n: сначала α₁ раз делитель p₁, затем α₂ раз делитель p₂ и так далее. В качестве последнего делителя, d, мы возьмем произведение оставшихся простых делителей. Если d не является квадратом целого числа, мы построили требуемое представление. Иначе мы заменим последний делитель на d / p_m, а первый делитель — на p₁ p_m, таким образом получая требуемое представление.

Это решение требует только найти разложение n на простые множители и работает за время .

Задача D (Столбики монет)

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

Пусть k — ответ, то есть максимальное количество одноцветных кучек, которого можно достичь. Выполним бинарный поиск по k. С этого момента нам остается научиться отвечать на следующий вопрос: для данного k проверить, можно ли получить k одноцветных кучек. Очевидно, оптимально попытаться сделать k самых маленьких кучек одноцветными.

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

Для начала рассмотрим каждый уровень по отдельности. Предположим, что нам этом уровне есть g_i золотых и s_i серебряных монет, а k минимальных кучек содержат в сумме t_i монет на этом уровне. Используя эти числа, мы можем рассчитать отрезок [a_i, b_i] такой, что тогда и только тогда, когда возможно добиться того, чтобы на i-м уровне выбранных кучек оказалось в сумме x золотых и t_i - x серебряных монет. Отметим, что отсюда будет следовать, что аналогичный отрезок для возможного количества серебряных монет на i-м уровне — это [t_i - b_i, t_i - a_i].

Теперь нам нужно убедиться, что отрезки для разных уровней позволяют нам найти корректное решение. Мы пройдем от самого нижнего к самому верхнему уровню. На уровня i нам нужно пересечь отрезок [a_i, b_i] с [a_i - 1, b_i - 1] и аналогично отрезки для количества серебряных монет. Таким образом мы получим один обновленный отрезок [a_i, b_i], который мы далее будем использовать для обновления отрезков на более высоких уровнях.

Это решение работает за время .

У этой задачи также есть решение за линейное время. Пусть g_i — общее количество золотых монет, которые находятся на i-м уровне. Пусть g'_i — максимальное количество кучек, которые можно сформировать таким образом, чтобы у них у всех были только золотые монеты на i-м уровне и ниже. Можно легко вычислить g'_i при помощи следующего рекуррентного соотношения:

Аналогично мы определяем s_i и s'_i для серебряных монет.

Пусть h_i — высота i-й кучки, и предположим, что кучки отсортированы по невозрастанию высоты, то есть h₁ ≥ h₂ ≥ ... ≥ h_n. Мы пройдем по кучкам и «раскрасим» их (делая их одноцветным), когда это возможно. Пусть мы рассматриваем i-ю кучку, и мы уже раскрасили кучки с номерами 1, 2, ..., i - 1 таким образом, что всего есть G золотых кучек и S серебряных.

Мы можем сделать i-ю кучку золотой, если и только если g'_hi > G. В таком случае мы покажем, что существует оптимальное решение, в котором эта кучка сделана золотой, а кучки 1, 2, ..., i - 1 раскрашены так же, как в нашем решении. Рассмотрим произвольное оптимальное решение, в котором кучки 1, 2, ..., i - 1 раскрашены так же, как в нашем решении. Пусть j ≥ i — самая высокая золотая кучка в этом оптимальном решении (она должна существовать, иначе мы можем добавить i-ю кучку и получить решение лучше). Можно поменять местами монетки из j-й кучки и i-й кучки и, так как g'_hj + 1 ≥ g'_hi > G, у нас есть достаточно много золотых монет, чтобы поместить их в i-ю кучку выше уровня h_j.

Аналогично, если мы не можем сделать i-ю кучку золотой, но можем сделать ее серебряной (то есть s'_hi > S), существует оптимальное решение, в котором мы так и делаем.

Иначе g'_hi + s'_hi ≤ G + S, что означает, что мы не можем «раскрасить» более чем G + S кучек высоты не менее h_i.

Так как мы можем отсортировать кучки по высоте с помощью сортировки подсчетом, описанный алгоритм работает за время O(n + m).

Задача E (Государственные дороги)

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

Мы представим рандомизированное решение этой задачи, которое легко запрограммировать, но довольно сложно придумать. Для каждого ребра, добавляемого в граф, мы выберем случайный целый вес. Для каждой вершины мы храним в ячейке массива результат операции , примененной к весам всех ребер, инцидентных этой вершине. Заметим, что такие значения можно обновлять за время O(1) при добавлении и удалении ребер.

Главное наблюдение состоит в том, что множество вершин {u₁, u₂, ..., u_k} представляет собой набор связных компонент тогда и только тогда, когда каждое ребро графа инцидентно либо двум, либо ни одной из вершин u_i. Таким образом, чтобы ответить на запрос, мы вычисляем:

где обозначает операцию . Если полученное значение не равно нулю, мы знаем, что ответ — «NO». Иначе с высокой вероятностью ответ — «YES». Вероятность неправильного положительного ответа — , где M — максимальный вес ребра. Эта вероятность оказывается достаточно мала при M = 2³² или M = 2⁶⁴.

Все решение работает за линейное время от размера входных данных.

Задача F (Стикеры)

В этой задаче нам дано n видов сткеров s₁, ..., s_n, где каждое s_i является словом длины d. Нас просят найти минимальное количество стикеров, которые нужны, чтобы составить данное слово t длины m.

Мы предложим простое решение, основанное на динамическом программировании. Обозначим как dp[i] минимальное количество стикеров, необходимое для того, чтобы составить ровно суффикс t[i..m], а как такое же число, но при этом разрешим стикерам выходить за границу и накрывать позиции из t[i - d..i - 1] (но не обязательно при этом правильными буквами). Ответ к задаче — это dp[1].

Как посчитать dp[i]? Ясно, что i-я позиция t должна быть в какой-то момент покрыта стикером, который начинается в этой позиции. Так как все стикеры имеют одинаковую длину, мы можем ограничить себя тем, чтобы положить этот стикер самым первым или самым последним. Это дает нам два случая:

1. Для некоторого j имеем s_j = t[i..i + d - 1]. Тогда мы можем составить суффикс t[i + d..m], возможно накрывая некоторые буквы из t[i..i + d - 1], и затем положить стикер s_j, начиная с позиции i. В этом случае мы используем стикеров.
2. Имеем s_j[1..d'] = t[i..i + d' - 1] для некоторого j и некоторого d' ≤ d. Тогда мы можем положить s_j, начиная с позиции i, затем составить t[i + d'..m] с ограничением, что нам нельзя изменять буквы перед позицией i + d'. В этом случае мы используем 1 + dp[i + d'] стикеров.

Если для каждого i мы знаем максимальное l[i], такое что t[i..i + l[i] - 1] является префиксом некоторого стикера, то случай (1) возможен, когда d = l[i], и результат случая (2) равен min_{1 ≤ j ≤ l[i]}(1 + dp[i + j]).

Мы вычисляем аналогично, но теперь вместо множества всех стикеров мы рассмотрим множество всех суффиксов стикеров. Таким образом мы вычисляем l[i] как максимальное число, такое что t[i..i + l[i] - 1] является подстрокой некоторого стикера.

Это решение может быть реализовано с временной сложностью O(mnd²). Интересно, что эта задача может быть решена за линейное время от размера входа, даже с использованием стикеров разной длины, но это решение гораздо сложнее.

Привет!

Совсем скоро начнется отборочный этап. Он состоит из трех раундов, которые пройдут:

Отборочный раунд 1 — 14 июля 2013, 21:00 MSK; Материалы раунда; Разбор

Отборочный раунд 2 — 18 июля 2013, 13:00 MSK; Материалы раунда

Отборочный раунд 3 — 22 июля 2013, 05:00 MSK; Материалы раунда

Каждый раунд продлится 100 минут. Ссылки для входа в раунды доступны по нажатию на название раунда.

Каждый раунд оценивается по системе гран-при 30. Чтобы пройти в финальный раунд не обязательно участвовать во всех отборочных раундах, вам нужно попасть в одну из этих категорий:

• топ-4 лучших в одном из раундов;

• топ-9 лучших (из тех, кто еще не прошел в финал) по суммарному рейтингу 2 из 3 раундов;

• топ-4 лучших (из тех, кто еще не прошел в финал) по суммарному рейтингу всех отборочных раундов.

Все финалисты, 75 лучших участников отборочного этапа, не прошедших в финал и 75 случайно выбранных среди решивших в отборочном этапе хотя бы одну задачу участников получат футболки Яндекс.Алгоритма!

Расписание раундов и подробные правила можно найти на сайте чемпионата.

Удачи! Санкт-Петербург уже совсем близко!

UPD: Результаты первого раунда признаны официальными, мы поздравляем Kenny_HORROR с блестящим выступлением и убедительной победой с тактикой "все в открытую".

В финальный раунд приглашаются Kenny_HORROR, Petr, tourist, eatmore.

UPD2: Мы поздравляем tourist с победой во втором раунде и приглашаем vepifanov, yeputons, ivan.popelyshev, peter50216 принять участие в финальном раунде!

UPD3: По результатам третьего раунда в финал приглашаются winger, KADR, ainu7, s-quark. Поздравляем!

Кроме того, заслуженное место в финальном раунде занимают

по сумме двух раундов: burunduk3, misof, niyaznigmatul, cerealguy, Mimino, liympanda, romanandreev, watashi, RAVEman;

по сумме всего отборочного этапа: Nerevar, ilyakor, dreamoon_love_AA, pparys.

Уважаемые финалисты! Мы поздравляем вас с отличным выступлением и проходом в финальный раунд. Я свяжусь с вами в ближайшее время для того, чтобы уладить формальности. Пожалуйста, не игнорируйте мои письма =)

UPD4 Доступны материалы второго тестового раунда: Тестовый раунд 2; Материалы

Квалификационный раунд и его разбор были подготовлены Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews и Gassa.

В квалификационном раунде турнира Яндекс.Алгоритм стартовало виртуальный контест 1732 участника, хотя бы одну попытку сделало 1606 участников. Из них 1558 решили хотя бы одну задачу. Отметим, что количество зарегистрировавшихся для участия в турнире — а это 3397 участников — практически вдвое превосходит количество участников, стартовавших контест. С чем это связано — непонятно.

Так как квалификационный раунд проводился в виде виртуального контеста, то участники могли выбрать наиболее удобное для себя время. Наибольшее количество участников онлайн (около 280) было в момент старта раунда, наименьшее — в районе между 3 и 4 часами ночи по Московскому времени (около 20 участников).

Первым хронологически все 6 задач сдал Scott.Ai из Китая; при этом все задачи были сданы «в открытую». Стартовавший почти в 22:00 по Москве i.metelsky (Иван Метельский, Беларусь) сдал задачи A-D «втёмную», E «в открытую» со второй попытки и F «в открытую» с первой и возглавил таблицу с очень неплохим результатом. Однако стартовавший через 4 с половиной часа vepifanov (Владислав Епифанов, Россия) сдал «втёмную» A, B, C, F и «в открытую» D и E с первой попытки, выйдя на первое место по штрафному времени. Уже во вторник утром первую строчку захватывают чемпионы мира из СПб НИУ ИТМО: сначала eatmore (Евгений Капун, победитель финалов ACM ICPC 2009 и 2012), стартовавший около 11 утра, сдаёт все 6 задач «втёмную»... но и он находится на этой строчке всего несколько часов: с той же стратегией, но с лучшим временем его обходит действующий чемпион мира tourist (Геннадий Короткевич, Беларусь). Через сутки после старта квалификации первая тройка выглядит так: Короткевич — Капун — Епифанов. При этом Геннадий Короткевич занял второе место в тестовом раунде, Владислав Епифанов — третье. А победитель тестового раунда — Антон Лунёв (Украина) — стартовал уже ближе к концу времени квалификации. Он сдал «втёмную» задачи A, B, F, D, затем сдал «в открытую» задачу E со второй попытки, затем сдал «втёмную» задачу C и вышел на итоговое третье место, сместив Епифанова на четвёртое. Таким образом, все три победителя тестового раунда оказались в Top4, но в другом порядке. Евгений Капун также получил право участия в отборочных раундах по результатам тестового, так что лучшим из тех, кто ещё не имел права участия в отборочном раунде, оказался занявший в итоге пятое место Иван Метельский. Всего по 6 задач решили 34 участника, при этом наилучший результат участника, сдававшего все задачи «в открытую», — 9-10 место.

Отметим также, что неожиданные затруднения у некоторых участников вызвал тот факт, что в качестве входного и выходного файлов в доступных в системе условиях были указаны stdin и stdout. Некоторые приняли эти обозначения стандартных потоков за имена файлов. В связи с этим жюри приняло решение пересудить такие решения с указанием соответствующих имён файлов; в дальнейшем система в аналогичных случаях во избежание путаницы будет использовать фразы «стандартный ввод» и «стандартный вывод».

Задача A (Древний баскетбольный матч)

В этой задаче требовалось просто сделать то, что написано в условии. Достаточно завести две переменные для подсчёта очков каждой команды и, считывая записи о бросках, увеличивать соответствующую переменную на необходимое количество очков. Узнать, какую переменную нужно увеличивать, можно с помощью оператора if.

Задача B (Простая задача)

Перенесём 1 в левую часть — получим k² - 1 = p₁·p₂, или, раскладывая левую часть на множители, (k - 1)(k + 1) = p₁·p₂. Так как k по условию задачи больше двух, то оба сомножителя в левой части не равны единице, а раз так, то (k - 1) = p₁ и (k + 1) = p₂ (без ограничения общности считаем, что p₂ > p₁). Действительно, левая часть должна делиться и на p₁, и на p₂, то есть если k - 1 = a·p₁, а k + 1 = b·p₂, то (k - 1)(k + 1) = ab·p₁·p₂ = p₁·p₂, так как a и b — целые положительные, то a = b = 1, что и требовалось доказать. Если бы k - 1 делилось на p₂, то оказалось бы, что k - 1 = p₂, k + 1 = p₁, но это противоречит тому, что p₂ > p₁.

Таким образом, задача сводится к поиску таких k, что k - 1 и k + 1 — простые (так называемые «простые числа-близнецы»; интересно, что задача о том, конечно или бесконечно количество пар таких чисел, в настоящий момент так и не решена).

С предложенными во время тура ограничениями это можно сделать любым способом, даже перебирая все (а не только чётные) k и при проверке числа на простоту перебирая все делители до данного числа. Учитывая, что n ≥ 4, «пустой ответ» невозможен, так как k = 4 удовлетворяет условию задачи.

Ещё вариант — раскладывать k² - 1 на простые множители и проверять, что таких множителей ровно два.

Задача C (Настольная игра)

Ответ на первый вопрос посчитать очень просто. Это сумма количеств атомов по всем кучкам. Она равна .

Для того чтобы ответить на второй вопрос, давайте сперва несколько переформулируем его. Из теории игр известно, что позиция в такой игре является проигрышной, если количеств атомов по всем кучкам равен 0. Соответственно, нам нужно найти количество первых ходов таких, что после любого из них количеств атомов по всем кучкам будет равен 0. Обозначим . Существует быстрый способ посчитать x. Для этого можно воспользоваться фактом, что для любого неотрицательного целого k справедливо . Значит, .

Если мы зафиксируем номер кучки i, из которой будем производить первый ход, то количество атомов, которые должны будут в ней остаться после этого хода, определяется однозначно. Оно равно количеств атомов по всем остальным кучкам, то есть . Значит, чтобы из кучки i можно было сделать правильный первый ход, i должно быть строго больше, чем . Это возможно, только если в позиции p, в которой в числе x стоит старший единичный бит, в числе i также стоит единичный бит. Нужно посчитать количество таких i, не превосходящих N. Среди чисел, меньших , их ровно половина. Если в p-м бите числа N стоит единица, то нужно также добавить к ответу .

Задача D (Бесконечная сумма)

Применим несколько преобразований к исходному выражению:

Обозначив , имеем

Теперь нужно только посчитать искомое рекуррентное соотношение и вывести ответ.

Задача E (Лабораторная работа)

Случаи X = 0 или K = 0 являются тривиальными и рассматриваются отдельно.

Понятно, что выгодно, чтобы Гена каждый день решал максимальное количество задач, которое может, а остальных студентов можно распределять по темам, и они могут подстроиться под работу Гены. Если в какой-то теме ещё осталось решить не меньше X задач, то Гена в этот день работает на максимум и решает X задач. Если такой темы нет, то он берет тему с наибольшим количеством задач и решает их, полностью закрывая тему. Таким образом, становится очевидным, какое минимальное количество задач останется после Гены по прошествии некоторого количества дней. Тогда можно двоичным поиском перебирать количество дней, т. е. ответ, затем проверять, успеют ли студенты за этот срок решить оставшиеся после Гены задачи.

Сложность такого решения . Также следует учесть, что нужно предварительно отсортировать темы по значению для поиска тем с максимальным количеством задач, когда у Гены уже нет возможности решать по X. Итоговая асимптотика с учётом того факта, что , и свойств логарифма, получается .

Альтернативное решение заключается в рассмотрении оптимальной стратегии для студентов. Зная, как оптимально действует Гена, можно предположить, как должны действовать студенты: вначале они должны решать тему с наименьшим значением и решать эту тему, пока не станет равным нулю. Когда такие темы закончатся, а задачи ещё останутся, то они могут выбирать любую тему и решать её, пока в ней не закончатся задачи. Таким образом, надо рассмотреть что произойдет первым: либо у Гены раньше закончатся темы с A_i ≥ X, либо у студентов закончатся темы с .

Сложность .

Задача F (Атомы: туда и обратно)

Количество кучек при каждом разделении удваивается. Из этого следует, что если N не является степенью двойки, то заданное состояние никак не получится и ответ «NO».

Если посмотреть последнее разделение, то есть разделение состояния, предшествующего заданному, то из каждой кучки была получена кучка размера X. Значит, как минимум половина кучек будет одинакового размера X. Тогда эти кучки можно отбросить и перейти к такой же задаче с N / 2 кучками. Если на каком-то шаге среди кучек нет хотя бы половины одинаковых, то ответ «NO».

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

Сложность .

Всем привет!

8-го июля в 19:00 по московскому времени стартует квалификационный раунд Яндекс.Алгоритма! Напоминаю, что раунд виртуальный, а это значит, что вы можете запустить его в любой момент в течение суток с момента старта, после чего для вас лично начнется 100-минутная квалификация (даже если начать в 18:59). Пожалуйста, не обсуждайте задачи до 20:40 9-го июля — чей-то квалификационный раунд может продолжаться.

2000 лучших участников, справившихся хотя бы с одной задачей, будут приглашены для участия в отборочном этапе. А для тех, кто прошёл квалификацию в тестовом раунде, данный контест будет отличной возможностью ещё раз прочувствовать тестирующую систему и особенности TCM/Time.

Вперёд, за орденами! На кону почти две сотни футболок и более полумиллиона рублей! =)

Регистрация

Ссылка на тур

UPD: Материалы раунда доступны на официальном сайте соревнования.

Тестовый раунд и его разбор были подготовлены snarknews и Gassa. Задачи тестового раунда уже использовались ранее в других соревнованиях. Все последующие раунды будут состоять из новых оригинальных задач, и вы все еще можете зарегистрироваться и поучаствовать в квалификационном раунде.

По ходу раунда многие участники пытались сдавать задачи «втёмную», время от времени даже выходя на первые строчки таблицы — правда, как оказалось после системных тестов, с одной фактически решённой задачей.

На момент окончания раунда первое место занимал tourist, сдавший все задачи, кроме B, «втёмную». Второе место занимал vepifanov, сдавший A, C и D «втёмную», а B и F — «в светлую» (причём каждую из них — с одной штрафной попыткой), третье — Anton_Lunyov, сдавший «втёмную» только задачу C. У остальных участников было сдано менее пяти задач. После системных тестов выяснилось, что у tourist было неверное решение по A, а у vepifanov — по D; тем самым, единственным участником, сдавшим 5 задач, стал Anton_Lunyov. У tourist — второе место, у vepifanov — третье.

Несколько странно, что задачи B и E (несмотря на не требующие особых знаний элементарные решения как в B, так и в E) остались в значительной степени «невостребованными»: все решившие эти задачи участники вошли в первую тройку, причём tourist решил E, а Anton_Lunyov и vepifanov — B.

Определённую сложность для участников, как оказалось, представляет работа со входными и выходными файлами: с этим было связано более 90% всех заданных жюри вопросов. Так что в последующих раундах Яндекс.Алгоритма файловый ввод-вывод решено не использовать.

Задача A (Окружности)

Данная задача является усложнённым вариантом задачи с нулевого («пилотного») Открытого Кубка, проходившего в мае 2004 года, или же упрощённым до двумерного случая вариантом задачи с Гран-При Москвы 2005 года.

Из формулы для площади треугольника S = abc / 4R получаем, что R = abc / 4S, где a, b и c — длины сторон треугольника. Учитывая, что координаты вершин целые, квадраты длин сторон являются целыми числами, равно как и удвоенная площадь треугольника, и можно вычислить R² точно, представив в виде отношения двух целых a²·b²·c² и 16S².

Так как координаты не превосходят 1400, то максимальное произведение сторон не превосходит 1400⁶·2, что меньше, чем , и вычисления можно производить в беззнаковых 64-битных целых. При этом при сравнении дробей потребуется или использовать встроенные типы для работы с длинными числами (в тех языках, в которых они есть), либо использовать модулярную арифметику, либо вычислять НОД, либо хранить старшую часть числа отдельно...

Отметим, что обычного double недостаточно даже без учёта погрешности вычислений: существует пример двух треугольников, радиусы описанных окружностей для которых различаются менее, чем на 2^- 52. Например, это треугольники с вершинами (0, 0), (1312, 164), (134, 1372) и (0, 0), (1351, 169), (106, 1317).

Вышеприведённый пример был построен при помощи следующего перебора: закрепляем одну вершину в начале координат, другие две — в точках (1400, 0) и (0, 1400), перебираем координаты этих двух точек в некоторой окрестности, вычисляя при этом радиусы описанных окружностей для всех треугольников, сортируем их и находим минимальную разность соседних радиусов после сортировки.

Как и ожидалось, по задаче было сделано много неудачных попыток, связанных с попыткой решения в double и последующим «поиском эпсилона» у большинства участников, которые сразу заметили возможность точного решения, реализация проблем не вызвала.

Задача B (Три дроби)

Эта задача впервые была предложена на Гран-При Москвы в 2005 году в более простой формулировке (без мультитеста).

Проще всего эту задачу решить предрасчётом.

Для заданных ограничений на n и количества запросов имеет смысл перед обработкой запросов построить полную таблицу ответов. Учитывая, что если n — составное число, и для всех простых чисел, меньших n, задача решена, то, представив n в виде произведения a·p, где p — простое, получаем решение . Таким образом, достаточно сначала предпросчётом построить таблицу для всех простых чисел и для n = 4, а затем вычислить вышеуказанным способом значения для остальных чисел.

Берём самую грубую оценку. Так как , то . Так как a > b > c, то , а значит , тем самым ; из аналогичных соображений и . Соответственно, перебираем для всех простых n значения в указанных диапазонах и проверяем, делится ли nbc на 4bc - nb - nc нацело. Если делится, — требуемая тройка получена.

Построенный таким образом предрасчёт даже на очень медленном CoreDuo 1.6Ghz занимает менее минуты. В коде достаточно хранить только b и c, вычисляя оставшееся число по формуле . При этом размер кода не будет превосходить 50k, что меньше, чем source limit.

Кроме того, можно перебрать значения c и попытаться разложить разность в сумму двух «египетских» дробей, использовав алгоритм Фибоначчи; в этом случае решение укладывается в Time Limit без предрасчёта (именно такие решения и сдали оба участника, решивших задачу).

Эта задача представляет собой частный случай известной математической проблемы — гипотезы Эрдёша-Штрауса. В общем случае проблема на данный момент не решена, однако для всех n ≤ 10¹⁴ соответствующее разложение существует.

Для любителей конструктивных решений — несколько формул.

• Если n = 3k + 2, то получаем ,
• Если n = 4k, то получаем ,
• Если n = 4k + 2 и k > 1, то ,
• Если n = 4k + 3, то получаем ,
• Если n = 8k + 5, то получаем .

То есть конструктивной формулы не существует только при n = 24k + 1.

Задача C (Выбери цифры)

Данная задача была впервые предложена на школьном кружке в Санкт-Петербургском ДТЮ в 2006 году.

Эта задача проста и допускает множество различных способов решения. Остановимся на некоторых из них. Далее мы считаем, что s — это заданная строка, а res — искомый результат.

Решение 1

Можно просто перебрать четвёрки позиций, которые мы выберем. Вот примерный код на языке Pascal:

res := 9999;
for i := 1 to 5 do
  for j := i + 1 to 6 do
    for k := j + 1 to 7 do
      for l := k + 1 to 8 do
        res := Min (res, StrToInt (s[i] + s[j] + s[k] + s[l]));

Решение 2

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

res = "".join (min (itertools.combinations (s, 4)))

Решение 3

Перебор можно организовать рекурсивно. Вот функция на языке Java с двумя параметрами: позицией p в строке s и количеством цифр q, которые осталось взять. Она вызывается из основной программы как recur (8 - 1, 4) и идёт по позициям строки с конца.

int recur (int p, int q) {
  if (q < 0 || p + 1 < q) return 9999;
  if (p < 0) return 0;
  return Math.min (recur (p - 1, q),
    recur (p - 1, q - 1) * 10 + s.charAt (p) - '0');
}

Решение 4

Можно решать эту задачу методом динамического программирования. Два параметра — количество просмотренных позиций i и количество выбранных позиций j. Значение целевой функции f(i, j) — минимальное число, которое можно получить. Из каждого состояния можно пойти вперёд двумя способами: либо выбрать, либо пропустить текущую позицию, после чего переместиться на следующую позицию в строке. Ниже представлен код на языке C/C++. Ответ находится в ячейке таблицы f[8][4].

memset (f, 0x3F, sizeof (f));
f[0][0] = 0;
for (i = 0; i < 8; i++) {
  for (j = 0; j <= 4; j++) {
    f[i + 1][j] = min (f[i + 1][j], f[i][j]);
    f[i + 1][j + 1] = min (f[i + 1][j + 1],
      f[i][j] * 10 + (s[i] - '0'));
  }
}

Задача D (Различные сомножители)

Данная задача была впервые предложена на школьном кружке в Санкт-Петербургском ДТЮ в 2009 году.

Начнём разбор с теста, который имел номер 15: n = 112 500 = 2²·3²·5⁵. Его сложность заключается в том, что нельзя выбирать делитель 2·3 = 6: в противном случае всего делителей получится не больше шести. Вместо этого следует выбрать следующее разложение на семь сомножителей: 112 500 = 1·2·3·5·10·15·25.

Это минимальный тест, на котором не работают некоторые простые, но неправильные решения. Одно из таких решений — жадно выбирать делители, начиная с самых маленьких, пока после добавления очередного делителя d оставшееся число строго больше d. На этом тесте оно находит делители 1·2·3·5·6, и остаётся разложить на делители 625 = 5⁴, но ни 5, ни 25 = 5² взять нельзя.

Авторское решение — перебор. Тривиальный рекурсивный перебор делителей до корня в порядке возрастания успевает отработать менее чем за секунду. Следующая функция на языке C/C++, будучи запущена как recur (n, 1, 0), записывает в res количество делителей, а в массив best — сами делители. Параметры имеют следующий смысл: n — число, которое осталось разбить на множители, k — минимальный следующий делитель, а cur — количество уже выбранных делителей.

void recur (int n, int k, int cur) {
  if (res < cur + 1) {
    res = cur + 1;
    now[cur] = n;
    memmove (best, now, sizeof (best));
  }
  for (int d = k; d * (d + 1) <= n; d++)
    if (n % d == 0) {
      now[cur] = d;
      recur (n / d, d + 1, cur + 1);
    }
}

Как оценить, насколько быстро работает такой алгоритм? Можно заметить, что ответ не очень большой: поскольку произведение первых 13 натуральных чисел больше, чем 10⁹, ответ не превосходит 12. Это означает, что первый if сработает не более 12 раз. Также полезно знать, что у чисел, не превосходящих 10⁹, не более 1344 различных делителей (http://oeis.org/A066150).

Проще всего написать программу для грубой оценки, которая посчитает количество вызовов рекурсивной функции (язык C/C++). Здесь n — число, которое осталось разложить на множители, а k — минимально возможный следующий множитель.

int count (int n, int k) {
  int res = 0;
  for (int d = k; d * (d + 1) <= n; d++)
    res += 1 + count (n / d, d + 1);
  return res;
}

Эта программа отличается от нашего перебора тем, что в recur мы будем заходить внутрь рекурсии не на каждой итерации цикла по d, как в count, а только тогда, когда n делится нацело на d. Зато она позволяет нам использовать максимально возможное n для оценки (хоть и грубой) худшего случая, а не искать то большое число с большим количеством делителей, на котором реальная программа работает дольше всего.

При вызове count (1000000000, 1) результат равен 151 631 365. Если мы учтём, что единицу можно всегда взять отдельно и искать делители, начиная с двойки, то оценка сверху на количество делений будет равна результату count (1000000000, 2) — это число 75 815 682 (в два раза меньше). На самом же деле, поскольку корень из числа порядка 10⁹ имеет порядок 30 000, а делителей до корня не больше 1344 / 2 = 672, понятно, что делений будет в разы меньше. Максимальное число делений и/или взятий остатка от деления по всем тестам жюри оказалось равно 15 395 811.

Есть и более быстрые варианты перебора. Например, можно перебирать не все числа до корня, а только делители числа n, которые можно заранее найти за . Можно также изначально разложить число n на простые множители и искать делители в виде наборов степеней для каждого из этих множителей.

Задача E (Таблица чемпионата)

Данная задача является адаптированным под memory limit=64 MiB вариантом задачи с Гран-При Москвы 2005 года. В первоначальной задаче ограничение по памяти было равно 3Mb, а длины названий команд не превышали 15 символов.

Существует два принципиально различных случая: когда все три утерянных числа относятся к одной команде и когда как минимум одно число относится к другой команде (или же утеряно меньше трёх чисел).

Обозначим количество матчей, сыгранных i-й командой, за P_i, количество побед — за W_i, количество ничьих — за D_i, количество поражений — за L_i и количество очков — за S_i.

Тогда верны следующие соотношения: W_i + D_i + L_i = P_i и 3W_i + D_i = S_i. В случае, если не все три утерянных числа относятся к одной команде, получаем, что надо решить несколько систем из двух линейных уравнений с не более чем двумя неизвестными.

В случае, если все три утерянных числа относятся к одной команде, третье уравнение получаем из того факта, что суммарное количество побед у всех команд равно суммарному количеству поражений, то есть W_i + W_- i = L_i + L_- i, где W_- i — суммарное количество побед у всех команд, кроме i-й, а L_- i — суммарное количество поражений у всех команд, кроме i-й.

Так что однозначное восстановление возможно всегда.

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

Так что входной файл надо читать по строкам два раза: в первый раз — для того, чтобы построить соответствующую систему уравнений (при чтении суммируются W_i и L_i для составления системы во втором случае), во второй раз — чтобы найти содержащую ответ строку.

Задача F (Электротакси)

Данная задача была предложена польскими авторами и впервые была использована на первом этапе Всепольской школьной олимпиады по информатике сезона 2012-2013.

Очевидно, что или участок от таксопарка до точки назначения можно проехать без пересадок, или добраться до точки назначения невозможно (так как такси, которое доедет до точки назначения, обязано проехать участок от таксопарка до точки назначения полностью). Поэтому «зарезервируем» машину с минимальным запасом хода, которая может доехать от таксопарка до точки назначения, а также построим самую удалённую от точки назначения точку Z, из которой эта машина сможет забрать пассажира и доставить в точку назначения. Если таксопарк находится в точке назначения, то «резервирование» не производится.

Далее отсортируем «незарезервированные» машины по убыванию запаса хода и будем всякий раз выбирать машину с наибольшим запасом хода. Покажем, что этот алгоритм даёт как минимум не худшее решение по сравнению с каким-либо другим. Пусть сначала используется машина с запасом хода X₁, а затем — машина с запасом хода X₂, при этом пассажир изначально находится на расстояни a от таксопарка (и по другую сторону от точки назначения). Тогда пассажир проедет (X₁ - a) + (X₂ - (2a - X₁)) = 2X₁ + X₂ - 3a километров. Если X₂ > X₁, то, поменяв местами X₂ и X₁, увидим, что расстояние, которое проехал пассажир, увеличилось. Если машина с наибольшим запасом хода уже не может доехать (или «незарезервированные» машины закончились до того, как пассажир проехал точку Z), то добраться до точки назначения невозможно.

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

Мы хотели бы подробнее рассказать вам о финале чемпионата, который состоится 21–23 августа в Санкт-Петербурге. Заключительный раунд Алгоритма пройдет в необычном для IT-мероприятий месте — во дворце великого князя Владимира Александровича, построенном в 1870 году.

В финале лучшие участники чемпионата останутся один на один с тестирующей системой. Никакого интернета или заготовленного кода — только «чистая» машина и выбранная среда разработки. За их борьбой можно будет следить посредством текстовой трансляции.

Не откладывайте в долгий ящик регистрацию: тестовый раунд начнется уже завтра.

Ещё одна хорошая новость: мы решили почти удвоить количество сувенирных футболок. Теперь майку с символикой Яндекс.Алгоритма получат 75 лучших участников отборочного этапа и ещё 75 человек, выбранных случайным образом — из тех, кто решил хотя бы одну задачу. И, разумеется, все финалисты.

UPD: Тестовый раунд доступен для участников: http://algorithm.contest.yandex.ru/contest/306.

Зрители смогут следить за развитием событий, перейдя по ссылке http://algorithm.contest.yandex.ru/contest/306/standings.

UPD2 Результаты тестового раунда доступны на сайте соревнований