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

Рассмотрим решение с помощью метода динамического программирования.

Пусть D_i - минимальный штраф, который мы заплатим, если будем решать задачу для шариков с номерами от i до n, причем шарик номер i будет обязательно приколот.

Тогда D_i = min_{i ≤ j  ≤ n}(D_j + 1 + S(i, j) + c_i)
где

Если числа S(i, j) не считать каждый раз, а пересчитывать, используя формулу S(i, j) = S(i, j - 1) + x_j - x_i, то решение требует всего O(n) памяти и  O(n²) времени на решение.

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

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

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


тогда переберем это значение x ≥ l, и найдем максимум выражения x· f(x). Это число и надо вывести.

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

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

Как известно, существует 2 условия равновесия тела (здесь и далее будем считать устойчивое и неустойчивое равновесие неразличимыми, и называть общим словом "равновесие" или "устойчивость", так как в данной задаче нет никакого внешнего воздействия на конструкцию, кроме естесственной силы тяжести и силы взаимодействия кубиков с друг другом), но нам в этой задаче надо будет рассмотреть второй закон равновесия, который мы переформулируем в критерий устойчивости для нашей задачи:

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

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

Приведем формулы для координат центра масс некоторых n кубиков:

где:
,
m_i = |x_i, 1 - x_i, 2|³ = |y_i, 1 - y_i, 2|³

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

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

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

Будем считать, что читатели знакомы с этой структурой (если это не так, то советую почитать тут). Самое простой по логике подход использует неявное декартово дерево, и этот алгоритм действует так: будем добавлять людей по очереди, в порядке их прихода. В вершине дерева, кроме служебной информации, будем поддерживать число maxValue, равное максимальному значению из чисел a_i в этом дереве.

Бинарным поиском переберем возможную позицию нового человека, пусть он имеет номер k, pos от 0 до c_k (для удобства нумерацию введем с конца очереди). Человек достигнет этой позиции тогда и только тогда, когда среди чисел a_i, 0 ≤ i < pos не существует ни одного, большего числа a_k. Это можно проверить, отщепив от декартова дерева поддерево размера pos, и проверив у него число maxValue. Таким образом мы найдем значение pos, и в эту позицию вставим нового человека. Построив полную очередь, нужно вывести ответ. Но это очень простая операция, не будем ее обсуждать. Асимптотика такого решения . Замечу, что это решения является неоптимальным, и вполне возможно, что оно не всегда пройдет по времени, поэтому модифицируем его:

избавимся от бинарного поиска. Для этого можно сразу отщепить от дерева поддерево размера c_k с начала дерева, и найти в нем такую максимальную позицию pos, что все числа a_i (0 ≤ i < pos) меньше a_k. Это делается с помощью одного обхода вниз по дереву, где на каждой вершине мы смотрим, надо ли закончить спуск, или надо выбрать одного из сыновей и продолжить. В процессе такого пути накапливаем количество вершин, оставляемых слева от текущей. Потом вставляем нового человека в найденную позицию, и восстанавливаем дерево обратно. Подумайте сами, как это реализовать, это не очень сложно. Асимптотика нового решения уже составляет .

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

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

Будем хранить для каждого списка также число maxValue, равное максимальному значению из чисел a_i в этом списке. Тогда добавление происходит так: будем искать подходящее место для нового человека, для этого пропустим все списки, суммарной длиной, меньшей c_k, причем во всех этих списках числа maxValue должны быть меньше, чем a_k. Если мы возьмем первый такой список, где это условие не выполняется, или c_k стало меньше, чем длина пропущенных список плюс длина текущего, то мы по такому списку пробежимся "в лоб", то есть по каждому элементу от начала до конца, проверим выполнение условий, и добавим нового человека на найденное место.

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

Тогда применим следующую хитрость: в момент, когда какой-либо список станет больше, чем 2 * s элементов, то сделаем перераспределение людей в очереди. Из списков, которые содержат более s элементов, будем проталкивать их в следующую очередь. Таким образом мы нормируем списки, и они станут достаточно короткие - всего не более s элементов в каждом.

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

Значит, наше решение работает за .

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

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

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

Эта задача была утешительной и самой простой на этом контесте. Ответ считается по формуле:



Никаких "подводных камней" и хитростей эта задача не содержит.

Всем доброго времени суток

