Всем привет!

Я надеюсь, никто не забыл, что каждый год перед ICPC World Finals проводится небольшое соревнование ICPC Challenge. Разумеется, этот год не будет исключением. Если вдруг кто-то не знает об этом, то ICPC Challenge — это дополнительный двухнедельный контест по программированию искусственного интеллекта в какой-нибудь игре для финалистов чемпионата мира по программированию ACM-ICPC. Победитель определяется по системе double-elimination tournament, и будет объявлен на одном из мероприятий Финала.

ICPC Challenge 2013 начался несколько дней назад (точнее 3 июня), и сейчас я хочу торжественно объявить, что он был подготовлен небольшой командой из Baylor University, North Carolina State University и Saratov State University, который я представляю! Мы приготовили для вас новое задание, которое носит название CodeRunner.

Немного об игре

Задание на 2013 ICPC Challenge, CodeRunner, представляет собой игру на прямоугольном поле, которое выглядит как на картинке ниже. Красный и синий игроки перемещаются по полю, собирают золото, убегают от врагов, которые двигаются по полю. Каждый игрок может перемещаться вбок, карабкаться вверх и спускаться вниз по лестницам, а кроме того разбивать кирпичи, которые находятся на игровом поле. Кирпичи могу восстанавливаться через некоторое время после разрушения.

Приятная новость

Но самая главная новость заключается в том, что в этом году в соревновании могут участвовать все желающие! Параллельно с основным ICPC Challenge для финалистов чемпионата мира, мы запускаем новое соревнование Open ICPC Challenge. Каждый может принять в нем участие и сразиться против лучших команд по программированию в игре CodeRunner!

Вы можете найти больше информации тут и тут.

Мы будем рады видеть каждого из вас :)

Удачи!

279A - Точка на спирали

Из-за небольших ограничений в данной задаче можно было просто промоделировать шаги коня. Удобнее всего это делать, храня текущее направление движения и счетчик со значением, сколько шагов в эту сторону осталось. Заметим, что конь движется по спирали по следующему шаблону: 1 шаг вперед, поворот, 1 шаг вперед, поворот, 2 шага, поворот, 2 шага, поворот, 3 шага, поворот, 3 шага, поворот, 4 шага и так далее.

279B - Книги

При решении этой задачи проще всего было воспользоваться методом двух указателей: левый указатель означает начало отрезка, правый — конец. При передвижении левого указателя на единицу вправо, правый надо двигать до тех пор, пока сумма a_i внутри отрезка меньше или равна t. Так мы сможем для каждого левого конца найти максимально удаленный правый, а ответ на задачу — это максимальная длина из этих отрезков.

279C - Лесенка

Давайте перед выполнением запросов выпишем в массив down отдельно все позиции i, для которых a_i > a_i + 1, и в массив up такие позиции i, такие что a_i < a_i + 1.

Теперь заметим важный факт для решения: отрезок [l, r] является лесенкой тогда, когда все позиции i, где a_i < a_i + 1 левее всех позиций j, в которых a_j > a_j + 1 (l ≤ i, j < r).

Для того, чтобы проверить это условие, давайте воспользуемся массивами up и down, в них с помощью бинарного поиска можно надо найти наибольший индекс i в отрезке, где происходит возрастание, и наименьший индекс j в отрезке, где происходит убывание, и если i < j, то отрезок — это лесенка. Отдельно необходимо рассмотреть случаи, когда числа в отрезке образуют невозрастающую или неубывающую последовательность.

279D - Минимальное количество переменных

Давайте решать задачу методом динамического программирования по бинарной маске. Пусть текущее состояние — это mask. Через count(mask) обозначим количество единичных битов в маске, а через b₁, b₂, ..., b_count(mask) их индексы (здесь и далее будем использовать 0-нумерацию).

Наше состояние означает, что в данный момент у нас имеется count(mask) переменных, которые равны a_b1, a_b2, ..., a_bcount(mask). Будем считать, что дойдя до такого состояния, мы уже сумели произвести count(mask) операций, а значит, сейчас нам надо получить x = a_{bcount(mask) + 1}.

Если это число x не представимо в виде x = b_i + b_j, то тогда точно следующее значение мы получить не можем, и это состояние тупиковое, а иначе даже неважно какие именно значения i, j мы возьмем, главное — убедиться, что такие существуют.

Итак, мы получаем число x на текущей операции. Теперь важно понять, куда мы можем его записать: а именно мы либо записываем в какую-либо из уже использованных переменных (старое значение стирается), либо в новую переменную (это будет стоить нам 1).

В терминах масок первая операция выглядит как выкидывание одного из битов b_k, и добавление нового бита, а вторая — просто добавление нового бита.

Начальное состояние в нашей динамике — это mask = 1, конечное — любая маска, в которой есть единичный бит на позиции n - 1 (в 0-нумерации).

При аккуратной реализации такое решение будет работать за O(2ⁿ·n). В частности, следующий хитрый прием поможет добиться этого: когда нам требуется проверить, что в маске есть такие два бита b_i и b_j, что a_count(mask) = a_bi + a_bj, то будем использовать предподсчитанный массив diff[q][p], в котором будет записан индекс такого элемента массива a, который равен разности a_q–a_p.

Это позволит нам при проверке перебирать лишь значение b_i.

279E - Красивая декомпозиция

Будет опубликовано чуть позже…

257A - Sockets

Очевидно, что выгоднее использовать сетевые фильтры с наибольшим количеством розеток на них. Поэтому сначала отсортируем их по убыванию этой величины. Теперь переберем ответ, то есть, сколько фильтров мы будем использовать, пусть это значение равно p, а фильтры имеют a₁, a₂, ..., a_p розеток. Очевидно, что если соединить эти фильтры, то итого будет доступно k - p + a₁ + a₂ + ... + a_p розеток. Это значение надо сравнить с m и выбрать минимальное подходящее p. Если ни одно значение p не подходит, то следует вывести  - 1.

257B - Playing Cubes

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

Единственное, что может изменить Петя в игре – это цвет первого кубика, и он его поставит так, чтобы его счет был как можно больше.

257C - View Angle

Сначала давайте избавимся от координат точек, а именно, заменим все точки лучами от (0, 0) до каждой из точек.

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

Отдельный случай — когда все точки лежат на одном луче, в этом случае ответ равен 0.

257D - Sum

У нас есть последовательность переменных a₁, a₂, …, a_n. Возьмем две переменные с максимальными значениеми (допустим, i и i + 1), удалим их и вставим в последовательность новую переменную x = a_i + 1 - a_i так, чтобы сохранилось свойство неубывания последовательности. Так будем делать до тех пор, пока не останется единственное число s, которое и будет искомой суммой. Очевидно, что если мы будем разворачивать последовательность замен с учетом знаков, то в итоге узнаем, какой знак стоит у каждой из начальных переменных так, чтобы их сумма была равна s.

Теперь осталось понять, почему число s подходит под ограничения 0 ≤ s ≤ a₁. Очевидно, что оно не может быть отрицательным, так как при всех заменах мы из большего числа вычитаем меньшее. Также несложно понять, что при всех заменах минимальное число в последовательности не может увеличиваться, значит, оно до последней замены будет максимум a₁. Аналогично, второе число в последовательности также не может перед последним шагом быть больше a₂ и так далее. Несложно понять, что при последней замене мы получим s ≤ a₂ - a1 ≤ a₁.

257E - Greedy Elevator

Эта задача решается классическим методом – событиями во времени. Событиями являются: «человек встал в очередь к лифту», «человек вошел в лифт», «человек вышел из лифта».

Будем поддерживать множество будущих событий, текущее время T и текущее положение лифта x.

В каждый момент времени будем выполнять следующие действия:

1. если есть люди, которые в текущее время T пришли к лифту, то поставим их в очередь на их стартовом этаже;
2. если на текущем этаже есть люди, то посадим их в лифт, таким образом очередь на этом этаже опустеет;
3. если в лифте есть люди, которые должны выйти на текущем этаже, то высадим их и запомним для них ответ – текущее время T;
4. найдем количество людей, которые ждут выше этажа x или которые едут выше, а также найдем количество людей, которые ждут ниже этажа x или едут ниже, и согласно условию выберем направление движения.

Однако если мы на каждой итерации будем увеличивать текущее время T лишь на единицу, то решение будет работать слишком долго. Надо научиться переходить сразу к следующему моменту времени, когда появится какое-либо новое событие, и лифт передвигать сразу на несколько этажей вверх или вниз. Очевидно, что между событиями направление движения лифта не меняется.

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

Это можно сделать с помощью структуры «множество» с операциями «найти следующее число в множестве после данного» и «найти предыдущее число в множестве перед данным». Это умеет стандартные структуры set в С++ или TreeSet в Java.

Также для действия номер 4 нам понадобятся две структуры данных, которые умеют находить сумму чисел на определенном отрезке в массиве, для этого можно использовать, например, деревья отрезков или деревья Фенвика. Одна из структур хранит, сколько людей ждут лифта на каждом из этажей, а вторая – сколько людей в лифте хочет выйти на каждом из этажей. В принципе, эти две структуры можно объединить в одну.

Таким образом, для каждого из людей мы будем обрабатывать ровно по три события, и итоговое время решения будет равно O(n·log(n)).

Всем привет!

Через несколько часов начнется Codeforces Round #159 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Иван Фефер (Fefer_Ivan), Павел Холкин (HolkinPV), Виталий Аксенов (Aksenov239) и Геральд Агапов (Gerald). Кроме того мы выражаем благодарность Марии Беловой (Delinur) и Михаилу Мирзаянову (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.

UPD: разбор на русском языке доступен тут.

UPD: контест закончен, поздравляем победителей!

1.GreatEagle

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

242A - Игра в монетку

Эта задача решалась очень просто: достаточно было двумя вложенными циклами по i и по j (a ≤ i ≤ x, b ≤ j ≤ y) перебрать всевозможные исходы игры и выделить среди них те, в которых i > j. Такие пары и составляют ответ. Время – O(x·y).

242B - Большой отрезок

Для начала заметим, что ответ всегда однозначный, потому что если существует отрезок номер i, который покрывает отрезок номер j, то отрезок j никак не может покрывать отрезок i. Единственный случай, когда такое возможно, — это когда отрезки i и j совпадают, однако по условию в наборе нет одинаковых отрезков. Заметим, что ответ должен покрывать самую левую из всех точек всех отрезков, и аналогично, самую правую из всех точек. Таким образом, надо найти эти точки линейным проходом: L = min(l_i), R = max(r_i), и найти номер отрезка [L, R], либо вывести  - 1, если его нет в заданном множестве. Время --– O(n).

242C - Путь короля

Самое главное для решения этой задачи – заметить, что суммарная длина всех отрезков не превосходит 10⁵. Используя этой свойство, мы можем занумеровать все разрешенные клеточки, и найти кратчайший путь с помощью обхода в ширину. Проще всего занумеровать клеточки используя ассоциативный массив (например, map в C++). Время –-- O(n·log(n)).

242D - Спор

Обозначим через b_i текущее число на счетчике номер i. Решать задачу будем следующим образом: возьмем любой счетчик i, такой, что b_i = a_i, и нажмем на соответствующую кнопку. Алгоритм прекратим тогда, когда такого i не найдется. Поймем, что этот алгоритм на самом деле решает задачу. Нам необходимо объяснить несколько условий:

1. Почему после конца алгоритма состояние будет выигрышным для Валеры? Потому что не будет существовать такого i, в котором b_i = a_i, а иначе мы бы нажали на кнопку.

2. Почему алгоритм не будет нажимать одну и ту же кнопку дважды? Потому что мы нажимаем кнопку i, только если b_i = a_i, и сразу же, как мы нажмем, число b_i увеличится, и равенство больше никогда не выполнится.

