Всем привет! :)

На случай, если вы пропустили рассылку, сообщаем, что сегодня в 10:00 UTC +3 стартовал второй раунд Оптимизационного трека. Как и первый раунд, он продлится 7 дней. Вам предложена одна задача, которая не предполагает наличие полного решения, но допускает множество подходов. По результатам двух раундов (смотрите раздел 3 в https://contest.yandex.ru/algorithm2018/rules/ — правила суммирования раундов одинаковы для алгоритмического и оптимизационного треков) будут определены победители трека и 128 будущих обладателей футболок с символикой конкурса.

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

Регистрация на конкурс еще открыта, так что всё в ваших руках — удачи!

Всем привет!

Меня зовут Роман Удовиченко и я рад всем сообщить, что первый оптимизационный раунд Яндекс.Алгоритма в самом разгаре! В этот раз мы приглашаем вас порешать задачу от команды разработки беспилотного автомобиля Яндекса.

Беспилотное будущее, как мы надеемся, не за горами, поэтому мы предлагаем вам составить алгоритм для оптимального управления целым флотом беспилотных такси. Разумеется, задача довольно сильно упрощена и в реальности всё гораздо сложнее, но и времени на её решение у вас всего лишь неделя. Написать базовое решение для предложенной задачи очень просто, а вот улучшить его — задача не столь тривиальная. Сможете ли вы придумать и реализовать что-нибудь действительно интересное и необычное? Всё в ваших руках, а времени ещё более чем достаточно :)

Авторов лучших решений в оптимизационном треке ждет денежный приз, а топ-128 — крутые футболки с символикой мероприятия. А если вы хотите попробовать свои силы в разработке настоящего беспилотника, то пишите мне в личные сообщения ;)

Удачи!

Задача A(div 2) — ЛНПП

Предполагалось, что эту задачу можно решить, не читая её условия, а только глядя на примеры :)

Найдём в заданной строке символ, который идёт в алфавите позже всех, обозначим его через z. Если этот символ встречается в строке p раз, то ответ — это строка a, состоящая из символа z, повторённого p раз.

Почему это так? Из определения лексикографического сравнения и из того, что символ z — максимальный в строке, несложно понять, что если какая-то другая подпоследовательность b заданной строки лексикографически больше a, то строка b обязана иметь большую длину, чем a, и при этом a должна являться префиксом (началом) b. Однако строка b должна также быть палиндромом, поэтому последний её символ — обязательно z. В таком случае в строке b должно быть больше вхождений символа z, чем в исходной строке s, что невозможно, так как b --- подпоследовательность s.

Кроме того, ограничение на длину строки было совсем небольшим, поэтому задачу можно было решить перебором всех подпоследовательностей строки. Для каждой из них нужно проверить, является ли она палиндромом, и из всех являющихся выбрать лексикографически наибольшую. Сложность такого решения составляет O(2ⁿ·n), где n — длина строки (в отличие от решения выше, сложность которого O(n)).

Задача В(div 2) — Инновационно новая простая задача

Ограничения в задаче были настолько малы, что проходило решение со сложностью O(m·kⁿ). В описании каждой задачи достаточно перебрать все возможные подпоследовательности слов, являющиеся перестановками описания Лёшиной задачи, для каждой из них вычислить количество инверсий, и выбрать перестановку с минимальным количеством инверсий. Это можно сделать либо с помощью рекурсии, либо, например, с помощью необходимого количества вложенных циклов (от 1 до 4).

Вот пример псевдокода для случая n = 4:

w - массив слов задачи Лёши
s - описание очередной задачи из архива
best = 100
for a = 1 to k do
    for b = 1 to k do
        for c = 1 to k do
            for d = 1 to k do
                if s[a] == w[1] and s[b] == w[2] and s[c] == w[3] and s[d] == w[4] then
                    inversions = 0
                    if a > b then inversions = inversions + 1
                    if a > c then inversions = inversions + 1
                    if a > d then inversions = inversions + 1
                    if b > c then inversions = inversions + 1
                    if b > d then inversions = inversions + 1
                    if c > d then inversions = inversions + 1
                    if inversions < best then
                        best = inversions

