Разбор всех задач финального раунда Яндекс.Алгоритма 201506.08.2015 19:34

Сегодня завершился финал Яндекс.Алгоритма — ежегодного чемпионата по спортивному программированию, который организует Яндекс. В 2015 году состязание проходило полностью в онлайне — на платформе Яндекс.Контест. Заявки на участие подали программисты из 73 стран. Больше всего участников — из России, Украины, Беларуси, Казахстана, Индии, США, Японии и Китая, но вообще география чемпионата крайне обширна — Бразилия, Индонезия, Перу, Доминиканская Республика, Мозамбик, Сенегал, Каймановы острова. 8,9% зарегистрировавшихся — девушки. Примерно половина всех участников — студенты. Всего мы получили заявки от 3722 человек, из которых до финала дошли 28.

А победителем Яндекс.Алгоритма-2015 стал Геннадий Короткевич. Он по привычке показал лучший результат, решив в финальном раунде пять из шести задач и получив при этом 80 минут штрафного времени. Геннадий занимал первое место в чемпионате Яндекса и в 2013, и в 2014 годах.

Второе место занял Пётр Митричев, а третье — Евгений Капун. Они решили по четыре задачи, при этом Пётр набрал 31 штрафную минуту, а Евгений — 79 минут. Результаты всех финалистов можно посмотреть на сайте Яндекс.Алгоритма.

Задачи для Яндекс.Алгоритма составляет международная команда, в которую входят как сотрудники Яндекса, так и приглашённые эксперты — в том числе победители и финалисты состязаний ACM ICPC и Topcoder Open. И мы по традиции подготовили для вас разборы всех заданий. Решить все из них никому не удалось. Больше всего участников справились с задачей B, а вот задания A и D решило всего по одному человеку.

Задача A. Task Manager

Автор разбора и задачи — Глеб Евстропов. Выпускник МГУ, двукратный золотой медалист ACM ICPC.

Стажёр Бомбослав работает над улучшением менеджера задач, используемого сотрудниками Яндекса. Текущая версия менеджера ассоциирует с каждой из n назначенных сотруднику задач два параметра ci и ui — важность и срочность данной задачи. Более высокие значения параметров соответствуют большей важности или срочности данной задачи.

Любой сотрудник может сам выбрать порядок, в котором он будет выполнять назначенные ему задачи. Единственное ограничение имеет следующий вид: если задача i является одновременно более важной и более срочной, чем задача j, то есть ci > cj и ui > uj, то она должна быть выполнена раньше.

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

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

Формат ввода. В первой строке ввода задано единственное число n — количество задач для данного сотрудника (1≤ n ≤ 100 000).
Следующие n строк описывают задачи в менеджере. Каждая из них содержит три целых неотрицательных числа ci, ui и pi — важность, срочность и желание выполнять данную задачу сотрудником, соответственно (0 ≤ ci, ui, pi ≤ 109). Гарантируется, что все pi попарно различны.

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

Решение задачи A

Заметим, что условие различности всех pi является существенным, так как оно позволяет нам пользоваться жадным алгоритмом, итеративно извлекающим минимальный исток. Более подробное описание алгоритма:

1. Пусть построен некоторый префикс оптимального ответа, от исходного графа остался только некий подграф.
2. Рассмотрим множество истоков текущего графа, то есть множество вершин, в которые не входит ни одно ребро. Очевидно, что текущую топологическую сортировку необходимо продолжить какой-то из вершин, принадлежащей этому множеству. Назовем эти вершины активными.
3. Поскольку все pi различны, то в силу структуры лексикографического сравнения следующая вершина определяется однозначно. Добавляем активную вершину с максимальным pi к текущему префиксу ответа и удаляем её из графа.

Асимптотическая сложность данного решения — O (V ∙ E), если просто реализовать текстовое описание алгоритма. Легко достигается асимптотика O (V ∙logV + E) — требуется лишь запоминать текущие степени полувхода для всех вершин и хранить множество активных вершин в какой-нибудь структуре с возможностью быстрого добавления элемента и извлечения максимума. Такой структурой может служить двоичная куча или любое сбалансированное дерево поиска.

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

Обратимся к идее сжатого двумерного дерева отрезков. Подробный разбор данной структуры здесь не предполагается.Напомним лишь, что она имеет размерность O (n ∙ logn) по памяти и позволяет отвечать на групповые запросы (такие, как максимум, минимум или сумма в прямоугольнике за время O (log2 n)). Данная сложность достигается за счёт разбиения области запроса на O (logn) полос по одной из размерности, для каждой из которых уже построена структура одномерного дерева отрезков. В свою очередь каждая из данных полос снова разбивается на O (logn) частей.