3. Почему этот алгоритм можно реализовать за приемлемое время? Потому что из условия 2 следует, что алгоритм сделает не более n нажатий, которые суммарно приведут не более чем к n + 2·m прибавлениям к числам. Для того, чтобы быстро находить те числа, в которых b_i = a_i, можно воспользоваться очередью: каждый раз, когда мы изменили число b_i, и оно стало равным a_i, то закидывать в очередь i. Несложно понять, что одно и то же число не может быть закинуто в очередь дважды.

Из алгоритма следует, что ответ всегда существует, а значить выводить  - 1 никогда не нужно было. Время – O(n + m).

242E - XOR на отрезке

Запишем числа a₁, a₂, ..., a_n в виде таблицы n × 20 где b_i, j равно j-ому биту в i-ом числе. Тогда сумма на отрезке [l, r] равно что равно , то есть мы можем перебрать номер бита j, найти в скольких числах этот бит равен 1, и прибавить к ответу (количество)·2^j.

Для эффективной реализации воспользуемся 20-ю деревьями отрезков по сумме, каждый из которых будет соответствовать одному из битов (то есть одному из столбцов таблицы b_i, j). Тогда операции можно переформулировать:

1. подсчет суммы эквивалентен нахождению количества единиц с l по r.

2. операция "xor" эквивалентна изменению всех бит c l по r на противоположные (то есть 0 меняется на 1, а 1 – на 0).

Первая операция выполняется для всех номеров бит, вторая – только для тех номеров бит, в которых у числа из входных данных стоит 1.

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

Время — O(m·log(n)·20).

Всем привет!

Через несколько часов начнется Codeforces Round #149 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Кроме того мы выражаем благодарность Марии Беловой (Delinur) и Михаилу Мирзаянову (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

В раунде будет использована стандартная разбалловка: 500-1000-1500-2000-2500

UPD: Соревнование закончилось, всем спасибо!

UPD: Поздравляем победителей:

1. Fio

2. ballmaids00

3. mihaipopa12

4. Yukari

5. chlxyd

UPD: опубликован разбор задач на русском языке

Привет!

Спешу поделиться с вами отличной новостью: с понедельника 29 октября 2012 года 00.00 часов по Московскому времени мы запускаем новое соревнование для программистов под названием Russian AI Cup 2012: CodeTanks! Но это будет не совсем обычное соревнование, так как в этот раз вам надо будет написать игровую стратегию и принять участие в танковом сражении.

Поучаствовать в этом мероприятии можно тут: http://russianaicup.ru

Что?

Russian AI Cup — это новый проект команды проекта “Одноклассники”, реализованный силами Mail.Ru Group и Саратовского Государственного Университета. Это соревнование — третье мероприятие компании Mail.Ru Group для талантливых IT-специалистов, ранее из этой серии мероприятий проводились Russian Code Cup и Russian Design Cup.

Где?

Заходите на http://russianaicup.ru и регистрируйтесь (мы рекомендуем для этого пользоваться аутентификацией для социальных сетей). Для участия в соревновании достаточно одной принятой посылки, и вы сразу попадете в рейтинг!

Когда?

• Песочница: с 29 октября по 2 декабря;
• Раунд 1: 10–11 ноября;
• Раунд 2: 17–18 ноября;
• Финал: 24–25 ноября.

А ништяки?

Конечно же, без них не обойдется :) Лучшие участники получат самые современные гаджеты в крутых комплектациях, среди которых MacBook Pro with Retina, MacBook Air, iPad и iPod.

Вау, как интересно, а можно поподробнее?

Подробнее вы можете прочитать на самом сайте http://russianaicup.ru, вот полезные ссылки:

• о Russian AI Cup
• o CodeTanks
• Быстрый Старт
• полные Правила

Let’s have fun! :)

Приветствую всех участников раунда!

237A - Free Cash

Из условия задачи легко понять, что если в некоторую минуту придут k человек, то Валере нужно иметь в кафе не менее k касс. Значит, требуется найти максимальное количество людей, которые придут в одну и ту же минуту, а это делается очень просто множеством способов, например, просто насчитав в массив cnt[h][m] количество людей, которые придут в час h и минуту m, а потом найдя в этом массиве максимум.

237B - Young Table

Решение, которое опишем ниже, почти никак не использует хитрую форму таблицы (кстати, такая таблица называется диаграммой Юнга). Заполним таблицу числами от 1 до s следующим способом: будем идти по строкам таблицы начиная с первой слева направо, после конца текущей строки переходим на начало следующей, и в процессе каждой из клеточек присвоим число по порядку обхода от 1 до s. Очень просто показать, что такой порядок чисел удовлетворяет оба неравенства из условия.

Теперь опишем алгоритм приведения таблицы из того вида, как она нам дана во входных данных, в описанный выше вид.

Возьмем число 1 и посмотрим, где оно находится в этих двух таблицах. Если это число стоит не на своем месте, то поставим его на свое место, соответственно то число, которое там стояло, встанет на старое место единицы. Аналогично сделаем для 2, 3, ..., s. Очевидно, что этот алгоритм сделает не более s шагов и приведет таблицу в вид, описанный в первом абзаце.

237C - Primes on Interval

Для начала с помощью решета Эратосфена выделим все простые числа от 1 до b и пометим их единичками в массиве d, то есть если p — простое, то d[p] = 1, иначе d[p] = 0.

Заметим, что если l — корректное число, то l + 1 тоже корректно. В самом деле, для позиций x от a до b - l количество простых в отрезке с началом в x могло лишь увеличиться (мы же длину отрезка увеличили, а значит, количество простых в нем никак не могло уменьшиться). А кроме того исчез из рассмотрения один отрезок с началом в точке b - l + 1, так как при увеличении длины его правый конец стал больше, чем число b.

Таким образом, мы показали, что функция f(l), возвращающая TRUE или FALSE (корректно число или нет) монотонна, а значит, мы можем с помощью бинарного поиска найти наименьшее l, для которого f(l) = TRUE, или ответить, что такого не существует.

Функция f(l) считается очень просто — можно проитерироваться по всем числам от a до b - l + 1 и найти для каждого начала количество простых чисел в соответствующем отрезке длины l, это можно сделать с помощью частичных сумм, насчитанных по массиву d.

237D - T-decomposition