В конце нужно выбрать задачу с минимальным значением best и вывести ответ в соответствующем формате.

Задача A(div 1)/C(div 2) — Чёткая симметрия

Интересно, что первоначально у авторов была идея не включать случай x = 3 в претесты. Представьте, сколько было бы в этом контесте сделано успешных взломов — при том, что из первых 43 решений по этой задаче ни одно претесты не прошло :)

Заметим, что ответ n — всегда нечётное число. Действительно, если n чётно, то две центральные строки матрицы A обязаны содержать только нули — в противном случае найдутся две соседние клетки, содержащие единицы. Аналогичное требование относится и к двум центральным столбцам матрицы A. Заменив две центральные строки на одну и два центральных столбца на один, при этом оставив в них нули, получим матрицу с такой же остротой, но со стороной на единицу меньше.

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

Заметим, что матрица со стороной n и остротой при нечётном n существует. Раскрасим все клетки матрицы в шахматном порядке и в чёрные клетки поставим единицы, а в белые — нули. Несложно убедиться, что такая матрица является и чёткой, и симметричной, и при этом имеет остроту ровно .

Интуитивно кажется, что раз существует матрица с остротой , то существует матрица и с любой меньшей остротой. Это верно всегда, кроме одного-единственного случая — не существует матрицы со стороной 3 и остротой 3, хотя и существует матрица со стороной 3 и остротой 5.

Покажем, что утверждение выше верно при нечётных n ≥ 5. Построим матрицу с остротой , как показано выше, и будем постепенно превращать единицы в нули, уменьшая остроту. Клетки с единицами в матрице бывают трёх типов.

Первый тип — центральная клетка. Она ровно одна, при этом можно превратить число в ней в ноль, и матрица не перестанет удовлетворять условию задачи.

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

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

Теперь для получения требуемой остроты x будем действовать жадно. Будем заменять единицы на нули в клетках третьего типа, делая это в четырёх клетках сразу, до тех пор, пока текущая острота превышает x как минимум на 4 и ещё есть клетки третьего типа с единицами. После этого начнём убирать клетки второго типа по парам, пока текущая острота превышает x хотя бы на 2. К этому моменту острота матрицы равна либо x, либо x + 1. Если она равна x + 1, поставим ноль в центральной клетке и получим матрицу с остротой x. Несложно проверить, что мы сможем получить матрицу любой остроты, действуя по этому жадному алгоритму.

Почему такие же рассуждения не работают при n = 3? Потому что в матрице с остротой 5, полученной из шахматной раскраски, отсутствуют клетки второго типа. При n ≥ 5 в такой матрице присутствуют клетки всех типов, что и является залогом успеха. Ответы для x ≤ 5 лучше найти вручную, но аккуратно — например, многие участники решили, что при x = 2 ответ 5, а не 3.

Задача В(div 1)/D(div 2) — Угадай автомобиль!

Нам нужно найти такие x и y, при которых величина принимает минимальное возможное значение. Эту величину можно преобразовать к виду , и заметить, что поскольку левая часть не зависит от y, а правая от x, то можно минимизировать каждую из частей по отдельности. Рассмотрим, как минимизировать часть , вторая минимизируется аналогично. Поскольку выражение в скобках не зависит от j, эту часть можно переписать в виде , где . Теперь достаточно просто перебрать все возможные значения x, и вычислить для каждого из них искомую величину, после чего выбрать x, для которого это значение минимально. Точно так же находится оптимальное значение y.
Итоговая сложность решения — O(n·m + n² + m²).

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

Главный действующий герой задачи — Ra16bit.

Задача С(div 1)/E(div 2) — Хрупкие мосты

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

Для любого решения полезно заметить следующий факт. Допустим, искомый путь начинается на платформе i и заканчивается на платформе j (i ≤ j, если это не так, можно поменять начало и конец пути местами). Тогда все мосты, находящиеся между платформами i и j, будут пройдены в этом пути нечётное число раз, а все остальные мосты — чётное число раз.

