13. Неубывающий массив
Дан массив из n целых чисел. Требуется за 2n операций "прибавить к одному элементу другой" сделать его неубывающим.
Пусть все числа положительные. Тогда можно ко второму элементу прибавить первый, после этого к третьему прибавить второй и так далее. Таким проходом мы превратим массив в массив префиксных сумм. Он очевидно, будет неубывающим.
Что делать, если есть не положительные числа? Возьмём сначала самый большой по модулю элемент и прибавим его ко всем остальным. Теперь они все одного знака. Если положительного -- то делаем как раньше, если отрицательного -- проходимся с конца.
14. Минимум и максимум
Даны 68 камней. Требуется за 100 операций взвешивания определить самый лёгкий и самый тяжелый
100 = 34 + 33 + 33. Сравним 1 и 2, 3 и 4, ..., 67 и 68. Камни разобьются на 2 группы по 34 камня -- те, которые точно не могут быть максимумами и те, которые точно не могут быть минимумами. Внутри каждой за 33 взвешивания находим минимум / максимум.
15. Сортировка
Можно ли отсортировать n камней за k взвешиваний?
Критерий, когда нельзя: n! > 2^k (log n! > k).
Обоснование: результаты k сравнений позволяют различить не более 2^k разных перестановок, а всего их n!.
Критерия, когда можно, человечество не знает.
(Кроме приведения, непосредственно, алгоритма.)
Если 2^k сильно больше log n!, то, скорее всего, можно (проверяемый тяжелыми вычислениями факт).
Кстати, отсюда вытекает, что мы не можем, например, строить двоичные деревья поиска быстрее, чем за log n! = log 1 + log 2 + ... + log n = O(n log n).
16. Сжатие строки
Дана случайная бинарная строка, про которую известно, что единичек 1/10. Нужно её сжать в 2 раза.
Да, задача весьма слабо относится обычным олимпиадам, но мне просто хотелось, чтобы вы немного почитали про алгоритмы сжатия информации и всё такое, ибо это очень красивая и важная тема.
Есть очень много способов решать её, мне больше всего нравится метод, названный арифметическим кодированием.
Заключается он вот в чём: рассмотрим отрезок [0, 1]. Дальше пройдёмся по символам исходной строки и будем изменять его границы следующим образом:
- если текущий символ 0, то r = l + (r-l)*0.9
- если текущий символ 1, то l = l + (r-l)*0.9
Интерпретация у этих отрезков такая: длина отрезка в точности равна вероятности получить соответствующую ему исходную строку, а сами отрезки строк упорядочены лексикографически.
Когда прошлись по всей строке, передадим самую короткую (в плане числа бит в записи) точку, которая находится внутри отрезка. Нужно потратить не больше бит, чем округленный вверх минус логарифм от длины этого отрезка (докажите сами, это несложно). Понятно, что по этой точке и длине строки, исходная строка однозначно восстанавливается.
Сколько мы бит в среднем потратим на один символ? Пусть мы кодируем очень большой блок из n символов. Там будет примерно 0.1n единичек и 0.9n нулей,
- значит его вероятность будет примерно P = 0.1^(0.1n) * 0.9^(0.9n),
- закодирована она будет за минус логарифм от этого числа L = 0.1n * log 1/0.1 + 0.9n * log 1/0.9,
- в среднем будет H = L/n = 0.1 * log 1/0.1 + 0.9 * log 1/0.9 ~= 0.46 < 0.5. Победа.
У всего этого есть более строгое обоснование без всяких "примерно", но пока просто поверьте, что эта логика работает.
Величина H называется энтропией.Есть очень интересная теория, выходящая за пределы интересов олимпиадника, которая ещё и доказывает, что оптимальнее энтропии нельзя.
Это, повторюсь, далеко не единственный способ. Можно было, например, попробовать сгруппировать биты по, скажем, 16, посчитать вероятность каждой из 2^16 таких групп и запустить на них алгоритм Хаффмана.
17. Попугаи
Нужно передать 64 байт какой-то информации, имея возможность послать 320 сообщений в 1 байт, которые приходят в случайном порядке.
Немного философский вопрос: а что такое передача информации? Это взаимно однозначное сопоставление объектов одного множества какому-то подмножеству другого. В данном случае, первые объекты -- бинарные строки (которые, кстати, проще представить как просто большие числа), вторые -- неупорядоченные наборы попугаев.
Сколько есть первых объектов? Здесь просто, 2^(64*8).
Сколько есть вторых объектов? Тут сложнее. Представим массив длиной 256, заполненный нулями. Когда прилетает попугай с очередным байтом, прибавим единичку в ячейку, номер которой равен этому байту. Понятно, что наборы попугаев для нашей задачи теперь эквивалентны массивам, сумма элементов которых равна 320 (числу попугаев). Сколько их? Вспоминаем шары и перегородки -- нужно распределить 320 шаров по 256 ящикам, т. е. C(320+256-1, 320). Выясняется, что это число больше количества первых объектов. Ура!
Придумаем тогда функцию, генерирующую k-й лексикографический такой массив, и обратно. Если не прогуливали занятие про генерацию комбинаторных объектов, то это не должно быть для вас трудным. Основная сложность конкретно здесь заключается в использовании какой-то формы длинной арифметики.
18. Перестановка
Есть перестановка из 64 элементов. Вы можете спрашивать, какие элементы находятся на заданном множестве позиций. Восстановите перестановку за 6 вопросов.
Спросим про элементы, номера которых имеют вид *****1, ****1*, ***1**, ***1***, *1**** и 1***** (каждый раз спрашиваем про позиции 32 элементов). Пусть мы хотим узнать, какой элемент находится на позиции k. Рассмотрим его бинарную запись. Все её единички дают ограничения на множество элементов, которые могут быть на этой позиции, а нолики -- какие точно не могут быть. Пройдясь по бинарной маске и делая операции пересечения / удаления, мы однозначно восстановим элемент (докажите, это несложно).
Запомните эту идею. Интерактивки, в которых делаются примерно такие запросы, весьма нередки.
19. Достижимость
Дан ориентированный граф без кратных рёбер. Для всех пар вершин u и v определите, можно ли дойти из u в v.
Решение за n^3 / 64: заведем n битсетов для каждой вершины, затем сделаем топологическую сортировку и прйдемся по вершинам в порядке от листьев к корням, делая такие обновления: b[v] |= b[u] для всех ребер (v, u). b[v][u] здесь означает, достижима ли вершина u из v. Рёбер O(n^2), объединение битсетов работает за n/64.
20. Дикий запад
Определить, есть ли в неориентированном графе цикл чётной длины.
Назовём граф без чётных циклов хорошим.
Лемма: циклы в хорошем графе не пересекаются. Пусть два цикла имеют нечётную длину и пересекаются по k рёбрам. Тогда мы можем выкинуть эти рёбра и склеить эти циклы в один. Длина нового цикла будет чётной: пусть длина первого была a+k, второго -- b+k, тогда длина нового цикла будет (a+k + b+k) - 2k = a+b. (a+k + b+k) и 2k чётные, значит и a+b тоже. Противоречие.
Значит, нужно проверить, что в графе не пересекаются циклы, и что каждый цикл имеет нечетную длину. Такие графы хорошо известны и называются кактусами. Проверку можно делать относительно несложными dfs-ами.