Возьмем любое ребро начального графа, очевидно два его конца принадлежат некоторому множеству x_i, значит, вес любой его Д-декомпозиции как минимум 2. Покажем, как постороить декомпозицию именно такого веса. Для этого каждое из ребер исходного графа превратим в отдельное множество x_i, то есть все они будут состоять из двух элементов.

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

Для того, чтобы сделать из него дерево, достаточно для каждой вершины v начального дерева выделить все x_i, в которых она содержится, и соединить их в цепочку в любом порядке, добавив нужное количество ребер.

Несложно понять, что такой граф не будет содержать циклов, будет связен, а значит является деревом. Постоенная Д-декомпозиция будет иметь вес 2, и количество вершин n - 1.

237E - Build String

Эта задача несложно решается алгоритмом поиска максимального потока минимальной стоимости на трехслойном графе:

1. первый слой состоит из n вершин, каждая из которых отвечает за свою строку из входных данных; в i-ую вершину этого слоя входит по одному ребру из истока с пропускной способностью c_i и стоимостью i;

2. второй стой состоит за 26·n вершин, каждая из которых отвечает за количество определенных букв в каждой из строк из входных данных; в вершины этого слоя входят ребра только из первого слоя стоимостью 0 и пропускной способностью равной количеству соответствующих букв в соответствующей строке;

3. третий слой состоит из 26 вершин, каждая из которых отвечает за количество соответствующих букв в строке t; в вершины этого слоя входят ребра только из второго слоя стоимостью 0 и бесконечной пропускной способностью; кроме того, из вершин третьего слоя выходят ребра в сток стоимостью 0 и пропускной способностью, равной количеству соответствующих букв в строке t.

Если максимальный поток в этой сети меньше, чем |t|, то ответ равен  - 1, а иначе — минимальной стоимости максимального потока.

Доброе время суток!

Через несколько часов начнется очередной Codeforces Round #147 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павлик Холкин (HolkinPV), Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

В раунде будет использована стандарная разбалловка: 500-1000-1500-2000-2500

UPD: Соревнование завершено, поздравляем победителей:

1. try_skycn

2. AntiKismet

3. dianbei_03

4. Uncia

5. Bigsophie

UPD: Разбор уже опубликован тут.

Тема интерактивных задач становится все популярнее, такие задачи каждый год встречаются на NEERC, иногда на этапах OpenCup и в других местах. Но все-таки на данный момент это непаханое поле, так как совсем немногие полноценно поддерживают инфраструктуру для тестирования подобных задач.

На Codeforces эту тему недавно поднимал MikeMirzayanov в своем посте. Вот цитата оттуда (**рекомендую прочитать этот пост для того, чтобы быть в курсе темы**):

Первый случай, первым завершилось решение:

• Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт Time Limit Exceeded, Memory Limit Exceeded или Idleness Limit Exceeded (последний, если программа продолжительное время вообще не расходовала процессорное время).
• Если завершилось с кодом возврата неравным 0, то возвращаем Runtime Error.
• Если завершилось благополучно и с кодом 0, то продолжаем ждать пока завершится интерактор.

Второй случай, первым завершился интерактор:

• Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт Judgement Failed.
• Если завершился с кодом возврата неравным 0, то обрабатываем его как обычный чекер:
• код 1: возвращаем вердикт Wrong Answer,
• код 2: возвращаем вердикт Wrong Answer (или Presentation Error, если такой вердикт поддерживается),
• код 3 или любой другой: возвращаем Judgement Failed.

А теперь рассмотрим два очень даже вероятных случая:

• Решение выводит интерактору какую-нибудь неадекватную информацию и ждет ответа. Интерактор понимает, что дальше невозможно продолжать протокол и кончает жизнь суицидом — завершается с вердиктом WA (ну или PE, если этот вердикт поддерживается). Таким образом он завершает потоки ввода-вывода со своей стороны, в частности stdin решения. Напоминаю, что решение в данном случае ждет ответа интерактора, но так как поток с его стороны завершен, у решения не получается считать ответ и оно падает с RE;

• Второй вариант противоположен. Решение пытается что-то вывести интерактору, но в середине этого занятия падает с RE, завершая поток stdin интерактора со своей стороны. Однако что-то на этот момент все еще лежит в буфере, и интерактор это "что-то" читает, считает, что решение просто вывело ерунду и логично завершает работу с вердиктом WA или PE.

Эти две ситуации с точки зрения тестирующей системы абсолютно равны, так как решение падает с RE, а интерактор выносит вердикт WA. Но между ними есть большая разница в причине такого поведения, а именно, это Runtime Error или Wrong Answer решения. Эта ситуация лечится определением того, какой из процессов раньше завершился. Если первым упало решение, то это RE, а если первым упал интерактор, то это WA, и казалось бы проблем нет...

НО! Оказывается, что нельзя гарантированно определить порядок завершения процессов, то есть на то, что скажет ОС, полагаться нельзя!

Вот мы и пришли к концу повествования, а именно к вопросу: а как же определить истинную причину и сказать настоящий результат участнику? Разумеется, совершенно не хочется категорично менять инфраструктуру, описанную в посте MikeMirzayanov'а, хочется обойтись минимальными дополнениями в существующую модель.

Any ideas?

Запускаем у себя следующий код:

#include <iostream>
using namespace std;
int main() {
    cout << "??-" << endl;
    return 0;
}

Фишка появляется в Visual C++ 2005, 2008. Кто знает почему так?

UPD: круто, что можно спросить тут что-нибудь, и ответ придет почти сразу :) Всем спасибо

Приветствую всех участников раунда!

215A - Цепная передача

Из-за совсем небольших ограничений мы переберем i от 1 до n, переберем j от 1 до m, проверим, что b_j делит a_i нацело без остатка и среди всех таким пар найдем максимальное значение величины . Затем запустим этот алгоритм еще раз, таким образом найдем искомое количество пар, где достигается максимальное значение.

215B - Олимпийская медаль

Пусть нам известны выбранные значения r₁, p₁ и p₂. Запишем равенство:

Нетрудно заметить, что для того, чтобы максимизировать величину r₂ необходимо взять r₁ и p₁ — максимальными, а p₂ — минимальным среди предоставленных значений. Простой перебор тремя циклами всевозможных значений не проходил из-за ограничения по времени, однако допустимо было заметить зависимость хотя бы для одной величины, а две другие перебирать.

215C - Крестики

Переберем величины n₁ = max(a, c) и m₁ = max(b, d) — размеры ограничивающего прямоугольника. Далее нам надо найти значение величины f(n₁, m₁, s), а к ответу прибавить f(n₁, m₁, s)·(n - n₁ + 1)·(m - m₁ + 1), где последние две скобки дают количество способов расположить ограничивающий прямоугольник в данном клетчатом поле.

Теперь нам надо подсчитать величину f(n₁, m₁, s). Ну во-первых, если n₁·m₁ = s, то ответ функции равен 2·(⌊ n₁ / 2⌋ + 1)·(⌊ m₁ / 2⌋ + 1) - 1 (попробуйте сами догадаться почему).

Если же n₁·m₁ > s, то нам надо выкинуть 4 уголка, которые являются одинаковыми прямоугольниками площадью . Мы можем перебрать одну из сторон уголка, найти вторую, проверить что все ограничения выполняются, и за каждую найденную пару сторон прибавить к ответу функции по 2.

Таким образом, решение работает за O(n³), однако, с очень маленькой константой гораздо меньшей, чем 1.

215D - Жара

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

Достаточно подсчитать эти величины и взять минимум.

215E - Периодические числа

Скоро появится…

Доброе время суток!

Через несколько часов начнется очередной Codeforces Round #132 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Эдвард Давтян (Edvard), Виталий Аксенов (Aksenov239), Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

Отдельно хочется пожелать успеха и спортивной удачи всем, кто сейчас представляет свои страны на XXX Олимпийских играх в Лондоне!

На раунде будет использована динамическая система оценки задач. Но, несмотря на это, задачи будут расположены в предположительном порядке возрастания сложности!

UPD: Раунд завершен, спасибо всем за участие! Надеемся, что все участники получили удовольствие!

UPD: Поздравляем победителей!

1. yooo — единственный участник Div.2, кто решил все представленные задачи!

2. zzy

3. High_Rich_Handsome

4. bookcity_clock

5. capythm

UPD: Разбор задач на русском языке уже опубликован!

Приветствую всех участников раунда!

203A - Two Problems

Из-за совсем небольших ограничений можно было перебрать минуту, на которой Вася пошлет решение по первой задаче и минуту, на которой Вася пошлет решение второй задачи. Однако были несколько хитрых случаев: нужно было не забыть, что Вася может послать только одну задачу (то есть в этом случае нужно было перебрать только одну величину), а также может вообще не посылать задачи — в этом случае он получает 0 баллов.

203B - Game on Paper

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

Таким образом, решение работает за O(m) с константой порядка 80 и требует O(n²) памяти.

203C - Photographer

Заметим, что если Вася хочет обслужить клиента номер i, то ему понадобится ровно f(i) = a·x_i + b·y_i мегабайт памяти на фотоаппарате. Также заметим, что так, как мы хотим максимизировать количество клиентов, то гораздо выгоднее брать тех, у кого величина f(i) меньше. Таким образом мы приходим к решению: сразу при чтении данных запомним для каждого клиента величину f(i), отсортируем всех клиентов по этой величине и будем обслуживать в порядке возрастания до тех пор, пока хватает памяти в фотоаппарате.

Время работы — O(n·log(n)).

203D - Hit Ball

Эта задача имеет два разных решения.

Решение 1. Будем последовательно двигаться по траектории мяча до тех пор, пока не влетим в поверхность двери. Для этого будем считать от каждой точки следующую точку, где текущий луч пересекает какое-либо препятствие (стена, дверь и так далее). Каждая точка на луче имеет вид (x + t·v_x, y + t·v_y, z + t·v_z), где t > 0 — параметр. Подставим уравнения всех препятствий в этот вид и найдем минимальное t, а значит, и точку, где луч пересечет препятствие первый раз. Осталось только пересчитать v_x, v_y,v_z и повторить процесс дальше до тех пор, пока мяч не влетит в дверь. Пересчитывать компоненты вектора скорости очень просто — при столкновении соотвествующую компоненту нужно просто умножить на  - 1.

Время работы такого решения — O(X²), где X — максимальная из координат мяча в начальный момент времени.

Решение 2. Как известно, траекторию отражения луча света от зеркала можно считать прямой, если отразить относительно зеркала все остальные объекты. Для уточнения приведем рисунок: на нем можно построить траекторию движения луча от точки A к точке B отразив точку в B в B' и нарисовав отрезок AB’.

Аналогичную идею будем использовать в нашем решении. Каждую координату x или z будем находить независимо, рассмотрим для x, для z аналогично.

Допустим у нас нет стен, тогда мяч прилетел бы в точку с координатой . Теперь допустим x₀ > 0, а стена представляет собой прямую x = a. Тогда мысленно отразим наш коридор (то есть полосу между прямыми x = 0 и x = a) несколько раз, то есть получим множество прямых x = ka, где пространство между соседними прямыми — это одно из отражений коридора.

Посмотрим, сколько раз отрезок между точками (a / 2, m) и (x0, 0) пересекал прямые, и в зависимости от четности можно понять, от какой стороны коридора последний раз отразился мяч, прежде чем попал в дверь. А сам ответ несложно найти отложив величину x₀ (mod a) (где "mod" означает остаток от деления нацело) от соответствующей стены.

Таким образом, описанное решение позволяет найти ответ за O(1).

203E - Transportation

В этой задаче требуется рассмотреть два случая.

Первый — пусть все роботы едут самостоятельно. Тогда выделим множество роботов, у которых l_i ≥ d, отсортируем их по возрастанию количества требуемого горючего, и будем брать в этом порядке и отправлять в багажное отделение пока не кончится топливо. Этот случай похож на решение задачи C этого же раунда.

