В конце сентября мы рассказывали, что решили попробовать провести контест, где желающие могут потренироваться в решении задач, максимально приближенных к «боевым». Так участники могут понять, какого формата задания получают разработчики на собеседованиях в Яндексе (этим интересуются очень многие), а самое главное — с чем они сталкиваются, работая над Поиском. Типичная задача на собеседовании — составить алгоритм, доказать его корректность, предложить пути оптимизации. Если человек разбирается в алгоритмах, то он быстро сумеет их реализовывать на любом доступном ему языке.

В Блице можно использовать Java, C++, C# или Python. Кроме того, участие в контесте дает возможность проверить свои знания. Если в итоге вы понимаете, что их стоит подтянуть, — это тоже результат. Кстати, тогда вам может пригодиться специализация на курсере «Алгоритмы и структуры данных», в создании которой Яндекс участвовал.

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

«Игра»

Условие

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

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

Гарантируется, что для любого теста победителя можно будет определить однозначно.

3
1 2 3 

Petya

3
1 4 2 

Vasya

Решение

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

«Сложные числа»

Условие

Обозначим через сумму цифр натурального числа .

Будем говорить, что натуральное число сложное, если не существует такого натурального числа  что

Найдите наименьшее сложное число.

Решение

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

«Турнирная таблица»

Условие

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

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

Linux - Gentoo - 1:0
Gentoo - Windows - 2:1
Linux - Windows - 0:2

+-+--------+-+-+-+-+-+
|1|Gentoo  |X|L|W|3|1|
+-+--------+-+-+-+-+-+
|2|Linux   |W|X|L|3|1|
+-+--------+-+-+-+-+-+
|3|Windows |L|W|X|3|1|
+-+--------+-+-+-+-+-+

Cplusplus - C - 1:0
Cplusplus - Php - 2:0
Java - Php - 1:0
Java - C - 2:2
Java - Perl - 1:1
Java - Haskell - 1:1

+-+----------+-+-+-+-+-+-+-+-+
|1|C         |X|L| |D| | |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|2|Cplusplus |W|X| | | |W|6|1|
+-+----------+-+-+-+-+-+-+-+-+
|3|Haskell   | | |X|D| | |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|4|Java      |D| |D|X|D|W|6|2|
+-+----------+-+-+-+-+-+-+-+-+
|5|Perl      | | | |D|X| |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|6|Php       | |L| |L| |X|0| |
+-+----------+-+-+-+-+-+-+-+-+

Решение

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

Из-за достаточно небольшого объема входных данных можно применять не сложные структуры, а стандартные механизмы любого из доступных языков. Например, при использовании C++ подойдет контейнер std::map. Ключом в контейнере будет название команды, а значением — информация о ней: количество набранных очков, число побед и результаты игр с другими командами. Результаты тоже можно хранить в std::map, где ключ — название оппонента, а значение — результат матча.

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

«Кошельки и монеты»

Условие

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

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

2
2 3
5

Yes

2
2 3
4

No

2
2 3
3

Yes

Решение

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

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

«Хорошая последовательность»

Условие

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

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

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

Гарантируется, что решение существует.

4
1 1 1
2 4 16
3 9 81
4 16 256

1 2 4 3

Решение

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

«Интересное путешествие»

Условие

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

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

Расстояние между двумя городами считается как сумма модулей разности по каждой из координат. Дороги есть между всеми парами городов.

7
0 0
0 2
2 2
0 -2
2 -2
2 -1
2 1
2
1 3

2

4
0 0
1 0
0 1
1 1
2
1 4

1

4
0 0
2 0
0 2
2 2
1
1 4

-1

Решение

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

«Разделение числа»

Условие

Дано число . Разбейте десятичную запись числа на максимальное возможное количество различных чисел.

Использовать числа с незначащими нулями не разрешается.

0

0

101

10-1

102

1-0-2

11

11

Решение

Несмотря на то, что исходное число может быть очень большим, количество способов разбить его на части зависит не от значения, а от количества знаков в числе. В худшем случае число состоит из 18 десятичных знаков (вариант 10¹⁹ мы не рассматриваем — там только один вариант разбиения). Значит, знак «-» мы можем поставить только в 17 различных позициях. В каждой из этих позиций мы можем как поставить знак, так и опустить его. Другими словами, существует всего 2¹⁷ способов выбрать разбиение для самых больших чисел. Это около 10⁵ вариантов. Переберем их все, отсечем те, которые нас не устраивают (то есть при которых получаются одинаковые числа), и выберем вариант, содержащий наибольшее количество частей.

«Максимальный урон»

Условие

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

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

8 2

16

9 3

20

Решение