Построим указанное в предыдущем абзаце разбиение для каждого из V углов вида x > xi и y > yi. Тогда вершина попадает в множество активных в момент, когда все элементарные области, составляющие данный угол, становятся пустыми. Будем поддерживать для каждой элементарной области текущее количество точек внутри неё, а также для каждой точки количество элементарных областей, образующих её угол и ещё не являющихся пустыми. Обратите внимание, здесь имеются в виду не все элементарные области попадающие в данный угол, а лишь те O (log2 n) из них, которые образуют разбиение области в запросе к двумерному дереву отрезков.

Шаг алгоритма сейчас выглядит следующим образом.

1. Выбрать активную вершину с максимальным pi и удалить её из множества активных.
2. Рассмотреть все элементарные области двумерного дерева отрезков, которые содержали точку, соответствующую данной вершине. По свойствам данной структуры их будет не более, чем O (log2 n). У каждой такой области уменьшить счётчик на единицу.
3. Для всех областей, счётчик которых стал равен нулю, необходимо рассмотреть список всех точек — таких, чтобы данная область входила в разложение соответствовавшего им угла. Эти списки строятся заранее, ещё до запуска основного алгоритма. Для каждой точки из списка счётчик также уменьшается на один.
4. Для всех точек, счётчик которых стал равен нулю, соответствующие им вершины добавляются в множество активных.

Общее время работы: O (n∙log2 n), как и занимаемая память.

Задача B. На пикник на автобусе

Автор задачи и разбора — Михаил Тихомиров. Выпускник МФТИ, финалист Topcoder Open 2014.

Каждое лето сотрудники Яндекса выезжают на природу на Яндекс.Пикник. Для сотрудников, у которых нет своей машины, арендуются автобусы от офиса до места отдыха.

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

Формат ввода. Первая строка содержит одно целое число(1 ≤ n ≤ 100) — количество групп сотрудников. Следующая строка содержит n целых чисел ai, разделённых пробелами — размеры групп (1 ≤ ai ≤6).

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

Решение задачи B

Общая идея: если количество мест в ряду не превосходит шести, работает простой жадный алгоритм.

Очевидно, каждую группу размера 6, 5 или 4 необходимо разместить в отдельном ряду. Группы размера 3 надо расположить максимально плотно: заполнить рядов парами троек, и, возможно, одну оставшуюся тройку поместить в отдельный ряд. Действительно, предположим, что в оптимальном разбиении присутствует два ряда, каждый из которых содержит по одной тройке. Тогда поменяем местами одну из троек с теми группами, которые сидят в том же ряду, что и вторая тройка. После нескольких таких операций переместим все тройки так, чтобы описанное условие выполнялось.

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

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

Задача C. Целое произведение

Автор задачи и разбора — Олег Христенко. Координатор Яндекс.Алгоритма, Открытого кубка, проекта snarknews.

Дано N — 1 дробей u_i/d_i, причём 2 ≤ ui ≤ N и 2 ≤ di ≤ N, все ui попарно различны и все di попарно различны. Выберите не менее 1 и не более N / 10 дробей так, чтобы их знаменатели были степенями простых чисел, а произведение всех выбранных дробей было целым числом.

Формат ввода. В первой строке задано одно целое число N (10 ≤ N ≤ 106). Каждая из последующих N — 1 строк содержит одну дробь в формате u_i/d_i (2 ≤ ui, di ≤ N, ui ≠ uj при i ≠ j, di ≠ dj при i ≠ j). Пробелов между числами и знаком »/» нет.

Формат вывода. Выведите две строки. Первая должна содержать целое число M — количество выбранных дробей. Следующие M строк должны содержать сами выбранные дроби, заданные в том же формате, что и во вводе, по одной на строку. Знаменатели всех выбранных дробей должны быть степенями простых чисел, то есть иметь вид , где pi — простое, а ki — целое положительное число. Дроби можно выводить в любом порядке. Одну дробь можно выбрать не более одного раза.

Если решений несколько, выведите любое. Если решения не существует, выведите в первой строке -1.

Разбор задачи C

Заметим, что для N от 105 до 2∙105 количество простых чисел, не превосходящих N, менее N/10.
Покажем, что если требуется выбрать P (N) или более дробей, где P (N) — количество простых чисел, не превышающих N, то задача всегда имеет конструктивное решение.

