Переберём количество строк длины p и q в ответе. Пусть это величины a и b. Если a·p + b·q = n, то посторим ответ, откусив с префикса сначала a раз строки длины p, а затем b раз строки длины q. Если ни одной подходящей пары a, b не нашлось, то ответа не существует. Конечно эту задачу можно решать и за линейное время, но здесь это не требовалось, поскольку ограничение на длину строки было маленьким.
Асимптотическая сложность решения: O(n2).
612B - HDD is Outdated Technology
В условии задачи задана перестановка f. Построим по ней другую перестановку p следующим образом: pfi = i. Таким образом, перестановка p определяет номер сектора по номеру фрагмента. Перестановка p называется обратной к перестановке f и обозначается f - 1. Теперь ответ на задачу равен просто 
.
Асимптотическая сложность решения: O(n).
612C - Replace To Make Regular Bracket Sequence
Заметим, что поскольку мы не можем менять тип скобок, то для существования ответа необходимо, чтобы заданная строка была правильной скобочной последовательностью без учета вида скобок. Если это не так, то ответа не существует. Иначе каждой открывающей скобке соответствует ровно одна закрывающая, и каждой закрывающей — ровно одна открывающаяя. Теперь заметим, что если пара соответствующих друг другу скобок одного вида, то их мы можем не менять. Если же они разного вида, то поменяем вид закрывающей на вид открывающей. Таким образом, мы построим ответ. Легко убедиться, что ответ оптимальный, поскольку задачи для несоответствующих друг другу скобок не связаны друг с другом и могут быть рассмотрены по отдельности.
Единственная техническая тонкость в том как найти соответствующие друг другу скобки. Для этого заведем стек открытых скобок. Теперь будем идти по строке слева направо и если скобка открывающая, то просто добавим ее в стек. Если же она закрывающая, то возникает три случая: 1) стек пуст — значит ответ не существует; 2) вверху стека лежит открывающая скобка того же вида, что и текущая закрывающая; 3) вверху стека скобка вида отличного от текущего. В первом случае ответа не существует, во втором ничего делать не надо, а в третьем ответ нужно увеличить на единицу.
Асимптотическая сложность решения: O(n).
612D - The Union of k-Segments
Для каждого отрезка создадим два события в момент li — открытие отрезка и в момент ri — закрытие отрезка. Отсортируем все события по моменту времени, при равенстве сначала будем обрабатывать события открытия отрезков. Это можно сделать, например, накидав в vector<pair<int, int>> events (пример для языка C++) пары момент времени и тип события ( - 1 для открытия и + 1 для закрытия). Далее это массив можно отсортировать стандартным компаратором.
Теперь будем идти по массиву events и считать баланс отрезков balance, для этого каждый раз нужно просто из баланса вычесть тип события. Теперь если баланс оказался равен k, а до этого был k - 1 значит мы стоим в левом конце отрезка из ответа, запомним этот левый конец (равный моменту текущего события) в переменную left и будем идти дальше. Если баланс оказался равен k - 1, а до этого был равен k значит мы обнаружили конец некоторого отрезка из ответа right. Добавим в ответ отрезок [left, right]. Таким образом, мы получим непересекающийся набор отрезков, содержащий все покрытые точки, в порядке слева направо. Очевидно он и является ответом на задачу.
Асимптотическая сложность решения: O(nlogn).