Второй случай рассматривает тех роботов, которые вкладывают друг в друга. Выделим множество роботов, у которых c_i > 0, пусть из всего k штук, и пусть . Тогда несложно понять, что если мы всех этих роботов упакуем так, чтобы лишь из них ехало самостоятельно, а остальные были вложены в другие роботы, то еще у нас останется свободных слотов для других роботов.

Таким образом, выделим множество роботов у которых c_i > 0, l_i ≥ d — то есть эти те роботы, которые могут везти других роботов и при этом могут самостоятельно добраться до багажного отделения.

Переберем, сколько из таких роботов на самом деле поедут своим ходом (не забываем про ограничения на топливо), и по формуле выше найдем количество свободных слотов. Заметим, что мы уже в любом случае отправили всех роботов, у которых c_i > 0, а значит остались только те, у которых c_i = 0, пусть таких всего num.

Каждый робот может иметь 3 состояния: он займет один из слотов, он поедет своим ходом, если у него l_i ≥ d и если хватит топлива, или он вообще не поедет.

Известно, сколько имеется слотов, а значит можно найти, сколько роботов или поедут своим ходом, или останутся, а точнее их . Таким образом, нам надо найти среди всех роботов с c_i = 0 и l_i ≥ d максимальное количество роботов (но не более, чем g штук), на которых осталось достаточно топлива. Остальные роботы поедут на свободных слотах или останутся (их известное количество).

Эта подзадача решается предподсчетом величины f(i), означающую минимальное количество топлива, необходимое чтобы отправить i роботов среди тех, для которых выполняется c_i = 0 и l_i ≥ d. По этой функции, очевидно, можно делать бинарный поиск.

Таким образом, соберем элементы решения: сначала переберем количество роботов, которые поедут своим ходом среди тех, у которых c_i > 0, а затем с помощью бинарного поиска по предподсчитанной величине найдем, сколько роботов из оставшихся уместятся на свободные слоты, сколько поедут также своим ходом, а сколько останутся.

Не забудем про случай, когда вообще все роботы едут самостоятельно.

Мы получаем алгоритм, который можно реализовать за время O(n·log(n)).

Друзья, привет!

Через несколько часов Вам посчастливится участвовать в знаменательном раунде Codeforces Round #2⁷ для участников Div. 2¹, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV). Как всегда с нами были Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Как вы все прекрасно знаете, только сегодня вы сможете поучаствовать в этом раунде в конкурсе, не упустите такую возможность! Другого раунда Codeforces Round #2⁷ вы не увидите нигде! :)

Традиционно всем удачи, полных решений и удачных взломов!

UPD: Распределение баллов по задачам стандартное: 500, 1000, 1500, 2000, 2500.

UPD: Соревнование закончено, всем спасибо за участие. Надеюсь вам понравилось, но не забывайте, что нас еще ждет системное тестирование.

UPD: Уже опубликована предварительная версия разбора на русском языке

Приветствую всех участников раунда!

Давайте проведем разбор задач в примерном порядке их сложности

182B - Vasya's Calendar

Обратим внимание, что Вася должен вручную прибавлять номер дня только тогда, когда заканчивается один месяц, и начинается следующий. Значит, пусть у нас в текущем месяце было x дней, а в следующем уже y. Тогда в первый день следующего месяца часы будут показывать день x + 1 (не забываем про модуль d), а должен показывать номер 1.

Очевидно, что Вася должен вручную прибавить d - x дней, чтобы часы показывали то, что нужно.

Значит, ответ — это сумма всех чисел d - a_i, где 1 ≤ i < n.

182D - Common Divisors

Эта задача решается многими способами, но самый простой подход следующий: найдем все делители строки s₁, все делители s₂ и найдем пересечение этих двух множеств.

Как же найти все делители строки? Пусть t — это делитель строки s. Тогда очевидно, что |s| = 0(mod|t|), а также t является префиксом строки s. Эти соображения и позволяют найти все делители строки, а именно переберем длину префикса, проверим делимость, а потом проверим, что префикс записанный подряд нужное количество раз совпадает с s.

Всего подходящих префиксов не более , проверка каждого работает за O(|s|), значит, итоговое решение за , где n = max(|s|, |t|).

Найти пересечение двух множеств строк несложно, можно воспользоваться стандартными структурами данных

182E - Wooden Fence

Условие задачи было сформулировано неверно, что привело к несоответствию решений, правильный вариант условия появится совсем скоро, приносим участникам свои извинения.

Основа решения этой задачи — это динамическое программирование.

Состояние — (last, type, l), где last — номер последней доски, type характеризует поворот последней доски, а l — длина оставшейся части забора.

Пересчитывать эту динамику тоже очень просто: переберем номер следующей доски, ее поворот, проверим подходит ли она в текущее состояние, и прибавим нужную величину.

Асимпотика решения — O(n²·len).

182C - Optimal Sum

Представим мысленно задачу в виде движения слева направо некоторого окошка длины len по исходному массиву. То есть нам нужно найти способ достичь максимума в выбранном окошке, а потом сместить его на одну ячейку вправо.

Пусть мы зафиксировали положения окошка, теперь посчитаем ответ. Для этого отдельно запишем все положительные и все отрицательные числа в окошке. Если положительных не больше, чем k, или отрицательных не больше k, то мы можем все числа сделать одинакового знака, и ответ — это сумма модулей чисел в подмассиве. Это простой случай.

Несложно понять, что невыгодно некоторые отрицательные числа делать положительными и одновременно некоторые положительные — отрицательными. То есть мы обязательно выберем знак <<+>> или <<->> и k чисел этого знака сделаем противоположными. Также несложно понять, что всегда при смене знака у некоторых чисел выгодно брать ровно k максимальных по модулю чисел этого знака.

Для того, чтобы поддерживать движение окошка будем использовать два отдельных дерева отрезков: одно для отрицательных, другое для положительных чисел.

Если в вершине дерева хранить пару (количество чисел в поддереве, сумма этих чисел), то такая структура умеет возвращать сумму k максимальных чисел, что нам и требуется.

Асимптотика решения — O(n·log(n)).

182A - Battlefield

В этой задаче есть два главных момента:

1. длина любой траншеи в метрах численно не превосходит b