Будем выбирать следующим образом. Сначала выберем дробь N/2. Если N чётно, ответ получен. Если N нечётно, выберем дробь с наименьшим простым делителем N в качестве знаменателя. Если числитель является чётным, первые две дроби являются ответом. Если числитель делится на знаменатель, вторая дробь является ответом. На каждом следующем шаге мы пробуем выбрать дробь с наименьшим простым делителем предыдущего числителя в качестве знаменателя. Если оказывается, что это число уже было в знаменателе на i-м шаге, то участок с i-й дроби до последней выбранной является ответом. Иначе выбираем соответствующую дробь. В наихудшем случае мы таким образом выберем в качеств знаменателей все простые числа, не превосходящие N, после чего неизбежно случится повторение.

Задача D. Объединяй и властвуй

Автор разбора и задачи — Глеб Евстропов.

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

Имеется исходная последовательность ai, состоящая из n чисел от 1 до 5, описывающая размеры последовательных частей во фрагментации исходных данных. Также имеется последовательность bi, состоящая из m чисел от 1 до 5, аналогично описывающая размеры последовательных частей во фрагментации образца.

За одно действие разрешается выбрать любые два соседних элемента в одной из двух последовательностей и объединить их, заменив одним элементом со значением, равным их сумме. Так, из последовательности 1, 2, 2 за одно действие можно получить только последовательности 3, 2 и 1, 4. После выполнения данной операции в последовательности вполне может появиться элемент, который больше, чем 5. Требуется вычислить минимальное количество действий, которые требуется проделать с данными последовательностями, чтобы последовательность bi стала подстрокой последовательности ai.

Формат ввода. В первой строке ввода содержатся два целых числа n и m — количество фрагментов в разбиении исходных данных и количество фрагментов в разбиении шаблона для поиска, соответственно (1 ≤n, m ≤ 200 000).

Следующая строка содержит n чисел ai, каждое от 1 до 5 включительно, задающих размеры фрагментов в разбиении исходных данных.

Последняя строка содержит m чисел bi, описывающих размеры фрагментов в разбиении шаблона в аналогичном формате.
Формат вывода. Выведите одно целое число — минимальное количество действий, необходимое, чтобы вторая последовательность стала подстрокой первой. Если добиться этого невозможно, то выведите -1.

Разбор задачи B

Научимся для начала решать за полиномиальное время задачу проверки того, что существует какой-нибудь положительный ответ. Переберём две границы в исходной последовательности. Как проверить, что последовательность bi в принципе возможность отобразить в выбранный фрагмент ai? Проверим, является ли сумма всех элементов bi равной сумме выбранных элементов ai. Легко увидеть, что данное условие является необходимым и достаточным, так как без ограничения на количество операций можно просто объединить все элементы в один.

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

Пусть мы знаем, что сумма элементов последовательности bi равна сумме элементов в некоторой последовательности ci (подотрезок ai). Определим минимальное количество операций слияния, необходимое, чтобы сделать эти последовательности одинаковыми. Рассмотрим произвольное положительное число x, такое что у обеих последовательностей существует префикс равный x. Одно из таких чисел x будет соответствовать первому символу в обоих последовательностях после выполнения всех объединений. Несложно увидеть, что если существуют два различных x1 и x2(x1 < x2), отвечающих указанному выше требованию, то ответ с минимальным количеством объединений (а следовательно, и максимальной длины) никогда не выгодно начинать с x2.

Действительно, так как каждому элементу в итоговом ответе соответствует подотрезок в каждой из последовательностей bi и ci, то этот подотрезок всегда можно разбить на два, которые будут образовывать элементы x1 и x2 — x1. Из этого следует, что оптимальный ответ можно набирать жадно, используя все x такие, что у обеих последовательностей есть префикс равный x. Количество таких x и будет определять длину ответа, а следовательно, и количество операций.

Мы научились выделять O (n) интересных подотрезков и находить ответ для каждого из них за время O (n + m). Это ещё слишком медленно. Вычислим все частичные суммы в обоих последовательностях и отметим их в битовом массиве. Тогда вычисление количества совпадающих элементов сводится к вычислению скалярного произведения двух битовых последовательностей. Вычислить результат скалярного произведения одной последовательности со всеми суффиксами другой можно с помощью быстрого преобразования Фурье. Итоговая сложность решения: O (cn·log (cn)), где c — ограничение сверху на элементы ai и bi.

Задача E. Компактные строки