Давайте найдём максимальную длину пути с концами на платформах i и j. Для этого для всех платформ найдём вспомогательные величины: left_i — максимальная длина пути, начинающегося и заканчивающегося на платформе i и при этом проходящего только по мостам левее платформы i; right_j — аналогично для мостов правее платформы j. Также для каждого моста определим odd_i — наибольшее нечётное число, не превосходящее a_i, и для каждой платформы определим sumOdd_i — сумму odd_j по всем мостам левее платформы i.

Тогда максимальная длина пути с концами на платформах i и j (i ≤ j) равна left_i + right_j + (sumOdd_j - sumOdd_i) или, что то же самое, (right_j + sumOdd_j) + (left_i - sumOdd_i).

Теперь мы можем найти пару (i, j), для которых эта величина наибольшая, за линейное время. Переберём j. Из формулы очевидно, что нужно найти такое i ≤ j, что (left_i - sumOdd_i) максимально. Если перебирать j от 1 к n, то можно хранить текущее максимальное значение этой величины для всех i ≤ j и пересчитывать его при переходе к следующему j, сравнив (left_j - sumOdd_j) с текущим максимумом и, возможно, этот максимум обновив. Таким образом, для каждого j нужно проверять не все значения i ≤ j, а только одно.

Осталось показать, как быстро искать все left_i (все right_j ищутся аналогично). Понятно, что left₁ = 0, далее будем считать left_i, используя left_i - 1. Заметим, что если a_i - 1 = 1, то left_i = 0, так как после перехода по мосту на платформу (i - 1) этот мост рухнет и вернуться на платформу i уже будет невозможно. Если же a_i - 1 > 1, то left_i = left_i - 1 + even_i - 1, где even_i - 1 — наибольшее чётное число, не превосходящее a_i - 1. Действительно, можно перейти по мосту на платформу (i - 1), проделать путь, соответствующий left_i - 1, а потом ходить по мосту между платформами (i - 1) и i, пока лимит на количество переходов не станет меньше 2 (при этом закончить нужно на платформе i).

Таким образом, общая сложность этого решения — O(n).

Задача D(div 1) — Инновационно новая задача

Первое решение, которое приходит на ум — рекуррентное соотношение f[i][j] =  (минимальное возможное количество инверсий, если среди первых j слов встречается перестановка слов, входящих в маску i). В таком решении параметр j изменяется от 0 до 500000, i — от 0 до 2¹⁵ - 1, а пересчёт значений происходит за O(1) (либо используем очередное слово, либо нет). Это слишком много.

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

Понятно, что при фиксированном подмножестве слов и количестве инверсий оптимально выбрать самые ранние вхождения этих слов, которые дают такое количество инверсий. Пусть f[i][j] =  (минимальное число z такое, что среди первых z слов найдётся перестановка слов из маски i, содержащая в точности j инверсий). База — f[0][0] = 0, f[0][j] = ∞ для j > 0. Пересчёт значений происходит следующим образом: перебираем слово q из маски i, которое было последним. Зная это слово, и количество инверсий j, легко вычислить количество инверсий j', которое было без этого слова — это j минус количество слов в маске, больших q (по номеру в описании Лёшиной задачи). Пусть p = f[i^(1«q)][j']. Тогда в качестве очередного возможного значения для f[i][j] нужно рассмотреть индекс p₂, равный позиции следующего вхождения слова q после позиции p. Для быстрого поиска таких значений необходимо заранее для каждой задачи из архива посчитать массив next[500010][15] такой, что next[i][j] = (минимальный индекс k > i такой, что k-е слово в описании текущей задачи равно j-му слову в описании задачи Лёши). Такой массив несложно посчитать за один проход справа налево.

Суммарное количество операций можно вычислить по формуле m·(k·n + 2ⁿ·C_n²·n), где m — количество задач в архиве, k — количество слов в описании одной задачи, n — количество слов в описании задачи Лёши. При заданных ограничениях эта величина составляла около 200 миллионов, и авторские решения (включая решение на Java) работали не более двух секунд. TL был выставлен довольно-таки лояльно, 5 секунд.

Главные действующие герои задач D(div 1) и B(div 2) — Chmel_Tolstiy и ivan.metelsky.

Задача E(div 1) — Насквозь бюрократическая организация

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