Завтра, 30 октября я приглашаю Вас принять участие в увлекательном соревновании. Оно будет являться отборочным раундом в ЗКШ (Школьная индивидуальная олимпиада #1 (ЗКШ 2010/11), подробнее читайте тут), но для более взрослых участников это будет просто новым Codeforces раундом (Codeforces Beta Round #38, ACM-ICPC Rules).

Замечу, что в отличие от предыдущей отборочной олимпиады, наше завтрашнее соревнование - личное. Официальные правила соревнования, как видно из названия, - ACM-ICPC.

За это соревнование, как и обычно, будет начисляться рейтинг. Участники, которые не принимают участие в отборе в ЗКШ, будут в таблице результатов отображаться, как участники "вне конкурса", но не пугайтесь, рейтинг будет подсчитан по совмещенной таблице.

Также, после совещания жюри, было решено продлить раунд. Теперь он будет длиться 4 часа, обратите на это внимание!

Авторами соревнования являюсь я (NALP), Михаил Мирзаянов и Артем Рахов. Также я хочу поблагодарить Марию Белову - нашего переводчика задач, Максима Иванова, Наталью Бондаренко за помощь.

Жюри Codeforces.

P.S. Напоминаю о том, что для участия в соревновании Вам нужно зарегистироваться. Не забудьте это сделать.

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

Эта задача является на этом раунде "утешительной", и я надеюсь, что все ее решили. Но для тех, у кого по каким-либо причинам не получилось это сделать, давайте разберем ее решение.

Пусть входная последовательность называется a, а ее длина равна n. Тогда в некоторый массив запишем индексы x₁, ..., x_k в возрастающем порядке  - все позиции, где в последовательности a стоят символы '1'.

Тогда нужно проверить последовательность x₁, ..., x_k на то, является ли она арифметической прогрессией. Проще всего это сделать так: записать некоторую переменную d = x₂ - x₁, и проверить, выполняется ли для всех 1 ≤ i < k свойство d = x_i + 1 - x_i.

Если выполняется --- вывести "YES", иначе "NO".

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

Во-первых, нужно сказать, что в данной задаче элементы теории вероятностей не играют существенной роли. То есть можно считать, что у i-ой мишени всего лишь есть некоторый "вес", который равен как раз вероятности попадания в нее, а именно p_i. Достаточно просто понять, почему это так:

Математическое ожидание количества попадания в i-ую мишень равно M_i = 0 * (1 - p_i) + 1 * p_i = p_i, а математическое ожидание попадания в несколько мишеней по очереди равно сумме математических ожиданий, а значит, по уже сказанному, равно сумме вероятностей попадания в эти мишени.

Поэтому нами (авторами этой задачи) предлагается решение динамическим программированием, а именно:

D_i равно максимальному математическому ожиданию попаданий, если у нас на данный момент прицел направлен в мишень номер i, причем, текущее время (которое, однако, не является параметром и явно нигде не учитывается) меньше или равно t_i.

Тогда D_i = p_i + max(D_j), где j-ая мишень обозначает следующую мишешь, куда мы переместим прицел. Соответственно, для нее должно выполняться условие: t_i + dist(i, j) ≤ t_j, для того, чтобы такой переход имел место быть. Очевидно, что граф переходов ацикличен, а это значит, что такое решение верно.

Ответом является максимальное D_i по всем 1 ≤ i ≤ n. Асимптотика данного решение O(n²).

А все-таки, что это такое? каков смысл участия в этом?
и вообще, расскажи, пожалуйста, что это и с чем едят =)

UPD: в раунде 1 даже не обратил внимания на эту штуку, потому что не до того было

Доброго времени суток всем.

В этот чудесный летний день приглашаю вас принять участие в Codeforces Beta Round #19. Сегодня авторами задач для Вас буду я и Артем Рахов.

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

Надеюсь, что вам понравится.
Всем успехов!

P.S. После начала соревнования вы сможете скачать условия на русском и на английском языках.

Это не совсем блог, а скорее просто вопрос к знающим людям =)

Интересно, а как вычисляется вклад (см. пару сантиметров правее на табличку)? что он означает по своей сути? Вот у меня вклад = +5... откуда? 0_о

Также пожелание - сделать или RSS, или просто табличку прямого эфира поболее, а то можно не успеть за последними новостями и сообщениями ;-)

Замечу, что интересно взглянуть на первый контест на данном ресурсе, потому что и правила, и время соревнований, и все ньюансы - пока покрыты мглой =) ждем-с

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

UPD2: хотелось бы, что бы в полной табличке лидеров http://mirror.codeforces.com/top-contributed были не имена пользователей, а ссылки на профили - например, чтобы проще у них читать блог