Автор задачи и разбора — Михал Форишек. Финалист Яндекс.Алгоритма 2013, автор задач ACM ICPC, IOI.

В этой задаче рассматриваются строки из строчных латинских букв («a»-«z»). Строка называется компактной, если между двумя любыми одинаковыми буквами в этой строке находятся только такие же буквы. Например, строки «yandex», «aacccb», и «eeeee» являются компактными, а строки «aba» и «aazbbzc» — не являются.

Вам задан шаблон, состоящий из строчных латинских букв и знаков вопроса (»?»). Каждый знак вопроса обозначает одну произвольную строчную латинскую букву.nНайдите количество различных компактных строк, которые соответствуют заданному шаблону. Так как ответ может быть очень большим, выведите остаток от деления его на 109 + 7.

Формат ввода. Первая строка входа содержит целое число t — количество тестовых примеров (1 ≤ t ≤ 100). Каждая из последующих t строк задаёт один тестовый пример, представляющий собой шаблон длиной не менее 1 и не более 104 символов включительно. Шаблон может состоять только из строчных латинских букв и знаков вопроса.

Формат вывода. Для каждого тестового примера выведите одно целое число — остаток от деления количества соответствующих ему компактных строк на 109 + 7.

Разбор задачи E

Сначала рассмотрим более простую задачу: дан шаблон, существует ли как минимум одна компактная строка, которая ему соответствует? Такая задача просто решается за линейное время: нужно убрать все знаки вопроса и проверить, является ли полученная строка компактной. Соответственно, первым шагом нашего решения будет такая проверка; если она не проходит, выведем 0.

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

Далее будем использовать следующие обозначения:

• N для обозначения длины данного шаблона (в данной задаче не более 104);
• S для обозначения размера алфавита (в данном случае 26);
• U для обозначения количества букв алфавита, которые не встречаются в данном шаблоне.

Если U=0, то задача решается просто. Для каждого блока последовательных знаков вопроса остаётся неизвестным только то, где заканчивается первая буква и начинается вторая.

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

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

Существует несколько способов эффективно подсчитать количество таких строк. Один из возможных подходов использует довольно стандартный способ: попробуем рекурсивно генерировать все эти строки, добавляя по одной букве за раз, затем заменим генерацию на подсчёт с мемоизацией. В случае, если соответствующие действия будут сделаны корректно, в результате мы получим мемоизированную рекурсивную функцию, которая будет отвечать на любой запрос за время O (NU).

Рекурсивная функция будет принимать следующие аргументы:

1. Количество символов в шаблоне, которые осталось обработать.
2. Количество всё ещё не использованных букв.
3. Тип последнего обработанного символа.

Тип может принимать одно из четырёх значений:

• fixed: последний обработанный символ был буквой, которую мы и поставили в строку, ибо обязаны.
• past: последний обработанный символ был знаком вопроса, и мы решили заменить его последней буквой, которая была обработана.
• future: последний обработанный был знаком вопроса, и мы решили заменить его следующей буквой, которая встретится в шаблоне в будущем (так как наша задача — только подсчёт, то знать, какая именно это буква, нам не обязательно).
• unused: последний обработанный символ был знаком вопроса, и мы решили заменить его буквой, которая до этого не была использована.

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

Кроме того, существует и другой подход, дающий несколько более быстрое решение. Заметим, что после инициализации (проверки на существование решения и замены всех тривиальных блоков одной буквой) мы можем получить не более, чем S+1 блоков последовательных знаков вопроса: один может быть в начале строки, а перед началом любого из остальных блоков должна идти какая-то буква. После инициализации все эти буквы будут попарно различны. Тем самым количество блоков не может превышать количество букв в алфавите более, чем на 1.

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

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

Тем самым мы получаем решение, которое использует O (NU) времени для построения таблицы биномиальных коэффициентов по заданному модулю и отвечает на единичный запрос за время O (SU2).

Задача F. Случайные точки

Автор — Иван Казменко. Выпускник СПбГУ, автор задач чемпионатов СПбГУ и Открытого кубка.

Рассмотрим следующий линейный конгруэнтный генератор псевдослучайных чисел. У генератора есть состояние — целое число s (0 ≤ s < 232). Каждый раз, когда требуется очередное псевдослучайное целое число в промежутке [0, X), генератор выполняет преобразование Snew=(a∙Sold+c)mod232. После этого Snew становится новым состоянием генератора, а результатом объявляется число .

