Задача A. Сон Студента.
В русской версии условия фразу "между любыми двумя пальцами девочки есть палец мальчика" нужно было читать как "между любыми двумя соседними пальцами девочки есть палец мальчика".
Если мальчик пойдёт слева от девочки, то он возьмёт своей правой рукой её левую руку, а оставшиеся руки (левая мальчика и правая девочки) окажутся незадействованными. Если наоборот, мальчик пойдёт справа, то он возьмёт своей левой рукой правую руку девочки. Это написано в условии. Осталось проверить, "совместимы" ли руки для прогулки хотя бы в одном из этих случаев.
Проверить это очень просто: пусть у мальчика B, а у девочки G пальцев, тогда:
- Если B < G, то им будет удобно, только если B = G - 1; это паттерн GBGBGBG...GBGBG. В этом паттерне нельзя добавить ни один палец девочки так, чтобы не нарушить требования условия.
- Если B > G, то наихудшая ситуация - это паттерн BBGBBGBB...BBGBB. Отсюда заметим, что должно выполняться 2G + 2 > = B для возможности прогулки вдвоём.
- Чтобы не затуманивать логику первых двух случаев, третьим случаем вынесем B = G, но тут всё тривиально: очевидно, что взяться за руки они могут.
Задача B. Тындекс.Бром.
Обозначим за p суммарную длину всех потенциальных адресов c. В этой задаче ограничения были выбраны таким образом, чтобы очевидное решение с асимптотикой O(p· k) не проходило. Ускорять будем следующим образом: для каждой буквы из введённой пользователем строки s сохраним отдельно все позиции букв 'a', 'b', ..., 'z' в отсортированном порядке. Обладая этой информацией, можно искать для текущего символа потенциального адреса ci ближайший из s за логарифмическое время бинарным поиском. Таким образом, получается асимптотика O(p · logk), которая прекрасно проходит по времени. Важно было обратить внимание на ограничения и учесть, что длина потенциального адреса может быть больше, чем 105, а ответ не всегда помещается в 32-битный тип.
Задача C. Инквизиция.
Заметим, что, согласно ограничениям, все треугольники лежат строго внутри квадрата. Это упрощает задачу - не нужно рассматривать дополнительно случаи касания границ шкуры.
Сохраним все отрезки каждого треугольника и все попарно пересечём. После этой операции на каждом отрезке может остаться много точек - результаты пересечения с другими отрезками. Рассмотрим каждый подотрезок этого отрезка такой, который не содержит внутри себя других точек. Этот подотрезок либо целиком лежит на границе пятна, либо целиком лежит внутри пятна.
Чтобы проверить этот факт, можно взять середину подотрезка и проверить её на принадлежность исходным треугольникам. Если эта точка - середина подотрезка - лежит строго внутри некоторого пятна, то и весь отрезок будет лежать внутри, и прибавлять его длину к ответу не нужно. В противном случае, добавим эту длину к ответу и, после обработки всех отрезков таким образом, выведем накопившийся ответ.
Если вы работаете с целыми числами, то учтите, что с заданными ограничениями до 105 вычисление, например, векторного произведения, может превысить 32-битный тип.
Если вы работаете с вещественными числами, то используйте максимально большой тип данных (long double в c++, extended в паскале).
Задача D. Дом для червя.
В этой задаче требуется найти следующий лексикографически эйлеров цикл, заданный из некоторой точки - входа - или сказать, что такого пути не существует. Будем решать эту задачу с конца.
Повторим маршрут Арни. Теперь будем откатываться назад по коридорам, которые он прогрыз, и добавлять рёбра к пустому графу (графу без рёбер). Пусть мы откатили на некотором шаге ребро, которое шло из комнаты x в комнату y. Проверим, существует ли вершина z такая, что есть ребро из x в z и номер вершины z больше номера вершины y. Кроме того, нужно проверить, что ребро (x; z) не является мостом - иначе мы разобьём компоненту связности на несколько и не сможем прогрызть все оставшиеся коридоры.
No solution получается тогда, когда ни на каком шаге нельзя найти требуемую вершину z.
Но когда такое ребро (x; z) оказалось найдено, то мы пройдём по нему и после этого будем искать лексикографически наименьший эйлеров путь. Для этого из каждой текущей вершины будем пытаться идти в вершину с минимально возможным номером. Пойти в вершину с минимально возможным номером можно только тогда, когда ребро, соединяющее эти вершины, не является мостом. Разумеется, нужно выбрасывать недостижимые вершины из графа и не считать их за отдельные компоненты, и не нужно выбрасывать начальную вершину, из которой Арни начал свой путь, иначе есть риск в неё уже не вернуться.
Проверку на то, является ли ребро мостом, можно делать поиском в глубину за O(E). Соответственно, суммарная сложность алгоритма O(N· E2).
Задача E. Вселенское Зло
Автор этой задачи - Василий Вадимов, ННГУ. Выкладываю его собственный разбор этой задачи и благодарю за помощь в проведении раунда.
В этой задаче требовалось найти максимальный поток в сети со структурой в виде цилиндра. Предполагалось динамическое решение за O(mn2n). Известно, что максимальный поток в сети равен величине минимального разреза. Причем все истоки должны принадлежать одной доле разреза, а все стоки --- другой. Тогда будем перебирать вершины слева направо, сверху вниз и добавлять в ту или иную долю разреза, по ходу пересчитывая ответ. Тривиальное решение имеет асимптотику O(2mn) и, очевидно, не укладывается по времени.
Но можно заметить, что то число, которое мы добавим ответу при добавлении новой вершины в какую-либо долю разреза, зависит только от того, к каким долям принадлежат вершины в предыдущем столбце и в том, которому принадлежит добавляемая вершина. Поэтому можно считать такую динамику: какой минимальный разрез можно получить, добавив i столбцов и в последнем столбце маска принадлежности вершин к долям разреза mask. Тогда имеется всего 2n переходов, т.к. различных состояний i - 1-го столбца 2n. Так решение оптимизируется до O(mn22n).
Но и это решение можно улучшить, если динамику считать по изломанному профилю. Будем искать минимальный разрез, если мы добавили i - 1 столбцов полностью и добавили j вершин из i-го столбца и маска принадлежности вершин, у которых соседи справа еще не добавлены, mask. Тогда добавляем j-ю вершину, определяем в какую долю ее поместим, считаем, насколько увеличится величина разреза и делаем переход. Итого mn2n состояний, O(1) переходов из каждого состояния и сложность алгоритма O(mn2n).
Поздравляем участников rng_58 и Ra16bit, решивших эту задачу во время контеста!
Выражаю благодарность ребятам из ННГУ (Владиславу Епифанову, Алексею Шмелёву), которые писали альтернативные решения и задавали вопросы по условиям. Спасибо вам!
возможно, возникли какие-нибудь проблемы с тестированием? я обязательно поинтересуюсь у администрации CFНапример, в этой задаче такое возможно.
Вообще-то плохо они были подобраны... Среди решений можно найти успешные решения без бинарного поиска, а с простым перебором от меньшего к большему - и они отрабатывали за 1,5 с. Причем даже на Java, например №308057.
Вообще-то плохо они были подобраны... Среди решений можно найти успешные решения без бинарного поиска, а с простым перебором от меньшего к большему - и они отрабатывали за 1,5 с. Причем даже на Java, например №308057.
Maybe few cases like
1 1
a
aa......a
where there are around 2*MAXN a's in the second line.(Actually this was a case that i were hacked with during the contest,but it failed due to a runtime error and not TLE).
Another tricky case where people tricked their greedy to work incase we already dont have minimum |j-i| = 0, could be
1 1
a....ab.....b
b....ba.....a
where the a's and b's = MAXN/2
MAXN = 99999 everywhere.
O(p*k) solutions could use the above tests to understand why according to the problem setter were expected to TLE and might have got lucky on the judge.
Hope this helps.Appreciate any comments.
If you make a queue to find When you find closest position,it will be O(P) :D
My Solution cost least time.
"номер вершины z больше номера вершины y" из разбора Dне совсем понятно, что значит номер, и для чего нужно это сравнение?
Просьба к Alex_KPR пояснить
все, кажется понял... вопросов нет, разбор достаточно подробен