Прочитать условия задач OCPC-2019 и отправить на проверку свое решение можно на acm.pp.ua. Регистрация свободная.
A. Ахиллес и черепаха
Поскольку Ахиллес бежит быстрее черепахи, но не должен ее обогнать, нас интересует точка, в которой он ее догонит. Для этого вначале найдем время, за которое Ахиллес догонит черепаху: $t =\frac{ x_t — x_a}{v_a — v_t}$. Теперь найдем координату, в которую в этот момент прибежит Ахиллес (и черепаха тоже): $x = x_a + v_a \cdot t$. Это число и будет ответом.
B. Буковель
Заметим, что расстоянием между двумя вершинами в нашей задаче является упорядоченная пара {количество подъемов, количество спусков}. Значит, сравнивая 2 пути, нужно сравнивать их сначала по первому параметру, затем по второму. Это сравнение уже реализовано в C++ в структуре std::pair<int, int>. Теперь просто построим наш граф, где весом каждого ребра будет пара {1, 0}, если это подъем, и {0, 1}, если это спуск. Запустим на нем алгоритм Дейкстры — он найдет кратчайшее расстояние. Сложность алгоритма $O(n \cdot \log m)$
C. Свидание
Заметим, что период от одного «любит» до следующего занимает ровно $k+1$ лепесток. При этом номера «счастливых» лепестков такие: $1$, $k+2$, $2 \cdot k + 3$… То есть, эти числа дают остаток $1$ по модулю $k+1$. Все, что нужно, проверить, дает ли такой же остаток число $n$.
D. Дивный новый мир
Отсортируем всех студентов по возрастанию оценок. Понятно, что в оптимальном решении, если остались не отчисленными какие-то студенты, то они в этом массиве будут идти подряд. Теперь переберем все возможные диапазоны из ровно $n-k$ студентов — это минимальное количество, которое можно оставить. Пройдемся по нашему массиву «окном» {i, i + n - k - 1}, где $i$ — текущий кандидат на минимальную границу диапазона оценок, а $i + n — k — 1$ — на максимальную. Будем заменять ответ текущим кандидатом, в случае, если новый диапазон не шире имеющегося. Сложность алгоритма $O(n \cdot \log n)$.
E. Энигма
Название задачи намекает, что надо расшифровать текст. И действительно — условие зашифровано. Поскольку все задачи данного контеста начинаются с «Ни для кого не секрет, что студенты ОНУ…», то у вас уже есть ключ. По нему можно понять, что к первому символу слова всегда прибавляется $1$, ко второму — $2$ и т.д. Это дает возможность написать программу и расшифровать условие, в котором сказано, что шифруются только латинские буквы и цифры, причем большие буквы заменяются большими, строчные — строчными, цифры — цифрами, а слова разделяются пробелами, т.е. пока не встретим пробел или конец строки, слово продолжается. Далее пишем простой конечный автомат и обрабатываем ввод посимвольно. Важно не читать ввод по словам, поскольку между двумя соседними словами может быть несколько пробелов и нужно сохранить их все. Сложность алгоритма $O(n)$
F. Fiasco del ACM
Будем обрабатывать отдельно «победные» контракты, отдельно — «ничейно-победные». Для простоты рассмотрим решение только для контрактов первого типа. Пусть у нас есть отрезок из $k$ побед подряд и мы добавляем еще одну победу. Тогда призовые команды увеличатся на $\sum_{i=1}^{k+1}w_i$, где $w_i$ — сумма денег за контракты длины ровно $i$. Действительно, в $k+1$-й ячейке закончатся победные серии длины $1$, $2$,… $k+1$. Таким образом мы можем посчитать для строк всех длин призовые за них. Обозначим такой массив $s$. Если накапливать сумму $\sum_{i=1}^{k}w_i$, а не считать ее каждый раз заново, то все эти вычисления займут $O(g)$ операций.
Теперь пусть у нас есть ячейка, где мы не выиграли. Например, «WWWDWWWWW». Чтобы посчитать сколько денег мы потеряли в этом матче, найдем максимальную длину побед слева и максимальную длину побед справа. Пусть это числа $w_l$ и $w_r$. В нашем примере $w_l=3$, $w_r=5$. Если заменить теперь ничью на победу, то у нас пропадут 2 выигрышных участка длины $w_l$ и $w_r$, зато появится один большой длины $w_l+w_r+1$. Значит, недополученная в матче сумма равна $s[w_l+w_r+1]-s[w_l]-s[w_r]$. Для получения ответа нужно сложить все такие числа для матчей, где мы не победили.
Теперь осталось научиться быстро считать $w_l$ и $w_r$. Научимся для $w_l$, для $w_r$ это делается абсолютно аналогично. Будем накапливать «хвост» слева в переменной $l$. Если текущий символ ‘W’, увеличим переменную на $1$. Иначе — обнулим. Будем заносить результаты в массив. Сложность всего решения $O(g)$.
G. Героиня оптимизации
Заметим, что для $k$ человек будет совершено $k \cdot (k-1)$ нажатий. Чтобы в памяти осталось ровно 0 нажатий, необходимо и достаточно, чтобы $k \cdot (k-1) \equiv 0 \mod n$. Поскольку $gcd(k, k-1) = 1$, из предыдущего тождества можно вывести систему новых:
$k \equiv 0 \mod a$
$k \equiv 1 \mod b$
$a \cdot b = n$
$gcd(a, b) = 1$
Из китайской теоремы об остатках следует, что для каждой такой системы будет существовать ровно одно решение на диапазоне $[0, n-1]$. Осталось посчитать сколько таких систем существует. А их ровно столько, сколько существует пар делителей $a, b: a \cdot b = n, gcd(a, b) = 1$. Поскольку у $a$ и $b$ нет общих простых делителей, это означает, что если какой-то простой делитель $n$ попал в $a$, то и все остальные такие же делители попадут в $a$. Поэтому количество различных значений $a$ равно количеству способов выбрать набор различных простых делителей числа $n$. Это $2^{cnt}$, где $cnt$ — количество различных простых делителей $n$.
Поскольку 0 и 1 всегда являются корнями нашего уравнения, а ответы просят искать с двойки, то уменьшим мощность множества ответов на 2. Ответом будет $\frac {n — 2 — (2^{cnt} — 2)}{n — 2} = \frac {n — 2^{cnt}}{n — 2}$. Чтобы факторизовать число $n$, достаточно $O(\sqrt{n})$ операций, что и является сложностью алгоритма.
H. Heap Search
В псевдокоде поиска реализован обход «корень-левое-правое» с отсечением в корне: если текущее значение меньше искомого, то идти в потомков не следует, потому что они еще меньше. Переупорядочим числа в куче в порядке этого обхода. Тогда если искомого числа $k$ в куче нет, то наш обход посетит каждую вершину с большими значениями, чем $k$ и из них сделает еще по $2$ захода — влево и вправо. По индукции можно показать, что всего заходов будет $2 \cdot g + 1$, где $g$ — количество чисел в куче, больших, чем $k$.
Если же число $k$ в куче есть, то мы будем идти до его первого вхождения по массиву слева направо, заходя только в большие вершины и их непосредственных потомков. Значит, нам нужно для каждого числа быстро находить на префиксе количество чисел, больших, чем оно. Это можно делать с помощью какой-то структуры данных, например, дерева Фенвика. К ответу будем прибавлять $2 \cdot g$, если $k$ — левый потомок своего родителя или $2 \cdot g + 1$, если правый. Сложность алгоритма $O(n + m \cdot \log n)$, где $m$ — размер диапазона, в котором запускается HeapSearch.
I. Игра белко-бобров
Будем анализировать данную игру с помощью обхода в глубину. Назовем проигрышной позицию, в которой текущий игрок проигрывает, а выигрышной — ту, в которой выигрывает. Если мы в тупике, то мы точно проиграли. Если из нашей позиции есть ход в проигрышную (для соперника, который ходит следующим), то мы выиграли. Если же все ходы в выигрышную (для соперника), то мы проиграем за исключением случая, когда у текущей вершины нечетное количество потомков. Действительно, в выигрышную позицию никто ходить не будет, а значит каждый игрок будет перегрызать ребро графа. Если их нечетное количество, то тот, кто начнет грызть первым, тот и закончит последним. Сложность алгоритма $O(n)$.
J. За двумя зайцами
Пусть мы выбрали какой-то набор матчей, которые мы будем играть, и теперь хотим проверить, можно ли распределить очки между всеми соперниками так, чтобы мы стали чемпионами. Эту задачу будем решать потоками с помощью алгоритма Диница.
Сначала построим граф. Из истока кинем ребра пропускной способности 3 во все вершины, соответствующие еще не сыгранным матчам. Пропускная способность 3 будет означать, что в матче распределяются 3 очка в какой-то пропорции. Заметим, что матчей нашей команды среди них не будет, потому что мы уже выбрали все матчи, которые мы выиграем и проиграем. Из каждого матча кинем по ребру пропускной способности 3 в вершины, соответствующие тем командам, которые играют в этом матче. Это означает, что команда может набрать от 0 до 3 очков в каждом матче. Из каждой команды кинем в сток ребро пропускной способности, равной тому числу очков, которое имеет право набрать эта команда так, чтобы не догнать нашу команду. Поскольку мы уже распределили результаты нашей команды, то ее очки известны и очевидно, сколько имеет право набрать каждый соперник. Построив этот граф и пустив по нему поток Диницем, проверим, смогли ли мы распределить $3 \cdot g$ очков, где $g$ — количество еще не сыгранных матчей.
Теперь мы можем перебрать все возможные наборы сыгранных нашей командой матчей и для каждого проверить потоком, можем ли мы победить при таком выборе или нет. Заметим, что структура графа для всех наборов будет идентичной, различаться будут только пропускные способности ребер от команд к стоку. Всего различных наборов не больше, чем $2^{n-1}$.
Далее заметим, что поскольку нас интересует минимальный по количеству набор игр, можем воспользоваться бинарным поиском. Это дает нам целых 2 преимущества:
1) мы будем проверять множества не всех мощностей, а приблизительно половину из них;
2) если для какой-то мощности множества уже есть подходящий ответ, не нужно проверять все остальные, нам достаточно одного положительного исхода;
Распределим все возможные маски из диапазона $[0; 2^{n-1}-1]$ по векторам в зависимости от количества единичных бит и будем для текущего $k$ проверять только маски с $k$ единичными битами.
Теперь заметим еще одну вещь: для фиксированного $k$, если две маски различаются только двумя битами, то графы идентичны, за исключением пропускной способности двух ребер, соответствующих тем командам, с которыми мы играем в первом наборе и не играем во втором (и наоборот). Значит, если мы пихнули поток по графу, соответствующему какой-то маске, а потом перешли к почти такой же маске, мы имеем право не искать поток заново, а чуть поменять пропускные способности (не более чем на 3), пихнуть лишний поток величиной до 3 обычным DFS-ом назад в исток и затем пустить Диница, который всего лишь достроит недостающий поток.
Чтобы перебирать маски в указанном порядке, будем помещать их в векторы не в порядке возрастания, а в порядке построения кодов Грея. Тогда каждый запуск ДФС+Диница будет иметь сложность $O(n^2)$. Итоговая сложность алгоритма $O(2^{n-2} \cdot n^2)$, что укладывается в 4.5 секунды из 10, данных на задачу.
Для отправки комментария необходимо войти на сайт.