В этой задаче a = 134 775 813 и c = 1 — такие значения используются во встроенном генераторе псевдослучайных чисел в Borland Delphi 7. Этот генератор используется для получения n случайных точек на плоскости, координаты которых — целые числа из промежутка [0, 100 000 000). Рассмотрим два способа генерации точек.

При первом способе (кодовое название RAW) генератор приводится в некоторое начальное состояние s, после чего последовательно генерирует 2n псевдослучайных чисел a1, a2, …, a2n в нужном промежутке. После этого n случайных точек задаются следующими парами координат: (a1, a2), (a3, a4), …, (a2n — 1, a2n).

При втором способе (кодовое название SHUFFLED) начало процесса такое же: генератор приводится в некоторое начальное состояние s, после чего последовательно генерирует 2n псевдослучайных чисел a1, a2, …, a2n в нужном промежутке. Однако затем эти 2n чисел переставляются случайным образом при помощи следующего варианта алгоритма Фишера-Йейтса (псевдокод):

for i = 1,2,…,2∙n:
k = random [0, i) + 1
swap (ai, ak)

Здесь random [0, i) — это псевдослучайное целое число из промежутка [0, i), для генерации которого используется всё тот же генератор, а swap (ai, ak) меняет местами числа ai и ak; если при этом i = k, ничего не происходит. Перед началом выполнения псевдокода генератор находится в том состоянии, в котором он оказался после генерации чисел a1, a2, …, a2n

После того, как числа a1, a2, …, a2 n оказываются переставлены, n случайных точек, как и в первом способе, задаются следующими парами координат: (a1, a2), (a3, a4), …, (a2 n — 1, a2 n).

Задана последовательность из n точек (10 000 ≤ n ≤ 100 000). Известно, что она получена одним из двух способов, описанных выше. При этом неизвестно, какой способ был выбран, а также каким было начальное состояние s. Выясните, какой способ генерации точек использовался.

Формат ввода. В первой строке задано целое число n — количество точек (10 000 ≤ n ≤ 100 000). Следующие nстрок содержат описания точек, по одному на строке. Каждое описание точки состоит из двух целых чисел, разделённых пробелом — её координат x и y (0 ≤ x, y < 100 000 000). Гарантируется, что точки получены одним из двух способов, описанных в условии.

Формат вывода.
Выведите «RAW», если использовался первый способ генерации точек, и «SHUFFLED», если использовался второй способ.

Решение задачи F

Общие наблюдения. Легко показать, что генерируемые случайные числа образуют одну циклическую последовательность из 232 чисел. От начального состояния зависит лишь то, с какого элемента этой циклической последовательности начнётся генерация.

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

Вот простой пример такого свойства. Зафиксируем небольшое число k (например, k = 10). Пусть координаты n точек сгенерированы последовательно. Тогда любая непрерывная подпоследовательность точек длины k также получается последовательной генерацией случайных чисел, начиная с некоторого состояния. А при генерации n точек с перемешиванием координат вероятность того, что какая-то непрерывная подпоследовательность точек длины k получается последовательной генерацией случайных чисел, очень мала.

Решение, проверяющее это свойство, может выглядеть так. Зафиксируем достаточно большое число t (например, t = 106). Сделаем t следующих шагов: выберем случайное начальное состояние и сгенерируем k точек без перемешивания координат. На каждом шаге проверим, что наши k точек встретились как непрерывная подпоследовательность среди заданных нам n точек. Если это случилось хотя бы на одном шаге, ответим, что координаты генерировались без перемешивания. Если же нет, ответим, что перемешивание имело место.

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

На каждом шаге проверку можно произвести за O (k) или 0(klogn), если предварительно построить ассоциативный массив, который каждой заданной точке ставит в соответствие её номер в заданной последовательности за O (1) (хеш-таблица) или 0(logn) (двоичное дерево поиска). Общее время работы решения равно O (n + tk) для хеш-таблицы или o (nlogn+tklogn) для двоичного дерева поиска.

Второе решение. Предположим, что перемешивания не было. Попробуем восстановить, каким было состояние генератора после генерации первой координаты (x1). Мы знаем, что . Значит, s приблизительно равно . Существует всего около 43 значений s, которые позволяют получить такое значение x1. Переберём их все и для каждого сгенерируем дальнейшие 2n — 1 чисел: y1, x2, y2, …, xn, yn. Если для какого-то s получившиеся точки совпали с заданными, очевидно, перемешивания не было. Если же такого s не нашлось — очевидно, перемешивание имело место.

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

© Habrahabr.ru