Олимпиады

Пролог. Написал я как-то вечерком очередной SRM и подумал, а почему же так мало народу с Казахстана там участвует? Одна из причин – неведенье. С ней разберемся попозже. Ну а сейчас вторая…

Среди многих программистов (и не только) бытует такое мнение, что соревнования по программированию – совершенно никчемная трата времени. Почему же в то же время они с удовольствием занимаются каким-либо видом спорта или хотя бы делают зарядку по утрам (что не является ни чем иным, как бессмысленным передвижением белковой массы по некоторой иногда определенной, иногда хаотичной траектории)?

Да, правильно, во-первых, для большинства занятие спортом – это, прежде всего, способ поддерживать свое тело в форме. Во-вторых (хотя не все себе в этом признаются), часто занятия спортом носят состязательный характер, начиная от очевидных (футбол, бег), заканчивая не вполне очевидными (фитнес?), а стремление быть лучше хоть в чем-то присутствует почти у каждого человека.

Но ведь оба этих момента присутствуют и в соревнованиях по программированию! Ведь участие в олимпиаде или подготовка к ней независимо от результатов позволяет поддерживать в форме то, что никаким спортом не получится, – мышление. Еще Ломоносов говорил: «Математику затем учить следует, что она ум в порядок приводит», а программирование (или информатику, если угодно) можно назвать близким родственником математики. Ну а про состязательный момент даже рассказывать не стоит – достаточно разок поучаствовать в TopCoder SRM и все станет ясно

Даже руководители таких крупных компаний и организаций как Google, IBM, NSA, Yandex понимают, что программист, добившийся некоторых успехов на олимпиадах, в большинстве случаев будет ценным сотрудником. Мало того, что они спонсируют эти мероприятия, так еще ходили слухи, что в одну из крупных фирм без собеседования принимают тех, у кого рейтинг на TopCoder выше определенного значения.

Кроме таких очевидно-прагматичных причин, существует еще как минимум одна – это знакомство и общение с лучшими в своей области специалистами. Где еще можно обсудить свои идеи или баги с 20 заинтересованными в этом людьми из разных стран от Китая до ЮАР, кроме как в комнате арены после SRM’а ?

Итак, просуммируем вышесказанное. Причины заниматься спортивным программированием:

1. здоровый сон во время контеста;
2. развитие алгоритмического и других видов мышления;
3. соревновательность;
4. расширение знаний алгоритмов, структур данных, приемов и т.д.;
5. знакомство с интересными людьми.

И, наконец, даже если вам не нравится писать код, если вы проектировщик, тестер или дизайнер, существуют соревнования по проектированию, разработке, тестированию и графическому дизайну.

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

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-м в дивизионе