Codeforces Round #265: разбор Я скоро засабмичу свои решения и положу здесь ссылки. В некоторых разборах приведены дополнительные челленджи, над которыми можно поломать голову. Делитесь идеями в комментариях. =) [problem:465A] Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна $l$. Тогда ответ равен $l+1$, кроме случая, когда вся строка состоит из единиц, тогда ответ $l$. Забавно, что в задаче div1E тоже приходится думать о том, что будет, если прибавить к числу 1. =) [problem:465B] Наилучшая стратегия такова: для каждого непрерывного отрезка из непрочитанных писем откроем первое письмо, пролистаем до последнего в том же отрезке, если есть еще непрочитанные письма, вернемся к списку. Легко показать, что лучше мы сделать не сможем: для выбранного отрезка посмотрим на момент, когда мы прочитаем последнее письмо из него. Если мы ...

Full text and comments »

ЕГЭ Раз уж я <a href="http://mirror.codeforces.com/blog/entry/436#comment-6097">начал</a> разговор о ЕГЭ, ...<br>Итак, поговорим о вопросах Жизни, Вселенной и Всего Такого.<br><br>Переписка двух людей в аське.<br>Ники изменены, цензура применена:<br>[cut]<br>&nbsp;xxx<br>если подумать - то процесс подготовки к ЕГЭ - это как раз придумывание, а уже потом натаскивание и тренировка на задания. В чем прелесть то - если уже один раз решал - потом не придётся изобретать велосипед, ибо ты его уже знаешь.<br><br>&nbsp;yyy<br>о_О<br><br>&nbsp;xxx<br>это как с задачами про программированию. Идя на контест ты помнишь основные методы , а задачи - это просто ходы влево-вправо от основных вещей. Другой вопрос, если организаторы сделали сюрприз и добавили что то новенькое<br><br>&nbsp;yyy<br>нее, ты не жжошь<br><br>&nbsp;yyy<br>это же убивает всю фантазию, весь интеллект<br><br>&nbsp;yyy<br>задания наоборот должны быть разнообразными, ХОТЯ БЫ в части С<br><br>&nbsp;xxx<br>да ладно. Ты на ЕГЭ решишь всего 4 задан...

Full text and comments »

ABBYY Cup 2.0 — Hard: разбор Разбор задач будет пополняться :) ### Разбор задачи <<Развивающая игра>> Это была самая простая задача из сложного набора. Для начала заметим, что можно решать данную задачу для каждого элемента $a_i$ отдельно. То есть, если мы фиксируем некоторое $k$, то вклад каждого $a_i$ в ответ можно считать отдельно. Итак, фиксируем некоторое $a_i$. Найдем максимально возможное $j$ такое, что $i+2^j \le n$. Несложно видеть, что для всех $k < i + 2^j$ вклад $a_i$ в ответ будет равен $a_i$. То есть нужно будет сделать $a_i$ ходов с переходом в $a_{i+2^j}$. Далее найдем такое максимальное $u$, что $2^j+2^u \le n$. Заметим, что $u < j$. Также заметим, что для всех $k$ таких, что $i+2^j \le k < i+2^j+2^u$ вклад $a_i$ в ответ будет равен $2 \cdot a_i$. Далее найдем такое $q$, что $i+2^j+2^u+2^q \le n$. Итак, для каждого элемента $a_i$ мы должны найти соответствующую последовательность степеней двойки. Очевидно, что общая сложность этого процесса $O(n \cdot \log(n))$. Теперь нам нужно с...

Full text and comments »

Идеи на контестах: доказательства или интуиция? Всем привет! При решении нетривиальных задач на контестах существуют два противоположных подхода. Первый (условно назовем его "научный") &mdash; полноценно решать математическую задачу, доказывая все факты и идеи; второй ("магический") &mdash; надеяться на свою интуицию и не тратить время на формальные доказательства, доверяя утверждениям, которые кажутся правильными. Также ко второму подходу относятся reverse-engineering подходы вроде "что мог иметь в виду этот автор задачи" и "что вообще тут можно закодить за время контеста". Раньше я всегда считал, что все применяют исключительно первый подход, а второй &mdash; удел шаманов-экстремалов. Однако все чаще я встречаю людей, даже не понимающих, зачем могут потребоваться формальные доказательства на контестах; так что моя вера в доминирование "научного" подхода пошатнулась. Но я до сих пор уверен, что область применимости этого подхода гораздо шире, чем шаманского (например, командные соревнования, где время за компом очень дорого; ...

Full text and comments »