Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных).
Сегодня я принял виртуальное участие в Codeforces Round #812 (Div. 2)
Первая задача
Решение этой задачи быстро пришло мне в голову, здесь стоит использовать просто жадные алгоритмы.
Если движение идёт только вдоль одной оси, то максимальная длина будет |Xmax| * 2. А если движение идёт вдоль обеих осей, то мы просто сначала идём всё забрать по оси X, а потом по оси Y. Время выполнения O(n).
Задачу я сдал на 2 минуте на языке программирования Python.
Вторая задача
На этом моменте мне пришлось оторваться от ноутбука, из-за чего я потерял минут 10. Поэтому задачу сдал только на 20 минуте.
Массив будет оптимальный если будет представлять из себя так называемую "гору". Что это значит?
Это значит, что в левой части массива элементы у нас не будут убывать, а в правой не будут возрастать.
Объяснение достаточно простое: если у нас массив будет представлять из себя гору, то все ненулевые числа всегда будут лежать только на одном промежутке. Время выполнения O(n).
Задачу я сдал на 20 минуте на языке программирования C++.
Третья задача
Для решения этой задачи нам нужна математика, а именно теория чисел. Сам алгоритм получился рекурсивный.
Первое - не бывает таких ситуаций, когда данной перестановки не существует. В ходе соревнования я придумал доказательство, но в разборе задач приведена его более простая версия.
Второе - нашим рекурсивным алгоритмом мы перебираем все числа, формируя "хорошую" перестановку. Время выполнения O(n).
Задачу я сдал на 39 минуте на языке программирования C++.
Четвёртая задача
Четвёртая задача была интерактивной. Мне она показалась очень простой и была про олимпийскую турнирную систему. Я, в ходе увлечения футболом, хорошо познакомился с ней.
Я решал задачу методом "разделяй и властвуй".
Базовая ситуация: четвёрка (предположим первый играл со вторым, а третий с четвёртый, победители в каждой паре играли друг с другом).
Мы можем определить победителя в четвёрке за два действия.
Сначала я сравнивал количество побед у первого и четвёртого.
- Если количество их побед одинаково, то победитель четвёрки либо второй, либо третий.
- Если побед у первого больше, то победитель либо первый, либо третий.
- Если побед больше у четвёртого, то победитель либо второй, либо четвёртый.
А после мы сравниваем количество побед у потенциальных победителей четвёрки. У кого больше побед, тот и победитель четвёрки.
Вот и всё. И после мы рассматриваем по два тура, пока количество участников >= 4. Как только их меньше, то их осталось либо 2, либо 1. Если два, то мы просто сравниваем количество побед у двух оставшихся номинантов и выводим номер того, у кого больше. Если один, то просто выводим его номер.
Решение я сдал через 1 час 14 минут после начала соревнования. Язык программирования - C++.
Пятая задача
У каждой клетки есть координаты (x, y). Если x != y, то повернуть клетку мы можем двумя способами: либо k = x, либо k = y, причём всё тоже самое аналогично для клетки (y, x) (поэтому в своём решении я переодически буду рассматривать только половину нашего поля). Для каждой клетки подсчитаем потенциальную выгоду с её поворотов. Если мы сделаем и k = x, и k = y, то с клетками (x, y) и (y, x) ничего не произойдёт в итоге.
Каждое k у нас может быть либо использовано, либо не использовано.
Дальше нам нужно построить систему непересекающихся множеств, с которой я знаком достаточно плохо. Эта задача показала пробелы в моих знаниях на эту тему, т. к. в ходе решения этой задачи я гуглил про DSU (расшифровывается как Disjoint Set Union. Просто в Wikipedia встречается ещё и такая расшифровка, как Dynamic Software Updating, которая не относится к множествам).
Затем мы просто смотрим, какие k нам выгодно применить, а какие - нет. И применяем. Время выполнения O(n2).
Решение я сдал на 1 час 39 минут на языке программирования C++.
Вывод
Как я и сказал в описании пятой задачи, мне бы подтянуть DSU. Это не стоит в большом приоритете, так как эта вещь редко встречается при решении задач. Я буду продолжать делать акцент на повторении побитовых операций, о чём я говорил в прошлой статье.