Яндекс.Алгоритм 2018: оптимизационный трек и ML-задача от разработчиков Алисы

A. Время в зазеркалье

Ограничение времени 1 секунда
Ограничение памяти 512Mb

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

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

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

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

Формат вывода
Выведите два целых числа $$ и $$ ($$, $$) — реальное значение текущего времени на часах.

Решение:
Рассмотрим движение "прямой" и "отражённой" стрелки. За то время, когда "прямая" стрелка повернётся на некоторый угол, "отражённая" повернётся на тот же угол, но в другую сторону, то есть суммарный угол поворота стрелок равен полному обороту. Для каждой стрелки независимо вычислим её позицию. Для часовой это 12 минус текущая позиция, а для минутной — 60 минус текущая позиция. В обоих случая надо не забыть заменить 12 или 60 на ноль.

B. Фактор палиндромности

Ограничение времени 1 секунда
Ограничение памяти 512Mb

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

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

Формат ввода
В единственной строке входных данных записана одна строка из базы Аркадия — непустая последовательность строчных букв английского алфавита. Длина строки составляет не менее 2 и не превосходит 200000 символов.

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

Решение:
Пусть существует какая-то подстрока, являющаяся палиндромом. Если мы уберём первый и последний символ палиндрома, оставшаяся строка тоже будет палиндромом. Будем повторять процесс до тех пор, пока не останется строка из двух или трёх букв (в зависимости от чётности).

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

C. Разделите их все

Ограничение времени 1 секунда
Ограничение памяти 512Mb

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

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

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

Формат ввода
В первой строке входных данных записано целое число $$ ($$) — количество мишеней. Каждая из последующих $$ строк содержит целое число $$ ($$), обозначающее тип мишени. Если $$, то мишень является кругом и далее следуют три целых числа $$, $$ и $$, определяющие радиус и координаты центра круга соответственно ($$, $$). Если же $$, то мишень является прямоугольником, который затем определяют восемь целых чисел $$ — координаты всех четырёх вершин ($$), перечисленных в порядке обхода по часовой стрелки или против часовой стрелки. Гарантируется, что данные четыре вершины образуют прямоугольник ненулевой площади.

Формат вывода
Если существует прямая, которая поделит каждый из имеющихся кругов и прямоугольников на две части одинаковой площади, выведите “Yes”. В противном случае выведите “No”.

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

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

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

D. Задача для собеседования

Ограничение времени 3 секунды
Ограничение памяти 512Mb

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

Делать нечего, и в преддверии очередного собеседования Алексей придумал новую задачу. Имеется числовая последовательность, на первом шаге состоящая из двух чисел 1. На каждом шаге следующем шаге между каждыми двумя соседними элементами добавляется новый элемент, равный их сумме. После первых нескольких шагов последовательность выглядит следующим образом:
1 1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1

На собеседовании Алексей хочет попросить кандидата написать программу, которая по заданному числу $$ будет определять, сколько раз число $$ будет встречаться в последовательности на $$-м шаге? Алексей ещё не научился решать свою задачу, но слышал, что кандидат, которого он будет сейчас собеседовать, добился высоких результатов в спортивном программировании, поэтому, скорее всего, легко справится с этим вопросом.

Формат ввода
Во входных данных записано единственное число $$ ($$).

Формат вывода
Выведите одно целое число, равное количеству вхождений числа $$ в описанную в условию последовательность на шаге $$.

Решение:
Докажем несколько лемм.

Лемма 1. Числа, оказавшиеся на каком-то шаге соседними, являются взаимно простыми.

Докажем по индукции. База очевидна (1 и 1 взаимно просты). Пусть доказано для $$ шагов. Все числа, выписанные на $$-м шаге, являются суммой
двух соседних на $$-м шаге чисел, то есть суммой двух взаимно простых чисел. Но НОД ($$, $$) = НОД ($$,$$)=1. Лемма доказана.

Лемма 2. Никакая упорядоченная пара соседних чисел $$ не может возникнуть в последовательности более одного раза (ни на одном шаге, ни на разных).

Пусть это не так, тогда отметим номер $$ шага, на котором в первый раз возникло повторение (то есть повторилась пара, существующая на этом или на предыдущем шаге). Пусть пара $$ возникла на $$-м и на $$-м шаге ($$). Но тогда, если $$, то $$ было построено как сумма соседей $$ и $$ (если $$, то $$ было построено как сумма $$ и $$), то есть на $$-м и на $$-м шагах также существовало повторение, что противоречит нашему предположению.
Лемма доказана.

Лемма 3. Любая упорядоченная пара взаимно простых чисел неизбежно будет соседней на некотором шаге.

Пусть мы имеем числа $$, стоящие рядом на некотором шаге и пусть $$ (без ограничения общности). Тогда $$ было получено как сумма $$+$$, то есть на предыдущем
шаге рядом стояли $$ и $$. Если $$, то два шага назад справа от $$ стояло число $$, если $$, то слева от $$ стояло число $$ и так далее. Так как $$ и $$
взаимно просты, то на каком-то шаге этот процесс, по сути являющийся разновидностью алгоритма Евклида, приведёт к тому, что с одной стороны окажется $$, а с другой — некоторое
натуральное число. Но пара $$ или $$ для любого $$ будет соседней последовательности на $$-м шаге. А так как действия восстанавливаются однозначно,
то это значит, что и исходная пара $$ в какой-то момент встретится в качестве соседней.

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

Подсчёт же количества таких чисел является известной задачей и опирается на мультипликативность функции Эйлера: если $$, то взаимно простых с $$
чисел будет $$. Раскладываем $$ на простые множители за время $$.

E. Резервное копирование

Ограничение времени 5 секунд
Ограничение памяти 512Mb

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

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

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

Формат ввода
В первой строке входных данных записано целое число $$ ($$) — количество тестовых примеров.

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

Формат вывода
Для каждого из $$ тестовых примеров выведите одно целое число — максимально возможную продолжительность эксперимента, то есть максимальный номер секунды, на которой Аркадий может отключить компьютер с номером $$.

Решение:
В задаче нам дано корневое дерево, на каждом шагу одна из вершин дерева удаляется. При этом, если корень вершины ещё не был удалён, то его значение увеличивается на 1 (изначально все значения равны 1). Если значение какой-то вершины становится равным $$, то именно она удаляется на следующем шаге. Требуется максимизировать номер шага на котором будет удалена корневая вершина.

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

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

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

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

Итоговая сложность решения $$.

F. Процессоры-лжецы

Ограничение времени 3 секунды
Ограничение памяти 512Mb

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

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

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

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

Формат вывода
Выведите одно целое число — минимальное возможное количество процессоров-лжецов на плате, при котором каждый процессор мог сообщить Евгению, что среди его соседей есть и исправные процессоры и процессоры-лжецы.

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

Посчитаем $$, где $$ меняется от 1 до $$, а $$ и $$ — битовые маски от 0 до $$. Значением динамики будет минимальное количество процессоров-лжецов, которое потребуется, чтобы заполнить первые $$ столбцов так, чтобы среди первых $$ столбца все процессоры вернули ожидаемый результат, а состояние процессоров в последнем и предпоследнем столбце были равны $$ и $$ соответственно. Всего различных состояний $$. Наконец, для вычисления перехода будет перебирать новую маску $$ и пробовать перейти в состояние $$.

Работая с масками с помощью предподсчёта и битовых операций получим результат $$. Работу программы можно значительно ускорить, если предпосчитать все корректные переходы их каждой пары масок $$ (то есть запомнить все подходящие к ним маски $$).

Упражнение: придумайте, как получить решение за время $$.