Краткий разбор моих решений Andrey Mokhov Contest #4
7Продолжаю начинание…
Внимание! В комментариях можно прочесть авторский и альтернативные подходы к решению задач.
Спасибо Андрею Мохову за очередной красивый контест 
Задача 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. Эта последовательность и будет оптимальной.
TopCoder SRM 401
0Вот и прошел очередной «Great Ratings Fall SRM». Относительная очевидность первых двух задач, не помешала сильно потормозить на первой и допустить баг во второй… В первой требовалось написать простую трехцикловую динамику. Во второй, составив очевидную систему уравнений, достаточно сложить квадраты первых двух из них, в результате чего получится квадратное уравнение. Дальше оставалось лишь рассмотреть частные случаи.
Результат СРМ в очередной раз подтвердил выражение «все хорошо в меру» – параллельное писание СРМ и просмотр интересного фильма до добра не доведут 
TopCoder SRM 400
0Вот и прошел очередной срм, который я впервые за последнее время написал более-менее нормально. Ключевым шагом было не поддаться депрессии после Coding Phase, когда я был примерно 15-м в комнате, и написать тест, валящий жадные решения. В результате 6 удачных челленджей и резкий скачок на 1-е место в комнате. Правда радость была скоро уничтожена глупым багом в первой задаче, которую, почему-то никто не решился челленджить (наверное, красный цвет сделал свое дело ). Но после систем теста я опустился всего на 2 места, и таким образом получаю немного денег и некоторую прибавку к рейтингу. Но в целом срм подтвердил мою «неудачливую» натуру – если бы первая не упала, я был бы 3-м в дивизионе
Краткий разбор задач KRSU Open Contest 2008
9По просьбам трудящихся постараюсь публиковать короткие разборы задач проходящих контестов.
Спасибо Улану Дегенбаеву и Андрею Мохову за интересный контест.
Problem A. Absolute Equation
Ключевая идея решения: весь интервал от -10^8 до 10^8 можно разбить на подинтервалы, внутри которых каждое из подвыражений уравнения (x, |x| + a, x + b) имеет постоянный знак и не равно нулю (x’ы, при которых какое-то из подвыражений равно 0 будут являться границами этих интервалов). Точки, являющихся границами интервалов это:
- -10^8, 0, 10^8;
- a, -a, при a < 0;
- -b.
Теперь, если взять интервал (l, r), то знак каждого из выражений строго определяется любым x’ом из этого интервала. Получив знак каждого выражения, избавляемся от модуля и решаем получившееся линейное уравнение, не забывая проверить, что ответ входит в нужный интервал.
Есть еще 2 частных случая:
- x’ы, равные границам интервалов надо проверить отдельно;
- при некоторых обстоятельствах интервал может целиком удовлетворять уравнению. Это легко проверить, подставив 2 разных x из этого интервала в уравнение. Если оба подошли, значит подойдет и весь интервал.
Problem B. Box packing
Очевидная интуитивная догадка:
- положим все коробки в приоритетную очередь (приоритет – время прибытия, чем оно более раннее, тем приоритет выше);
- возьмем две коробки с наиболее ранним временем прибытия, удалим их из очереди и упакуем, получив новую коробку с временем прибытия max(t1, t2) + k, которую положим обратно в очередь;
- повторяем пока в очереди не останется одна коробка, время ее прибытия и будет являтся ответом.
Problem C. Check Solution
У нас всего 26 монет. Попробуем каждую из них поочереди сделать тяжелее других и проверим, что выдаст заданный алгоритм.
Problem D. Deficient Memory
У нас мало памяти, но много времени. Посчитаем сначала количество чисел от 0 до 250000 – 1, затем от 250000 до 500000 – 1, от 500000 до 750000 – 1 и от 750000 до 1000000, встречающихся в обоих последовательностях. Это можно сделать, следующим образом:
- генерируем первую последовательность и каждое число (если оно лежит в нужном интервале) отмечаем в битовом массиве;
- генерируем вторую последовательность и если встречается число, отмеченное в битовом массиве, то увеличиваем результат на единицу, а из битового массива снимаем отметку, соответствующую этому числу.
Легко заметить, что для данного решения требуется не более 250000 / 8 ~32K памяти.
Problem E. Extreme point
Очевидно, что сумму расстояний можно минимизировать по каждой в отдельности. Таким образом задача распадается на 3 одинаковые задачи в одномерном пространстве. Для решения одномерного случая можно использовать, например, следующий алгоритм:
- посчитаем сумму расстояний (s) до самой левой точки;
- пойдем по всем координатам от самой левой до самой правой точки, поддерживая количество точек не правее текущей координаты (l). При этом, когда переходим от координаты x к x + 1, то пересчитываем s по следующей формуле: s = s – (n – l) + l. Таким образом для каждой координаты мы будем знать сумму расстояний от нее до всех точек, и попутно выбирая минимум получим ответ.
Короткий разбор задач с KBTU Open 2008
3Задачи KBTU Open 2008 (спасибо Герману Ильину за предоставление электронных вариантов условий).
Задача A. Computer Networks
Условие задачи сводится к нахождению минимального реберного разреза между любыми двумя вершинами в графе. Как известно величина реберного разреза между вершинами s и t численно равна величине максимального потока между этими же вершинами. Простой перебор всех пар вершин и нахождение между каждой парой вершин этого самого потока не уложится по времени. Для решения задачи достаточно заметить (доказать, интуитивно предположить ), что перебирать надо не все пары вершин, а только пары (1, i) (естественно, вместо вершины 1 можно взять любую другую).
Задача B. Contest
Динамика по двум параметрам. Пусть d[i, j] – количество различных «ranklist» для i участников распределенных по j местам (не забываем, что несколько участников могут занимать одно место). Тогда при j > i d[i, j] = 0, а в остальных случаях d[i, j] = (d[i - 1, j] + d[i - 1, j - 1]) * j.
Задача C. Counter Strike
Задача на «идею». Переберем все пары оружия и количество патронов, которые мы можем купить. Пусть a1, a2 – «damage» текущих видов оружия, а b1, b2 – соответствующие количества патронов. Надо сосчитать для всех возможных a1, a2, b1, b2, сколько максимум врагов мы сможем уложить. Теперь «идея» (одна из возможных): возьмем какое-то количество выстрелов одного оружия и найдем, сколько необходимо выстрелов другого оружия в дополнение к ним, чтобы уложить одного врага. Уложим таким образом столько врагов, сколько сможем. Для оставшегося количества патронов рекурсивно повторим процедуру. Вот и все (доказательства не спрашивать ).
Задача D. Fatboy
Задача сводилась к нахождению наибольшей общей подпоследовательности трех последовательностей так. Делается стандартной динамикой по трем параметрам: d[i, j, k] – длина наибольшей общей подпоследовательности префиксов строк длиной i, j, k.
Задача E. Super Heroes
В задаче надо было разделить данный граф на две доли так, чтобы в одной доле между каждой парой вершин было ребро (назовем эту долю A), а во второй – ребер не было вообще (B), или сказать, что такое разделение не возможно. Между вершинами из разных долей ребра могут быть. Ключевая идея – вершина с наибольшей степенью лежит в доле A. На основании ее получаем решение: взять вершину с наибольшей степенью, связанную ребрами со всеми вершинами находящимися в доле A, поместить ее в долю A, удалить ее из исходного графа и повторить операцию с оставшимися вершинами. Как только нельзя будет найти вершину, связанную со всеми из доли A, останавливаемся и проверям, есть ли ребра между оставшимися вершинами (которые относятся к доле B).
Задача G. Points
Известно, что удвоенная площадь треугольника, вершины которого имеют целочисленные координаты – целая. Таким образом надо посчитать, сколько получается треугольников с четной площадью. Если расписать площадь как векторное произведение двух векторов, то можно заметить, что ее четность зависит только от четности координат векторов, которые в свою очередь зависят только от четности координат вершин. Поэтому все вершины можно «сложить» в квадрат (0, 0) – (1, 0) – (1, 1) – (0, 1) (при этом несколько вершин могут «сложиться» в одну), а дальше – тривиальный перебор или формула.
Задача H. Sequence
Динамика по N. Пусть f[i, j] – количество хороших последовательностей длины i, оканчивающихся на j, где j – это 0 или 1. Тогда:
f[i, 0] = f[i - 1, 0] + f[i - 1, 1];
f[i, 1] = f[i - 1, 1] + f[i - 1, 0] – f[i - 2, 1] + f[i - 3, 1].
Опять же, здесь не надо хранить само количество, – достаточно его четности.
Обо всем понемногу…
0Давно уже не писал – то не было времени, то желания, но вот решился наконец.
Республиканскую студенческую олимпиаду наша команда (я и Сергей Склонин) все-таки выиграла. В первом туре я был первым, а Сергей – вторым, во-втором – наоборот. За первое командное место нам дали принтер… один За первое индивидуальное место мне дали бумажку, это подтверждающую. Но в общем все-таки получилось довольно неплохо – олимпиада заставила решить задачу с NEERC, которую в домашних условиях решать было лениво
Также, прошла III-V этапы Республиканской олимпиады школьников по информатике. Задачи, составленные мной, на удивление, оказались не очень простыми, что показали 1-й и, особенно, 2-й тур V этапа, проходившего в Павлодаре. В Павлодаре нас устроили довольно неплохо, хотя с первого взгляда зона отдыха Энергетик походила именно на зону Главный положительный момент поездки – познакомился с ребятами из КБТУ и научился играть в русский бильярд.
Через день после возвращения из Павлодара состоялся Открытый чемпионат КБТУ, на котором мы участвовали экспериментальной командой – я, Сергей и Жомарт Садыков – золотой призер IOI прошлого года. Не оправдав надежды организаторов, мы решили все задачи за 4 часа и получили вторую порцию пиццы А на награждении симпатичные девушки из Алси подарили нам ретро-телефоны и свои визитки.
Ретро-телефон от Алси
Республиканская студенческая олимпиада, I тур
0Практически только что закончился I тур олимпиады в КарГТУ. На нее собралось, как сказали на открытии, 27 команд из 20 ВУЗов Казахстана. Сразу хочется отметить плюсы и минусы:
+ приветливые организаторы/дежурные, симпатичные девушки ;
+ быстрая регистрация;
+ удобное расположение компьютерных классов;
+ без проблем получены призы за проходившую незадолго до этого Дистанционную олимпиаду ;
- места в гостинице не были забронированы организаторами, хотя они зачем-то справлялись, будем ли мы жить в предложенной ими же гостинице;
- не продумано питание участников – в предложенном кафе заказ ждали около часа, а потом двум из нас сказали, что того, что они заказали нет, а все остальное закончилось;
- отсутствие пробного тура или хотя бы его подобия – как следствие, даже обещанный Visual C++ 6.0 не работал и пришлось писать на Delphi ;
- неполные условия задач и неправильный тип задач для олимпиады по программированию;
- ручная проверка задач – результаты обещали к 18.00, но, по слухам, в прошлом году проверка затягивалась до ночи.
Вот, пока все.
Результаты III Международной дистанционной олимпиады по информатике
0Сегодня появились долгожданные результаты. Оказалось, что я, как и некто Коробов Алексей из КарГТУ, стали победителями среди студентов, набрав максимальное количество баллов. Теперь надо бы забрать из Караганды заслуженные 6 тысяч тенге
Определены финалисты TCHS 2008
0Список здесь. Поздравляем Армана Есенаманова (army), ставшего единственным представителем Казахстана.