2. траншеи не пересекаются

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

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

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

Два тонких момента:

1. мы не можем перебегать между траншеями, если между ними расстояние больше a

2. пусть Вася прибежал в момент времени t, теперь нам нужно найти момент, когда он сможет убежать дальше. Для этого нужно найти следующий момент времени, когда лазер будет перезаряжаться. Эта величина T несложно ищется по формуле:

Асимптотика решения — O(n²).

Друзья, всем привет!

Через несколько часов состоится очередное соревнование — Codeforces Round 112 для участников Div. 2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Артем Рахов (RAD), Павел Холкин (HolkinPV). Как всегда с нами были Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Отдельно хотелось бы пожелать удачи моим сокомандникам, Артему Рахову и Иванову Максиму (e-maxx), которые на днях улетели в США для принятия участия в онсайд-раунде Facebook HackerCup.

Мы надеемся, что сегодняшние задачи понравятся всем участникам, и каждый займет заслуженное высокое место в итоговой таблице :)

UPD: Соревнование завершилось, всем спасибо за участие :) Мы надеемся, что вам понравилось.

UPD: Друзья, предлагаю всем ознакомиться с разбором задач: http://codeforces.me/blog/entry/4124

UPD: Поздравляем победителей!

1. Doriam30

2. woshisb

3. Senjougahara_Hitagi

4. LiWenHaoTianXiaDiYi

5. pqxdcel

6. UranusX

7. QDkAc

Полные результаты доступны по ссылке: http://codeforces.me/contest/165/standings

160A - Twins

В этой задаче требовалось найти подмножество наименьшего размера, сумма чисел в котором строго больше, чем половина суммы всех чисел. Несложно понять, что выгоднее брать наибольшие числа в массиве, так мы быстрее наберем нужную сумму. Тогда решение выглядит следующим образом: отсортируем числа по невозрастанию и переберем сколько первых чисел заберем мы, а сколько – наш близнец, Как только у нас строго больше, чем осталось для близнеца – выведем ответ.

160B - Unlucky Ticket

Запишем в массив a первые n цифр, а в массив b — последние n цифр, и отсортируем эти массивы. Нетрудно понять, что если для всех i выполняется a[i] < b[i], или для всех i выполняется a[i] > b[i], то билет точно является несчастливым. Но также нетрудно понять, что для любого несчастливого билета выполняется или первое условие, или второе. Таким образом, мы придумали критерий несчастливости, можно реализовать за время O(n·log(n)).

160C - Find Pair

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

Пусть число k и массив a заданы в 0-нумерации, а сам массив отсортируем. Тогда если все числа различны, то очевидный ответ – это пара (a[k / n], a[k % n]), где операция % означает остаток по модулю. Однако, если в массиве есть повторяющиеся числа, то ситуация становится немного хитрее, рассмотрим пример: пусть дан массив (1, 1, 2, 2), тогда пары записаны следующим образом: (1, 1), (1, 1), (1, 1), (1, 1), (1, 2), (1, 2), (1, 2), (1, 2), (2, 1), (2, 1), (2, 1), (2, 1), (2, 2), (2, 2), (2, 2), (2, 2), каждая пара учитывается и никуда не девается, всегда рассматриваются ровно n² пар чисел.

По-прежнему верно, что первое число – это a[k / n]. А второе число – это a[(k–n·cnt) / num], где cnt – количество чисел в массиве строго меньших, чем a[k / n], а num – количество чисел в массиве, которые равны a[k / n].

В этой формуле несложно убедиться, рассмотрев пару примеров с повторяющимися элементами. В крайнем случае, можно написать тривиальное решение за O(n²·log(n)) и убедиться, что вы правильно придумали формулу.

P. S. Претест 3 имеет вид: в массиве (1, 1, 2) нужно найти 3-ю по лексикографичности пару. Она равна (1, 1).

160D - Edges in MST

Во-первых, разберем случай, когда все веса одинаковы. Тогда очевидно, что любое ребро может быть в дереве, но в случае, если ребро – мост, то оно является единственным способом соединить две компоненты, а значит, оно принадлежит любому MST. Итак, для мостов ответ равен «any», а для всех остальных – «at least one».

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

А значит, мы можем решать задачу по слоям: на каждом слое мы рассматриваем одновременно все ребра с данным весом, а сами слои – в порядке возрастания веса.

Построим на каждом слое отдельный граф, причем вершинами будут являться уже сформированные на данный момент компоненты связности, а ребра добавляются между соответствующими компонентами. Если ребро – петля, то значит, что существует способ связать два конца этого ребра за меньшую стоимость, и это ребро никогда нам не нужно, ответ для него – «none».

Если ребро в построенном графе – мост, то по ранее разобранному случаю, ответ для него «any», а для всех остальных – ответ «at least one». При разборе этих случаев нужно быть аккуратным, потому что при сжатии графа появляются мультиребра, ответ для них всегда «at least one», потому что ни одно из повторяющихся ребер не является мостом.

Решение это задачи можно реализовать за время O(n·log(n)).

160E - Buses and People

Для начала, промасштабируем все координаты и времена, а также, так как все t_i различны, то запомним для каждого t_i номер автобуса, который поедет с этим временем.

Для каждого автобуса создадим событие вида «при координате s_i появляется автобус, который поедет в момент времени t_i и уедет до точки f_i». Для каждого человека создадим событие вида «при координате l_i появляется человек, который поедет в момент времени b_i и уедет до точки $r_i$».

Эти события отсортируем в порядке возрастания координаты (s_i, если это автобус, и l_i, если это человек) и будем выполнять в этом порядке.

Будем поддерживать структуру данных, в которой для каждого времени t_i будем хранить максимальное f_i автобуса, который едет в этот момент. Тогда если текущее событие означает автобус, то нужно просто обновить соответствующее значение в структуре данных. А если текущее событие означает человека, который в момент времени b_i поедет до остановки r_i, то нужно с помощью структуры данных отвечать на запрос «найти в структуре минимальную позицию t, которая не менее b_i, а соответствующее ему значение не менее r_i», тогда соответствующий этому t номер автобуса и есть ответ.

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