Если бы не дополнительный запрет на использование групп определенного размера, который в условии назван несчастливым, то произведение было бы максимальным при разбиении исходного числа на группы по 3 юнита. Если общее число юнитов нацело делится на 3 — просто разбиваем их на группы по 3 юнита. Если остаток от деления на 3 равен 1, то отделяем группу из четырех юнитов (если, конечно, изначально у нас больше одного юнита), а в остальные группы определяем по 3 юнита. И наконец, если остаток от деления на 3 равен 2 — отделяем группу из двух юнитов, а в остальные определяем по 3 юнита.

Докажем, что такое разбиение корректно. Попробуем доказать это методом от противоположного. Предположим сначала, что в нашем разбиении есть числа ≥ 5. Но тогда мы можем заменить на два числа: -3 и 3. На общую сумму замена никак не повлияет, а произведение чисел 3 и -3 всегда больше чем при ≥ 5. Так что чисел, превосходящих или равных 5 в нашей последовательности существовать не может. Предположим, что в ней есть число 4, но мы можем заменить его на две двойки, никак не повлияв на значения суммы и произведения, поэтому давайте так и поступим. Далее, в нашей последовательности не может быть больше двух двоек, иначе мы могли бы заменить любые три из них на две тройки. Значение суммы от этого бы не поменялось, а значение произведения увеличилось бы (8 = 2⋅2⋅2 < 3⋅3 = 9). Следовательно, трех или большего числа двоек тоже не может быть. Ну и кроме того, у нас не может быть единиц (только если исходная сумма сама не равна единице). Таким образом, наша результирующая последовательность может состоять только из троек и не более чем двух двоек, что мы и показали выше.

Вернемся к ограничению на несчастливый размер группы. Если он превышает значение 3 — наше решение останется точно таким же. Если он равен 3, то, перебрав маленькие размеры групп вручную, будем разбивать последовательность на группы размером 2. Если изначально число юнитов нечетное, то дополнительно возьмем группу, состоящую из 5 юнитов (поскольку одна группа размера 5 обеспечит большее финальное значение, нежели 2 группы по 2 юнита и одна группа из одного юнита). Если же исключены размеры группы, равные 2, то используем алгоритм деления на группы по 3 юнита. Наконец, если их начальное число не делится на 3 нацело, возьмем в качестве размера дополнительных групп не 2, а 4 юнита.

«Красно-черные деревья»

Условие

Красно-черным деревом называется дерево, у которого все вершины покрашены в красный или черный цвет и есть еще дополнительные свойства:

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

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

• , т. е. корень переходит в корень.
• Если и у вершины есть дети ( и ), то и у вершины есть дети ( и ), при этом или и , или и .
• сохраняет цвет вершин, то есть .

5

1

7

2

6

0

Решение

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

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

Как вычислить значение ? Корнем у него может быть любое число от 1 до . Тогда в левом поддереве будет содержаться вершина, а в правом — вершин. Сколько поддеревьев может получиться в левом поддереве? Если его корень черный, то число поддеревьев равно , а если красный, то . Аналогично для правого поддерева: , если корень поддерева черный, и , если корень красный. Просуммируем числа, полученные для левого и правого поддеревьев: и Получим общее количество поддеревьев, которые могут быть в нашем дереве с корнем в вершине . Поскольку нам нужно вычислить количество деревьев с точностью до изоморфизма, достаточно посчитать ответ для . Если , то прибавим к ответу произведение числа поддеревьев слева и справа: . Если же мы строим оба поддерева из одинакового числа элементов (), то к результату нужно прибавить вариантов.

При вычислении значения давайте действовать тем же способом, но с двумя замечаниями. Во-первых, число черных вершин во втором индексе не изменяется, поскольку наш корень красный. А во-вторых, раз у красного корня не может быть красных потомков, то слева и справа у нас могут быть только деревья с черными корнями. Следовательно, если мы выбрали число в качестве нашего красного корня, то количество деревьев слева равно , а количество деревьев справа — . Остальные вычисления аналогичны первому случаю.

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

«Все кроме одной»

Условие

Даны перестановок из элементов, каждая из которых принадлежит к одному из типов.

Посчитайте позицию первого элемента, если последовательно применить эти перестановок, убрав одну из них.

3 2
1 3 2
2 3 1
3
1 2 1

3
1
2

2 2
1 2
2 1
3
1 2 1

2
1
2

1 1
1
1
1

1

Решение

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

«Вложенные прямоугольники»

Условие

На клетчатой плоскости отмечено клеток.

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

Определите, через сколько шагов неокрашенных клеток не останется.

1
-1 -1

1

3
-1 -1
0 0
1 1

2

5
0 1
1 0
1 1
2 1
3 2

2

Решение

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

«Игра с числами»

Условие

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

Через сколько операций числа станут одинаковыми?

2
1 1

0

3
9 6 3

3

6
1000000000 1000000000 1000000000 1000000000 1000000000 1

4999999995

Решение

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

Автор: nkmakarov

Источник