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

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

182B - Календарь Васи

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

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

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

182D - Общие делители

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

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

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

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

182E - Деревянный забор

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

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

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

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

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

182C - Оптимальная сумма

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

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

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

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

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

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

182A - Поле битвы

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

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.ru/blog/entry/4124

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

1. Miriam

2. woshisb

3. Senjougahara_Hitagi

4. KotonohaKatsura

5. pqxdcel

6. UranusX

7. QDkAc

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

160A - Близнецы

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

160B - Несчастливый билет

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

160C - Найти пару

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

Пусть число 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 - Ребра в MST

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

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

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

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

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

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

160E - Автобусы и люди

Для начала, промасштабируем все координаты и времена, а также, так как все 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. "Умный мальчик"

Задача E. "Ну-ка, покатились!"

Задача C. "Жалюзи"

Задача D. "Архитектор Вася"

Задача G. "Очередь"

1. Декартово дерево (дуча, treap или дерамида)

2. Использование метода -декомпозиции.

Задача B. "Ладья, Конь... и снова Конь"

Задача А. "Армия"

Задача А -  "Внеземной разум"

Разбор задачи "C. Тир"

Также выражаю благодарность всем, кто помогает нам в организации этого соревнования: Михаилу Мирзаянову, Эдварду Давтяну  и Юлии Сатушиной.