Блог пользователя NALP

Автор NALP, 14 лет назад, По-русски

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

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

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

Тогда
Di = mini ≤ j  ≤ n(Dj + 1 + S(i, j) + ci)

где


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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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

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


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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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

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

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

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

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

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

где:
,
mi = |xi, 1 - xi, 2|3 = |yi, 1 - yi, 2|3

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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

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

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

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

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

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

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

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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


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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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

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



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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски
Всем доброго времени суток

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

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

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

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

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

Жюри Codeforces.

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

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

Поздравляем победителя, который занял первое место как в общем, так и в школьном зачетах, решив все предложенные задачи за ~2 часа: tourist. Поздравляем!

Следующая отборочная олимпиада для школьников состоится 6 ноября, в 14.00 по московскому времени. Следите за новостями!

Немного статистики: всего участников было 788, из которых 274 принимали участие в отборе. Мы надеемся, что в следующем соревновании эти показатели будут побиты :)

UPD2: опубликованы некоторые разборы. Скоро появятся и остальные, не беспокойтесь:
Разбор задачи А
Разбор задачи B
Разбор задачи C
Разбор задачи D
Разбор задачи E
Разбор задачи F
Разбор задачи G

Полный текст и комментарии »

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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


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

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

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

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

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 36
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски

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


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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор NALP, 14 лет назад, По-русски
Доброго времени суток всем.

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится