Архивы для May, 2008

7-го июня после долгого устранения технических неполадок наконец-то состоится Kazakhstan Contest 2 на сервере КРСУ. Это будет, вроде бы, первый ACM-контест, почти полностью написанный мной. Так что приглашаю всех желающих, вдруг кому-нибудь даже понравится

И спасибо ребятам из КРСУ, в частности Улану Дегенбаеву и Андрею Мохову за то, что уже второй раз согласились хостить предложенный мной контест.

Продолжаю начинание…

Внимание! В комментариях можно прочесть авторский и альтернативные подходы к решению задач.

Задачи, результаты.

Спасибо Андрею Мохову за очередной красивый контест

Задача A. Agreement

Если немного формализовать задачу, то она будет звучать так:

Дано логическое выражение вида (x1 | ~x1) & (x2 | ~x1) & (x2 | x3) & ,.., где xi – это глаголы в исходной задаче. Требуется определить, существует ли такое множество значений xi, при которых данное выражение истинно.

Данная задача известна как 2-SAT. Основная идея решения: построим ориентированный граф, вершинами которого будут xi и ~xi. Пусть в логическом выражении существует дизъюнкция (a | b), тогда в графе должны быть ребра ~a -> b, ~b -> a, что означает “если ~a – истина, то b тоже истина, а если ~b истина, то a – истина”. Ясно, что необходимым условием существования решения является отсутствие в этом графе цикла, в который одновременно входят c и ~c. Другими словами, c и ~c не должны одновременно находиться в одной сильно-связанной компоненте графа. Можно доказать, что это условие является и достаточным. Таким образом, решение задачи сводится к нахождению сильно-связанных компонент графа, что делается обходом в глубину за линейное время.

Задача C. Collect the coins

Попробуем смоделировать последние шаги удачной последовательности перемещений. Пусть всего монет M, а шагов K.

• после K-го шага: одна коробка с M монетами;
• после K-1-го шага: M / 2, M / 2;
• после K-2-го шага: (M / 4, M / 4, M / 2) или (3M / 4 и M / 4);
• …

Становится ясно, что количество монет в любой коробке всегда должно иметь вид pM / q, где q – степень двойки, а p – нечетное.

Вычислим для каждого ai значения pi и qi. Очевидно, что перемещать монеты нужно между такими i и j, что qi = qj. Пусть pi > pj, тогда:

pi -= pj;
pj += pj.

Понятно, что в результате данной операции pi и pj становятся четными, что позволяет сократить их как минимум на 2, не забывая про qi и qj. Повторяя такую операцию, пока возможно, получаем решение задачи. Оценка количества шагов: для каждого значения знаменателя не может быть больше N / 2 пар коробок. Количество различных значений знаменателей – log N. Количество шагов – N log N / 2, что гораздо меньше требуемых 10000.

Задача D. Disconnect the network

В задаче требуется найти минимальный разрез между всеми парами вершин. Можно доказать (если знаете – расскажите как ), что достаточно находить величины разрезов между вершиной 1 и всеми остальными. Величину разреза можно искать простым потоком: так как количество ребер небольшое, данный алгоритм работает достаточно быстро.

Задача E. Efficient sorting

Представим перестановку в виде графа с N вершинами и ребрами i -> a[i]. Можно доказать, что этот граф представляет собой набор циклов. Следовательно, если мы возьмем какое-то a[i] и поставим его на свое место, а с числом, которое стояло на месте a[i] повторим то же самое, то мы пойдем по циклу и в один прекрасный момент закончим последовательность перестановок, обойдя весь цикл. Ясно, что количество перестановок в одном цикле на единицу меньше количества вершин в этом цикле. Таким образом, отняв от количества вершин количество связанных компонент, получим ответ.

Задача F. Full-length mirror

Внимательное рассмотрение чертежа в течение нескольких секунд дает вполне очевидный ответ – половина от высоты Данила.

Задача G. Good fraction

Как всегда, когда не понятно оптимальное решение и ограничения не намного превосходят те, при которых задача решалась бы “в лоб”, попробуем эвристики. Лобовое решение:

• переберем все N от 1 до 10^D, где D – количество цифр после запятой в x;
• для каждого N вычислим соответствующее G;
• если G / N укладывается в интервал [x - 0.5 * 10 ^ (-D + 1), x + 0.5 * 10 ^ (-D + 1)), то ответ найден.

Недостаток данного решения - D может быть до 8, а 10^8 операций с 64-битными целыми это довольно долго.

Теперь оптимизации:

• очевидно, что перебирать можно не до 10^D, а до D / gcd(x, 10^D);
• если потестить значения, близкие к нулю или к единице, то можно заметить, что именно на них программа работает самое большое время. Правильное решение - таблица, например, для первых и последних 50 значений x ;
• вычисление и проверку G надо делать в целых числах, используя как можно меньше операций деления.

Такие нехитрые оптимизации приводят перебор к Accepted.

Задача H. Hungry? Go eat!

Классическое название задачи - задача о двух станках. Решает ее алгоритм Джонсона. Выпишем все C[k] и E[k] в одну последовательность A и будем повторять следующие действия, пока это последовательность не опустеет:

• возьмем минимальное число из A;
• если взятое число исходно было из C, то соответствующее блюдо добавим в очередь Q;
• если взятое число исходно было из E, то соответствующее блюдо добавим в стек S.

Теперь будем заказывать все блюда из Q в соответствующем порядке, а затем из S. Эта последовательность и будет оптимальной.

Вот и прошел очередной срм, который я впервые за последнее время написал более-менее нормально. Ключевым шагом было не поддаться депрессии после Coding Phase, когда я был примерно 15-м в комнате, и написать тест, валящий жадные решения. В результате 6 удачных челленджей и резкий скачок на 1-е место в комнате. Правда радость была скоро уничтожена глупым багом в первой задаче, которую, почему-то никто не решился челленджить (наверное, красный цвет сделал свое дело ). Но после систем теста я опустился всего на 2 места, и таким образом получаю немного денег и некоторую прибавку к рейтингу. Но в целом срм подтвердил мою “неудачливую” натуру – если бы первая не упала, я был бы 3-м в дивизионе