Допустим, мы сделали какие-то k запросов. Сопоставим каждому из n человек строку из k бит, где i-ый бит равен единице, если этот человек был указан в i-ом запросе, и равен нулю в противном случае. Заметим, что мы сможем определить точную дату приёма для каждого человека в том и только в том случае, если всем n людям соответствуют попарно различные k-битовые строки. На самом деле, если двум людям соответствуют одинаковые строки, то они могли бы поменяться датами между собой и ответы на запросы не изменились бы. Если же всем людям соответствуют разные строки, для каждой даты можно определить, кто именно записан на эту дату, рассмотрев множество запросов, в ответах на которые эта дата фигурирует, и найдя человека, который указан ровно в том же множестве запросов.

Ограничение в m пустых строчек в бланке означает, что в каждой из k позиций в строках суммарное число единиц по всем n числам не должно превышать m. Таким образом, функция maxN(m, k) должна возвращать максимальную мощность множества различных k-битовых строк, для которых выполняется это ограничение. Давайте ослабим это ограничение: будем искать множество, в котором в сумме по всем разрядам количество единиц не превышает k·m. Как мы докажем после, ответ от этого не изменится.

С таким ослабленным ограничением задача решается простым жадным алгоритмом. Логично, что сначала лучше брать те строки, в которых меньше единиц. Будем перебирать количество единиц i в строке от 0 до k, а также хранить переменную t, обозначающую количество единиц, которое ещё можно поставить (изначально она равна k·m). Тогда на i-ом шаге максимально можно взять чисел с i единицами. Добавим p к ответу, а от t отнимем p·i. Отметим, что значения C_kⁱ нужно считать аккуратно — они могут оказаться слишком большими, и нужно не допустить переполнения.

Можно показать, что сложность такого решения на один тест составляет не более O(log²n).

Осталось доказать необходимое утверждение. Идея доказательства ниже принадлежит rng_58 (авторское было заметно сложнее).

Решим задачу жадным алгоритмом с ограничением в k·m на общее число единиц. Полученное множество может не удовлетворять ограничению в m единиц на каждый разряд — тогда в некоторых разрядах количество единиц больше m, а в некоторых меньше m. Возьмём некоторый разряд X, в котором более m единиц, и некоторый разряд Y, в котором менее m единиц. Найдём строки, в которых стоит 1 в X и 0 в Y (допустим, таких строк x) и строки, в которых стоит 0 в X и 1 в Y (допустим, таких строк y). Понятно, что x > y. В каждой из x строк мы можем попробовать поставить 0 в X и 1 в Y — тогда полученная строка может либо остаться уникальной, либо совпасть с какой-то из y строк (но ровно одной). А поскольку x > y, точно найдётся одна из x строк такая, что в ней можно поменять местами цифры в разрядах X и Y и все строки останутся различными. Сделаем это. Теперь в разряде X стало на одну единицу меньше, а в разряде Y — на одну единицу больше. Это значит, что суммарное число лишних единиц в разрядах уменьшилось (т.к. в Y единиц не стало больше m). Таким образом, повторяя эту операцию необходимое число раз, мы сможем добиться того, чтобы в каждом разряде было не более m единиц.

Футболки, футболки, футболки... Футболки разыгрывают все, кому не лень. Каждый месяц на codechef.com, каждый год на Topcoder и Code Jam, в этом году добавились Hacker Cup, Russian Code Cup и Yandex.Algorithm. Футболки раздают в ЛКШ. Футболки дают на АСМ/ICPC (1/4 финала, финал). Участвуя в полуфинале NEERC, можно стать счастливым обладателем футболки от Яндекса, а в прошлом году и от Codeforces. Футболку получает каждый участник Петрозаводских сборов, кроме этого, на последних сборах проводился спонсорский Codeforces Beta Round, за который тоже давали футболки. И это ещё не говоря о различных малоизвестных контестах, таких как, например, Bitwise. Школьникам дают футболки на ВКОШПе, на международной олимпиаде, на белорусской республиканской олимпиаде (не знаю, дают ли на всеросе, не имел возможности в нём поучаствовать). Довольно-таки однообразно, не находите?