Таким образом авторское решение работает за время O((n + m)·log(n + m)).

Существует достаточно простое решение с двумерным деревом отрезков, работающее за O((n + m)·log²(n + m)), но не гарантировалось, что оно уложится в Time Limit.

149A - Командировка

Во-первых, ясно, что если сумма всех чисел a_i меньше, чем k, то Петя в любом случае не сумеет вырастить цветок до нужной высоты, и следует вывести <<-1>>.

Во-вторых, несложно понять, что если мы хотим выбрать один месяц из двух, в который мы будем поливать цветок, то выгодно выбирать тот, где число a_i максимально. Таким образом, решение задачи очень просто: следует брать месяцы в порядке убывания чисел a_i и в эти месяцы поливать цветы. Как только сумма набранных a_i станет больше или равна k — следует прекратить процесс, ответ найден.

149B - Марсианские часы

В этой задаче требовалось только умение работать с разными системами счисления. Давайте попробуем перебрать основание, для каждого основания проверить, допустимо ли оно, а также перевести часы и минуты в десятичную систему и сравнить с 24 и 60 соответственно.

До какой величины следует перебирать основание? На самом деле, достаточно до 60, потому что 60 – верхнее ограничение на допустимые числа. Это следует из того, что если число в неизвестной системе счисления состоит из одного знака, то ее значение в десятичной не меняется никогда, а иначе его значение не меньше основания.

Также стоило разобрать случай с ответом <<-1>>, для этого, например, можно было проверить большое основание, например 100, и если для даже для него время корректно, то и для всех больших оно тоже корректно и ответ равен <<-1>>.

149C - Разделение на команды

Отсортируем всех мальчиков по умению играть. Тогда если мы отправим в первую команду всех мальчиков, стоящих в отсортированном массиве на нечетных местах, а во вторую – стоящих на четных местах, то все требования к разбиению выполнятся.

Первые два требования очевидно выполняются.

Для доказательства третьего рассмотрим геометрическое представление: пусть каждый мальчик обозначается точкой на оси X со значением, равным его умению играть. Соединим отрезками точки с номерами 1 и 2, 3 и 4, и так далее. Если n нечетно, то соединим эту точку с ближайшей предыдущей.

Очевидно, что все эти отрезки попарно пересекаются разве что в точках, а суммарная их длина равна разности сумм умений играть мальчиков, входящих в первую команду и во вторую команду. Также очевидно, что все эти отрезки полностью содержатся в отрезке [0, max(a_i)], а так как попарно имеют нулевую длину пересечения, то третье требование выполняется, что мы и доказали.

149D - Раскрашивание скобок

Введем обозначения цветов: 0 – черный, 1 – красный, 2 – синий. Заметим, что у отдельно взятой пары скобок всего 4 варианта раскраски: 0-1, 1-0, 0-2, 2-0.

Рассмотрим динамическое программирование, где состояние имеет вид – (l, r, c_l, c_r), где пара (l, r) задает одну из пар скобок, а с_l и c_r означают фиксированные для них цвета. Значением динамики является количество способов раскрасить все скобочки внутри отрезка (l, r) с соблюдением всех условий.

Выпишем все пары скобок, которые вложены непосредственно в пару (l, r), пусть их k штук. Причем, будем рассматривать только первый уровень вложенности, именно непосредственно вложенные. Для того, чтобы подсчитать значение динамики для состояния, внутри этого состояния будем подсчитывать еще одну динамику, где состояние – это пара (i, c) которое означает количество правильных раскрасок первых i непосредственно вложенных скобок и всех внутри них, если последняя закрывающая скобка имеет цвет c. Пересчитывать такую динамику вперед очень просто – попробуем раскрасить (i + 1)-ую скобочку в один из четырех вариантов, учитывая возможные конфликты. У такой динамики начальным состоянием является пара (0, c_l), а итоговый результат – сумма по состояниям вида (k, c), где c не должно конфликтовать с c_r.

Ответ на всю задачу считается аналогично внутренней динамике. Асимптотика решения – O(n²) с коэффициентом порядка 12.

149E - Марсианские строки

Будем решать задачу отдельно для каждой из m строк. Итак, пусть у нас есть строка p, ее длина l, и нам нужно проверить, может ли марсианин ее увидеть.

Введем дополнительные массивы: пусть pref[i] – минимальная позиция в s начала вхождения префикса строки p длиной ровно i, а также пусть suff[j] – максимальная позиция в s конца вхождения суффикса строки p длиной ровно j.

Нетрудно понять, что марсианин сможет увидеть p, если существует такое i, что suff[l - i] ≥ pref[i] + l–1.

Как подсчитать массивы? Для массива pref достаточно найти Z-функцию строки p#s, а для массива suff – Z-функцию строки r(p)#r(s), где r(t) означает перевернутую строку t. Используя массив Z-функций значения массивов suff и pref подсчитать тривиально.

Друзья, всем привет!

Наконец, открылась регистрация на SRM 523. Напоминаю, он начнется в 21.00 по московскому времени

Для вашего часового пояса смотрите сюда.

Задача А (Div-2). Игрушечные армии

Задача E (Div-1). Две последовательности

Задача A. Double Cola

Задача B. Множества

Задача C. Всеобщая мобилизация

Задача D. Два из трех

Я рад приветствовать всех любителей программирования!

Сегодня состоится второй квалификационный раунд Яндекс.Алгоритм, и для вас его готовили Артем Рахов, Михаил Мирзаянов и я.

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

Напоминаю, лучшие 500 участников проходят в Яндекс.Алгоритм 2011 Раунд 1, который состоится 20 мая в 19.00

Удачи!

UPD: соревнование закончилось, я поздравляю tourist с победой!

Напоминаю, что это был квалификационный раунд, а это значит, что первые 500 участников в конкурсе выходят в следующий раунд! Мои поздравления!

Сегодня у нас целых два самых удачливых участника: Hossein_Hima и ss.nurboolean - они разделили 499-500 места с результатом в 978 балла. Желаем еще большей удачи :)

Задача F. "Умный мальчик"