Архивы за Апрель, 2008
Краткий разбор задач 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 часа и получили вторую порцию пиццы А на награждении симпатичные девушки из Алси подарили нам ретро-телефоны и свои визитки.
Ретро-телефон от Алси
