Hello CodeForces Community,

I’d like to invite you to CodeChef November Cook-Off at https://www.codechef.com/COOK64.

Time: 22nd November 2015 (2130 hrs) to 23rd November 2015 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK64

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Problem Setter: Sergii Nagin
Russian Translator: Sergii Nagin
Editorialist: Sunny Aggarwal
Problem Tester: Istvan Nagy
Mandarin Translator:: Hu Zecong
Contest Admin: Praveen Dhinwa
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

It promises to deliver on an interesting set of algorithmic problems with something for all.

Good Luck! Hope to see you participating!!

426A - Сережа и кружки

Посчитаем сумму всех элементов Sum и значение максимального элемента M. Если Sum - M ≤ S то ответ — да, иначе — нет.

426B - Сережа и развороты

Решим задачу с обратной стороны. Будем пытаться свернуть нашу матрицу как можно больше число раз. Свернуть означает операцию, обратную к описанной в условии. Для проверки, можно ли свернуть матрицу нужно, что бы выполнялись следующие условия:
1). n mod 2 = 0
2). a_i, j = a_{n - i + 1, j} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

425A - Сережа и обмены

Переберем интервал, на котором будет находится максимальная сумма. Для улучшения суммы, мы можем поменять не более K минимальных элемента из интервала на не более K максимальных элементов, не принадлежащих отрезку. Так как n не большое мы можем делать это любым образом, например отсортировать все элементы на интервале по возрастанию и вне интервала по убыванию, а дальше будем менять максимальный элемент из вне интервала на минимальный в интервале по тех пор, пока не поменяем k элементов или не останется не замененных элементов в отрезке или не останется не замененных элементов вне отрезка или операция обмена вообще не будет оптимальной. Сложность авторского решения O(n³·log(n)).

Есть ли у Вас идеи о ток, как решать эту задачу за время O(N) или O(N·log(N)) ?

425B - Сережа и таблица

Заметим, что если у нас есть массив x[1..n], 0 ≤ x_i ≤ 1 и y[1..m], 0 ≤ y_i ≤ 1, то матрица описанная в условии имеет следующий вид a_i, j = x_i xor y_j.
Если n ≤ k, то мы можем перебрать массив x и с помощью жадного алгоритма найти наилучший y. Иначе у нас найдется хотя бы одно i, что мы не должны менять ничего в строке номер i. Таким образом мы можем просто перебрать строку и выбрав ее за x жадно посчитать y. Из всех строк выберем самую оптимальную. Такая строка найдется, потому что ошибок меньше, чем количество столбцов в которых они могут быть.

Под жадным алгоритмом понимается следующий: будем для каждого элемента из y смотреть: лучше ли будет ответ, если определенный бит будет равен 0 или 1. Что бы проще проверять, что оптимальнее можно просто взять текущую строку(i) и посмотреть: сколько бит в ней совпадают с x, а сколько нет. Если совпадающих больше, то y_i = 0, иначе y_i = 1.

425C - Сережа и две последовательности

Для этой задачи будем использовать динамическое программирование: dp_i, j — минимальный номер позиции удаленного элемента во втором массиве, что мы провели первую операцию j раз и удалили из первого массива не более i элементов.

Разберемся теперь как делать переходы. Находясь в состоянии dp_i, j мы можем оставить все как есть и перейти в состояние dp_{i + 1, j}, иными словами сделать dp_{i + 1, j}:  = min(dp_{i + 1, j}, dp_i, j). Что происходит, когда мы делаем первую операцию, при фиксированном префиксе по элемент номер i? Нам нужно найти элемент второго массива с номером больше dp_i, j и равный a_i, пусть это будет элемент номер t, тогда нужно сделать переход dp_{i + 1, j + 1}:  = min(dp_{i + 1, j + 1}, t).

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

425D - Сережа и квадраты

Пускай прямая x = k содержит не более точек. Тогда мы можем просто для каждой пары точек на ней (пускай они будут (k, y₁) и (k, y₂)) проверить: есть ли квадрат, который содержит их как вершины. То есть на нужно проверить: есть ли в наших входных данных пара точек (k - |y₂ - y₁|, y₁) и (k - |y₂ - y₁|, y₂), или пара (k + |y₂ - y₁|, y₁) и (k + |y₂ - y₁|, y₂).

Удалим все просмотренные точки и отразим оставшиеся относительно прямой x = y. Мы получили ситуацию, что каждая прямая x = k содержит не более точек. Решим задачу так же как и в первый раз.

Теперь нужно научится проверять: есть ли пара точек на некоторой прямой. Запишем все эти пары в вектора для тех прямых, где мы хотим проверить. Допустим, мы проверяем все пары для прямой номер k. Пометим в некотором массиве u для всех точек с абсциссой k u_y = k. Теперь пройдем по всем интересующим нас парам (y₁, y₂). Пара нам подходит, только если u_y1 = u_y2 = k.

425E - Сережа и множества

Сначала посмотрим на то, как мы считаем величину F(S). Сперва мы сортируем все интервалы по правому концу, а затем при обходе их в отсортированном порядке смотрим: если текущий интервал не пересекается с последним взятым в множество, то просто возьмем его.

Решение нашей задачи будет использовать эту жадность. Решение задачи, это динамика с параметрами:
1). номер позиции, в которой будут заканчиваться поставленные интервалы.
2). количество поставленных интервалов
3). правая позиция последнего поставленного интервала

Как делать переходы: заметим, что считая dp_{i, count, last} мы можем изменить last только на i, либо вообще не изменять. Давайте посмотрим, что произойдет в обеих случаях. В первом случае last меняется на i, тогда мы должны поставить хотя бы один из интервалов [last + 1, i], [last + 2, i], ..., [i, i], таких интервалов ровно i - last. Что бы узнать количество способов поставить их как нам нужно, можно использовать метод включений-исключений, но на самом деле можно просто взять число 2^i - last - 1. Все остальные интервалы: [1, i], [2, i], ..., [last, i] мы можем брать как хотим, таким образом имеем 2^last способов. Перемножим количества и получим количество переходов из dp_{i, count, last} в dp_{i + 1, count + 1, i}. Если же мы считаем количество переходов из dp_{i, count, last} в dp_{i + 1, count, last}, то просто будем брать число 2^last.

Так же стоит не забыть про случай dp_i, 0, 0. Из которого тоже нужно делать переходы, которые по своей сути тривиальны.

Таким образом мы получили очень простое решение.

Всем привет!

Совсем скоро, 27 апреля в 19:30 MSK состоится Codeforces Round #243, автором которого являюсь я. Это мой одиннадцатый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald) и Ярославу Твердохлебу (KADR) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Разбалловка в первом дивизионе 500-1000-1500-2000-2000. Во втором стандарт.

Gl & hf ! :)

Разбор.
Статистика.

381A - Сережа и Дима

Просто проделаем все операции описанные в условии.

381B - Сережа и лесенка

Посчитаем количества каждого числа. Все различные числа, кроме максимального можно использовать не более 2-х раз. Максимальное же — только 1.

380A - Сережа и префиксы

Сгенерируем первые 100000 чисел. Будем по очереди обратывать запросы, если запрос попадает в точку доабвления 1 числа, то просто выведем его. Иначе посмотрим, какому элементу будет соотвествовать наш, и просто выведм его из предподсчитаного массива.

380B - Сережа и дерево

Сгенерируем дерево, как описано в условии. Для каждого запроса на добавление элементов. Просто для уровня будем добавлять отрезок. На запрос количества элементов будем просто проходить по всем нижним уровням, считая самую левую и самую правую вершину в поддереве. Далее для каждого уровня будем проходить по отрезкам, которые ему принадлежат и для каждого проверять — пересекается ли он с тем, что у нас сгенерирован на текущем этапе. Если да, то просто добавим элемент в множество. Сложность решения O(n·m).

380C - Сережа и скобочки

Будем поддерживать дерево отрезков, в каждой вершине будем хранить:
a_v — максимальную длину скобочной подпоследовательности
b_v — сколько вне нее есть открытых скобок
c_v — сколько вне нее есть закрытых скобок
Если нам нужно объединить две вершины с параметрами (a₁, b₁, c₁) и (a₂, b₂, c₂), то можно пользоваться следующими правилами:
t = min(b₁, c₂)
a = a₁ + a₂ + t
b = b₁ + b₂ - t
c = c₁ + c₂ - t

380D - Сережа и кинотеатр

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

380E - Сережа и деление

Заметим, что на любом конкретном отрезке нас интересует не более 60 чисел. Самое большое войдет в ответ с коэфициентом 1/2, следующее — 1/4, 1/8 и так далее. Таким образом для решения нужно для каждого числа знать: в сколько отрезков оно входит как максимум, как второй максимум, третий, и так далее до 60ого.

Что бы знать такую информацию достаточно найти 60 чисел больше заданого слева и справа. Это можно делать аккуратно написаным set-ом, или dsu.

Теперь имея такую информацию можно посчитать величину, которую элемент несет в ответ. Это не сложно сделать, зная позиции элементов, больших текущего. Пускай позиции элементов слева p₁ > p₂ > ... > p_s1. А позиций справа q₁ < q₂ < ... < q_s2. .

Все детали можно посмотреть в любом прошедшем решении.

Всем привет!

Совсем скоро, 12 января в 19:30 MSK состоится Codeforces Round #223, автором которого являюсь я. Это мой десятый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Это первый раунд в этом году. Кстати, в прошлом году первый раунд для двух дивизионов тоже был мой(а по статистике +1/-1, оказался самым крутым из тех, что я давал). Надеюсь, что в этот раз задачи окажутся еще более интересными для Вас. Получится ли? Узнаем после окончания раунда :)

Gl & hf ! :)

Разбалловка в обоих дивизионах стандартная.

Всем привет.

Хотел бы рассказать про наш(я и M0sTik) проект. Над которым уже некоторое время идет работа.

Суть в том, что я заметил, что ВКонтакте появилось немереное количество публичных страниц. Каждая из них поначалу предоставляет интересные посты, на затем "порох" заканчивается и по сути идет полнейший треш. Плохие группы исчезают, хорошие появляются но пользователям лень переходить из группы в группу, они просто сидят на старых пабликах и читают все, из которых 1/3 это что то нормальное, 1/3 плоский юмор и 1/3 реклама. Да и на новых, хороших пабликах обязательно находится то, что явно не хочется читать.

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

Для тех, кто уже захотел это увидеть, вот ссылка: LNT.

Запущен он был пару дней назад. За чуть больше суток тут уже больше 70 постов. Пост здесь немного отличается от обычного паблика. Если в одном посте обычного паблика лежит в среднем одна фотография, то мы делаем подборки по группам. Почему? Ответ тут, это две причины:
1). Прочитал я, что ВКонтакте делает ограничение на количество публикаций, если не писать ту большую схему, то можно сказать грубо: один пост в десять минут. Этого мало, учитывая объемы постов, с которыми мы работаем, а так же разноплановость аудитории, которой хочется достичь.
2). Причина крайне банальна, не стоит мешать соль с сахаром. Есть люди, которым нравится "парашный" юмор и провокации, есть интеллигенты, а есть и дамы. У каждого свои вкусы. Группировка по пабликам, это хорошее решение, как по мне.
Таким образом за день тут накапливается колоссальное количество публикаций. По текущим результатам подборки выходят не столь и плохими(когда как). Некоторым это может и не нравится, всем не угодишь. Но подборки ориентированы на общую массу.

Теперь по поводу "мозга, сердца и мышц" нашего паблика(алгоритм и код):
Основная работа состоит из нескольких основных кусков:
1). искать
2). выбирать
3). публиковать
Вся техническая часть, и конечно же масса кода лежит в первом и третьем пункте. Второй пункт это основная алгоритмическая часть. Собственно тут еще лежит куча доработок и оптимизаций. Полностью всю логику я не могу тут написать, но суть тут лежит в следующей оптимизационной задаче:
в реальном времени Вам поступает публикация, в которой есть информация, картинки, вложения, лайки, репосты, комментарии, время публикации, размер публики страницы. В короткие сроки( ~ 10 минут), определить хорош ли он, или нет. Как упражнение, можете сами подумать над этой задачей, скажу, что тут можно придумать массу всяких способов выбора. Но в целом, это очень интересно.
Проблема такой задачи, тяжкий и долгий дебаг. Что бы убедиться, что тут публикуется то что нужно , ждать приходится около дня, пока весь анализ выполнит свою работу.

Помимо основной части, тут еще нужно доработать и создать не мало деталей.

Еще чуть чуть, и думаю можно начинать полноценную рекламу всего этого.

Интересно услышать Ваши отзывы по этому поводу.

P.S. Просьба не кричать, что я тут развращаю аудиторию, своими публикациями, я этого очень не хочу :).

Разбор задач Codeforces Round #215

368A - Сережа и вешалка

Будем каждый раз циклом проходить по массиву и искать минимальный элемент, который еще не помечен. Если мы найдем элемент, добавим в ответ и пометим, иначе отнимем от ответа штраф.

368B - Сережа и суффиксы

Предпосчитаем значение ans_i — количество различных элементов на суффиксе с i. Для подсчета пройдемся с конца массива, и будем считать ans_i = ans_i + 1 + new_ai, new_ai равно 1, если элемент a_i еще не встречался и 0 в противном случае.

367A - Сережа и алгоритм

Если разобраться в том, что написано в условии, то станет понятно что алгоритм закончит свою работу, если мы можем получить строку вида: xx, yy, zz, zyxzyxzyx... и все ее циклические сдвиги. Для проверки нужно просто знать количество букв x, y и z по отдельности. Количества можно считать с помощью частичных сумм.

367B - Сережа и анаграммы

Разобьем последовательность на min(n, p) последовательностей. 1-й, (1 + p)-й, (1 + 2·p)-й, ... символ идет в первую последовательность, 2-й, (2 + p)-й, (2 + 2·p)-й... идут во вторую последовательность и так далее. Теперь ответ нужно найти для каждой из них, считая что p = 1. Это можно решить простым методом. Можно пройтись по последовательности слева на право и посчитать количество вхождений каждого числа. Если количества вхождений каждого числа будет совпадать с количеством вхождения того же числа во вторую последовательность, то все ОК.

367C - Сережа и расстановка чисел

Понятно, что нужно набрать как можно больше самых дорогих чисел, что бы из них можно было построить массив. Замечу, что имея n чисел, мы будем иметь m = n·(n - 1) / 2 обязательных связей. Видим, что это граф, в котором нужно сделать Эйлеров путь, добавив как можно меньше ребер. Для n%2 = 1 — все ясно, а для n%2 = 0 нужно добавить n / 2 - 1 дополнительное ребро. Почему? Это Ваше домашнее задание :)

Так же подробное объяснение Вы можете найти здесь.

367D - Сережа и множества

Заменим все множества одним массивом, где элемент — номер множества, которому принадлежит индекс. Теперь возьмем все последовательные отрезки длиной d и найдем множество элементов, которое там не встречается. Понятно, что если в качестве ответа мы выберем подмножество такого множества, то оно нам не подойдет. Запомним все такие "плохие надмножества". Когда мы всех их знаем, найдем все "плохие" множества. Выберем самое большое по количеству элементов не плохое множество. Лучше всего здесь работать с битовыми масками.

367E - Сережа и отрезки

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

Рассмотрим два случая n > m и n ≤ m. Казалось бы нужно для обеих писать динамику за разную сложность, но не сложно показать, что в первом случае ответ 0. Второй случай делается следующей динамикой: dp_i, l, r, i — сколько чисел мы рассмотрели, l, r — только на этом интервале отрезков будет присутствовать i. Так же нам будет нужна вспомогательная динамика s_i, l, i — сколько чисел рассмотрели, l — сколько отрезков уже закрыто, и i ничему не принадлежит. Переходов будет 4, так как на каждом числе у нас может начинаться и заканчиваться не более одного отрезка.

Осталось прилепить число x, это делается достаточно просто: просто добавим еще один параметр 0 / 1 в динамику, было ли у нас такое начало интервала или нет. Учитывая нашу динамику, это не составит труда.

Для уточнения деталей решений просмотрите любое прошедшее системное тестирование решение.

Всем привет!

Совсем скоро, 26 ноября в 19:30 MSK состоится Codeforces Round #215, автором которого являюсь я. Это мой девятый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald), Диме Березину (Berezin), Виталику Аксенову(Aksenov239), Михаилу Мирзаянову (MikeMirzayanov) и Максиму Бевзе(Cenadar) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Разбалловка див1: 500-1000-1500-2000-2000
Разбалловка див2: 500-1000-1500-2000-2500

Gl & hf ! :)

Раунд завершен, спасибо за участие. Извиняюсь за ошибку в задаче A. Надеюсь, что задачи Вам понравились, а нестабильность сегодняшнего соревнования не испортила Вам настроение.
Всем хорошего вечера :)

Так же давайте поздравим rng_58 с достижением 3010 очков рейтинга!

Разбор тут.

358A - Дима и непрерывная линия

Автор — Berezin

Если наша линия имеет самопересечения, то существует пара полу-кругов, которые пересекаются. Пусть точки x₁ < x₂ соединены полу-кругом, и точки x₃ < x₄ соединены полу-кругом. Тогда эти полукруги пересекаются, если выполняется одно из условий:

1). x₁ < x₃ < x₂ < x₄
2). x₃ < x₁ < x₄ < x₂

Перебираем все пары отрезков, таким образом, решение работает за O(n²), что удовлетворяет ограничениям.

358B - Дима и СМС

Автор — Berezin

Очевидно, что добавление случайных символов означает, что мы можем попросту их игнорировать, они не меняют структуру фразы на этапе  < 3word₁ < 3word₂ < 3... word_N < 3. Давайте соберем фразу Димы до вставки случайных символов: s = " < 3" + word1 + " < 3" + ... + " < 3" + wordN + " < 3". пусть i — номер символа в s, который мы сейчас ожидаем. изначально i = 0; будем идти по тексту смс, и если нам встретился символ, который равен s_i просто увеличим i.

Если после прохода по тексту смс |s| ≤ i мы нашли все нужные нам символы, ответ — да, иначе — нет.

358C - Дима и контейнеры

Автор — Berezin

Поскольку мы знаем числа наперед, очевидно, что мы хотим извлечь три максимума. Максимумы можно предпосчитать, определив следующий 0, и пройдясь по всем числам между соседними нулями. Осталось определить, какие операции мы будем применять. Мы обязаны делать извлечения из разных контейнеров, поэтому будем хранить максимумы в вершине стэка, начале очереди, и начале дека (можно и по другому). Нужно определиться, куда какой максимум ложить: к примеру, первый (самый большой) — в стек, второй — в очередь, третий — в начало дека. "мусор" — остальные числа, можно записывать в конец деки. Также нужно предусмотреть случаи, когда между соседними нулями меньше 3 чисел.

358D - Дима и зайцы

Автор — Sereja

Посмотрим на первого зайца: мы либо берем его перед вторым, либо после. Если он взят после второго, то задача от второго зайца и до последнего не зависит от первого зайца, иначе, если мы взяли первого зайца первее, мы получим почти такую же задачу, только скажем, что перед втором зайцем уже что то есть. Таким образом имеем две динамики:
1). d0_i — ответ для суффикса, как для отдельной задачи
2). d1_i — ответ для суффикса, если перед первым зайцем уже что то стоит

переходы:

d0_n = a_n
d1_n = b_n

d0_i = max(a_i + d1_i + 1, b_i + d0_i + 1)
d1_i = max(b_i + d1_i + 1, c_i + d0_i + 1)

Ответ на задачу d0₁.

358E - Дима и пинки

Автор — Sereja

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

Будем перебирать это число. Теперь осталось проверить таблицу зная величину шага K.

Найдем самую левую, а из них самую верхнюю закрашенную клетку. Пусть это (X, Y), тогда после каждого шага Дима мог оказаться только в клетках вида (X + K * a, Y + K * b). Пусть закрашенные клетки такого вида — вершины графа. А последовательности закрашенных клеток, соединяющие их — ребра. Построим граф. Проверим, что нету лишних закрашенных клеток. Проверим граф на связность и наличие Эйлерова пути. Если все условия соблюдены, то мы нашли очередной ответ.

При правильной реализации получим решение со сложностью примерно O(N * N * log(N)). На самом деле она почти никогда не будет достигаться.

Сегодня случайно зашел на эту страничку и увидел интересный факт: IOI 2017 — Iran. Вопросы таковые:
1). а нужно ли будет делать участникам новый паспорт, что бы поехать туда?
2). а сможет ли команда США поехать на этот IOI?

Извиняюсь, если я что то не правильно понял, и теперь поездка в Иран не составляет преград получению визы в США.

Разбор задач Codeforces Round #204

352A - Джефф и цифры

Рассмотрим решение как разбор случаев:
1. Если у нас нету нулей, то ответ -1.
2. Если у нас меньше чем 9 пятерок, то ответ 0.
3. Иначе ответ имеет вид:
4. 1. максимальное количество пятерок, кратное 9
4. 2. все нули, что у нас есть

352B - Джефф и периоды

Будем идти по массиву слева направо. На каждом шаге будем хранить массивы:
1. next_x — последнее вхождение числа x
2. period_x — период, с которым встречается x
3. fail_x — был ли момент, когда число x перестало подходить

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

351A - Джефф и округления

Изначально запомним количество целых чисел — C. Далее округлим все числа вниз, и посчитаем сумму. Теперь мы можем изменить сумму, округлив некоторые числа вверх, при чем не важно какие именно, главное — сколько. Рассмотрим пары, которые могли получится (описанные в условии, первая компонента — число, округленное вниз, вторая — число, округленное вверх):
1. (int, int) (c₁)
2. (int, double) (c₂)
3. (double, int) (c₃)
4. (double, double) (c₄)

Переберем количество пар первого типа c₁. Тогда мы знаем суммарное количество вторых и третьих типов и количество четвертого типа:
1. c₂ + c₃ = C - 2c₁
2. c₄ = N-(c₁ + c₂ + c₃).
Проверим, можно ли получить такие числа (хватит ли нам целых и действительных чисел соответственно). Получим, что мы можем округлить вверх от c₄ до c₄ + c₂ + c₃ чисел. Найдем среди них самое подходящее и обновим ответ.

351B - Джефф и Фурик

Заметим что после каждого шага количество инверсий в перестановке изменится на 1. Перейдем от перестановки к инверсиям — пусть их будет I штук. Понятно, что когда у нас одна инверсия, то ответ — 1. Теперь поймем, как это использовать дальше:
1. понятно, что после хода Джеффа инверсий станет на 1 меньше
2. понятно, что после хода Фурика инверсий станет на 1 меньше с вероятностью 0, 5, и на 1 больше с вероятностью 0, 5.
3. имеем формулу для ответа ans_I = 1 + 1 + ans_{I — 1 — 1} × 0.5 + ans_{I — 1 + 1} × 0.5
4. после преобразования получим ans_I = 4 + ans_I — 2.

351C - Джефф и скобки

Как решить задачу для маленького NM? Просто использовать динамику dp_i, j — минимальная стоимость построить i первых скобок с балансом j. Переходы просты:
1. dp_i, j + a_i + 1 -> dp_{i + 1, j + 1}
2. dp_i, j + b_i + 1 -> dp_{i + 1, j - 1}
3. переходы делаем только, если результирующий баланс не отрицателен
4. стартовые значения dp_0, 0 = 0

В данной задаче можем считать, что баланс никогда не превысит 2N. Доказательство этого факта оставим как домашнее задание. А использую этот факт задачу можно решить возводя матрицу в степень:
1. пусть T_i, j — цена перехода от баланса i к балансу j с помощью N скобок
2. (T^M)_0, 0 — ответ на задачу

351D - Джефф и удаление периодов

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

Количество различных чисел на под отрезке в оффлайне — стандартная задача, описанная на многих ресурсах, решается за O(N^1.5).

Задачу про поиск нужного элемента будем решать аналогичным способом:
1. отсортируем запросы как пары (l_i / 300, r_i), деление целочисленное
2. научимся переходить от отрезка (l, r) к (l - 1, r), (l + 1, r), (l, r - 1), (l, r + 1) за O(1)
3. с помощью таких операция будем переходить от одного отрезка к следующему, в сумме операция выйдет O(N^1.5)

Осталось научится делать изменение отрезка на 1 элемент. Такую задачу решать достаточно просто:
1. заведем deque для всех значений чисел
2. в зависимости от изменения отрезка будем добавлять/удалять элемент в начало/конец соответственного deque
3. проверим, является ли полученный deque арифметической прогрессией. это останется домашним заданием

351E - Джефф и перестановка

Сделаем нулевой шаг, заменим элементы на их модули.

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

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

Теперь поймем, как считать ответ, когда максимумов больше одного. Напишем динамику dp[i][j] — сколько можно получить инверсий, когда мы рассмотрели первых i максимумов и j из них оставили положительными. Из такой динамики не сложно сделать переходы и получить ответ.

И так имеем простой и короткий алгоритм:
1. делаем итерации пока массив не пуст
2. найдем все максимальные элементы
3. с помощью динамики определим знаки, которые нужно поставить элементам
4. удалим элементы из массива

Для уточнения деталей решений просмотрите любое прошедшее системное тестирование решение.

Всем привет!

Совсем скоро, 4 октября в 19:30 MSK состоится Codeforces Round #204, автором которого являюсь я. Это мой восьмой раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald), Евгену Василиву(yvasyliv), Максиму Бевзе(Cenadar) и Максиму Ахмедову(Zlobober) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Разбалловка в первом дивизионе: 1000-1000-1500-2000-2000.
Разбалловка во втором дивизионе: стандарт.

Разбор.

Gl & hf ! :)

Закончился Russian Code Cup, на котором подарили квадрокоптер Parrot Ar.Drone 2.0.

Вопрос следующий: есть ли люди, которые сломали его раньше меня?

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

315B - Сережа и массив
Будем поддерживать все элементы в массиве, но дополнительно заведем переменную add: сколько нужно добавить ко всем элементам. Тогда про добавлении ко всем элементам просто увеличим add. При выводе будем выводить элемент массива + величину add. При обновлении будем ставить элемент равным значению, которое нужно поставить минус текущая величина add.

314A - Сережа и контест
Заметим, что если мы удалили некоторого участника, то мы никогда не удалим участников с меньшими номерами, так как их сумма будет только увеличиваться. Поэтому просто последовательно рассмотрим всех участников, и если участник не подходит, то удалим его.

314B - Сережа и периоды
Понятно, что можно жадно искать количество вхождений 2й строки в первой, но такое решение работает долго. Для ускорения процесса можно искать в первой строке строку, которая задает период второй. А ответ поделить на то, сколько строк нужно для задания второй строки. Далее рассмотрим наш жадный алгоритм. Мы идем по первой строке, пока не встретим первый символ второй строки, потом второй, третий и так далее до последнего, потом снова ищем первый, второй и так по циклу. Понятно, что когда мы дважды окажемся в состоянии, в котором позиции в первой строке соответствует одному символу строки, которая задает период и позиции во второй строке одинаковы, то мы получим период. Когда мы найдем этот период, то просто повторим его столько раз, сколько возможно, что бы каждый раз не считать одну и ту же информацию.

Для лучшего понимая, советую прочитать любое прошедшее решение.

314C - Сережа и подпоследовательности
Понятно, что нужно посчитать сумму произведений элементов всех различных неубывающих подпоследовательностей заданной последовательности. Будем идти по последовательности слева направо и поддерживать массив q[i]: какая сумма всех нужных подпоследовательностей, таких что их последний элемент равен i. Понятно, что если очередное число это x, то нужно поставить q[x] = sum(q[1]+q[2]+...+q[x])*x+x. Ответом на задачу будет сумма всех q[i]. Для нахождения всех сумм можно использовать дерево Фенвика.

314D - Сережа и прямые
Повернем все на 45 градусов с помощью преобразования: (x, y) -> (x', y'): x' = x+y, y' = x-y.
Далее нужно разместить две прямые параллельно осям координат. Отсортируем точки по первой координате. Далее будем использовать бинарный поиск по ответу. Пускай мы зафиксировали некоторое число, теперь нужно проверить хватит ли его, или нет. Заметим, что сейчас нужно разместить две полосы ширины 2 * зафиксированная величина, что бы ими покрыть все точки. Допустим, что некоторая точка будет прилегать к левой стороне вертикальной полосы, далее для всех точек, которые не попадают в полосу найдем минимальную и максимальную вторую координату. Если разница между найденными координатами не больше 2 * зафиксированная величина, то полосы разместить можно, иначе — нет.

Скоро...

Всем привет!

Совсем скоро, 7 июня в 19:30 MSK состоится Codeforces Round #187, автором которого являюсь я. Это мой седьмой раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald), Роману Фурко(Furko) и Аксенову Виталику(Aksenov239) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Разбор.

302A - Евгений и массив
Если длина отрезка — парное число, и количество 1 и -1 по отдельности не меньше половины длины, то ответ положительный.

302B - Евгений и плейлист
Запомним для каждой песни момент, когда она окончится (например частичными суммами). Дальше просто бинарным поиском или двумя указателями найдем максимальный номер песни, что ее конец не меньше заданного числа.

301A - Ярослав и последовательность
С помощью поиска в глубину посчитаем сколько отрицательных чисел мы можем получить. Заметим, что можно сделать либо все числа положительными либо одно число отрицательное(показать это просто, если изменить знак у числа Ч и некоторого набора чисел, а затем у числа У с тем же набором). Если можно получить все положительные числа, то ответом будет просто сумма модулей чисел иначе нужно поменять знак у числа с минимальным значением по модулю.

301B - Ярослав и время
Бинарным поиском будем искать ответ. Далее воспользуемся простым алгоритмом Форда-Белмана. На каждом шагу будем хранить максимальное значение таймера при нахождении персонажа в конкретной вершине, при переходе будем проверять: не умрет ли персонаж при переходе между вершинами. Если переход возможен, то будем обновлять значение конечной вершины. Благодаря тому что a_i<=d и координаты — целые мы не получим циклов.

301C - Ярослав и алгоритм
Нужно воспользоваться тем, что у нас есть знак вопроса(возможно, есть решение, которое не использует этот знак). Поставим знак вопроса в начало строки. Далее будем двигать его пока он не достигнет конца строки. Далее заменим его на два знака вопроса. И будем тянуть их к началу пока перед ним находится число 9, как только мы нашли другую цифру — просто увеличим ее и закончим алгоритм. Если мы дошли до начала строки, то просто поставим 1 в начало и закончим алгоритм.
Смотрите любой прошедший код для большей ясности.

301D - Ярослав и делители
Зададим все пары вида: (x,y) ((d[x]%d[y]==0) || (d[y]%d[x]==0)). Задавать такие можно с помощью решета Эретосфена. Пар заданного вида будет порядка O(n*log(n)) благодаря тому, что нам задана перестановка. Дальше с помощью сортировки подсчетом отсортируем их. Отсортируем заданные на входе отрезки. Дальше для каждого такого отрезка нужно посчитать кол — во вложенных из заданных ранее. Такую задачу можно решить с помощью дерева Фенвика. На каждом шаге добавлять отрезки в порядке сортировки по правому краю. На каждой итерации будем обновлять Дерево Фенвика, которое сможет считать количество начал уже добавленных отрезков на отрезке. С помощью такой информации легко найти ответ. Сложность решения: O(n*log^2(n)), учитывая, что мы используем дерево Фенвика. Константа в решении очень маленькая.

301E - Ярослав и расстановки
Будем строить нужные нам массивы последовательно добавляя числа. Давайте посмотрим на то, какие параметры нам нужны. Во первых, очевидно что нужно хранить количество способов построить массив на уже добавленных числах, во вторых нужно знать общее количество добавленных чисел. Теперь посмотрим на то, что происходит когда мы добавляем новое число(то есть число, большее всех предыдущих в некотором количестве). Понятно, что добавленные числа должны стоять между числами на 1 меньше. При этом если мы поставим 2 новых числа подряд, то между ними должно стоять большее(так как меньшие мы уже расставили). При этом очевидно, что нужно покрыть все предыдущие числа(между которыми должны стоять новодобавленные).Таким образом имеем еще один параметр: количество чисел, между которыми мы можем ставить новые. Таким образом мы имеем динамику от четырех параметров: dp[all][ways][lastnumber][counttoadd].
Переход.
Понятно, что нужно добавлять не менее counttoadd чисел, но как это повлияет на количество способов расставить числа? Все просто. Пусть мы добавили x чисел, тогда количество способов нужно будет умножить на величину Q(x-counttoadd, counttoadd), где Q(x,y) — количество способов расставить x одинаковых шариков в y разных коробок. Q(x,y) = C(x+y-1,y-1), где C(x,y) — биномиальный коэффициент.

Всем привет!

Совсем скоро, 5 мая в 19:30 MSK состоится Codeforces Round #182, автором которого являюсь я. Это мой шестой раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald) и Диме Соболеву(sdya) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

По техническим причинам начало соревнования было сорвано. Приносим извинения, контест будет НЕРЕЙТИНГОВЫМ.

Разбор.

296A - Ярослав и перестановки
Заметим, что после применения операций обмена любая перестановка чисел.
Не сложно понять, что ответ будет положительным, если можно разместить одно число, что бы оно не стояло в соседних клетках.
Таким образом, если некоторое число встретилось С раз, то должно выполнятся условие С<=(n+1)/2.
296B - Ярослав и две строки
Будем решать обратную задачу: посчитать количество способов сделать сравнимые пары.
Для начала посчитаем количество способов сделать первую строку меньше равной второй.
Это количество равно произведению количества способов сделать это для каждой позиции по отдельности,так как они все позиции независимы. Посчитаем такую же величину, но когда вторая строка меньше-равна первой. И аналогично посчитаем количество способов сделать две строки равными. Для каждого символа величины можно считать простым циклом.
Теперь возьмем величину 10 в степени количества знаков вопроса во входном файле и отнимем полученный ответ на обратную задачу, это и будет ответом.
295A - Егор и массив
Для того, что бы прибавить значение d на отрезке [x,y] достаточно завести массив b и поставить значения
b[x] += d
b[y+1] -= d
Дальше за один проход по массиву легко восстанавливаются все числа.
Применим данный метод дважды: сначала для запросов, а потом для операций(зная сколько раз мы ее выполним).
295B - Егор и граф
Для решения задачи нужно хорошо понимать принцип работы алгоритма Флойда.
Общий вид алгоритма Флойда:
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
То есть на каждом шаге мы пытаемся пропустить путь через вершину К.
Будем не удалять вершины, а добавлять(идя с конца).
На каждом шаге будем пробовать пропустить путь между всеми вершинами через новую.
Таким образом мы получим решение, работающее за кубическое время.
295C - Егор и друзья
Заметим, что на каждом шаге нас интересует только положение лодки(номер берега) и количество людей веса 50 и 100 на каждом береге. При чем количество людей на одном береге полностью определяется через другой.
Для поиска минимального количества переправ будем использовать волновой алгоритм, основанный на этом состоянии.
Для нахождения количества способов просто добавим сумму всех переходов в состояние при переходе будем переносить все способы из одного состояния в другое умножая на количество способов выбрать людей, которые нужны для перехода из одного состояний в другое.
295D - Егор и пещеры
Будем пользоваться динамическим программированием: dp[i][j] — сколько существует способов построить фигуру, что в строке i будет ровно j столбцов занятыми черными клетками и всем, что между ними. При этом фигура должная не убывать (иными словами мы берем только верхнюю часть фигуры).
Как делать переход? Заметим, что dp[i][j] = 1+dp[i-1][2] * (j-2+1)+ ... +dp[i-1][l] * (j-l+1)+ ... +dp[i-1][j].
Распишем это: dp[i][j] = 1+dp[i-1][2] * j+ ... +dp[i-1][l] * j+ ... +dp[i-1][j] * j — dp[i-1][2] * 1 — dp[i-1][3] * 2 — ... — dp[i-1][j] * (j-1).
Понятно, что если завести частичные сумму, то данные величины считать становится очень просто.
Как посчитать полный ответ: будем перебирать номер максимального подходящего t(обозначенного в условии).
Теперь единственное отличие, это то что следующая строка должна содержать строго меньше столбцов. То есть имеем аналогичный переход, с -1 слагаемым.
Так же заметим, что зафиксировав "основу" мы должны домножить количество способов на число способов разместить ее на плоскости, то есть основу шириной j мы можем поставить (m-j+1) способами.
295E - Ярослав и точки
Научимся решать задачу: найти сумму расстояний между точками.
Если расписать, что происходит при добавлении одной точки, то получим формулу: x_i*(2*i-n) Где x_i — отсортированные координаты, а n общее количество точек.
Научимся зная ответы для двух отрезков точек знать ответ для их объединения.
Понятно, что для подсчета такой информации нужно всего лишь сложить два ответа,
и добавить сумму координат первого множества умноженное на некоторое число и
и добавить сумму координат второго множества умноженное на некоторое, возможно другое, число.
Таким образом зная ответы для некоторых отрезков общий ответ.
Будем использовать корневую декомпозицию или декартово дерево для хранения таких отрезков.
Не сложно понять, что вставка и удаление делается достаточно быстро для этих структур.
Например для корневой декомпозиции можно каждый раз просто вырезать и вставлять точку в нужные отрезки, а если множество стало содержать длинные отрезки или много отрезков, то просто перестроим его заново. Асимптотика решения не меняется.

Всем привет!

Совсем скоро, 11 апреля в 19:30 MSK состоится Codeforces Round #179, автором которого являюсь я. Это мой пятый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Разбалловка в первом дивизионе стандартная, а во втором: 500-1500-1500-2000-2500.

Gl & hf ! :)

Контест завершен. Надеюсь вам понравились задачи.

Победители в первом дивизионе:
1). marcina007
2). yeputons
3). gawry
4). KADR
5). enot110

Победители во втором дивизионе:
1). goie
2). Koblyk
3). Beriand

Идеи решений тут.

Всем привет!

Совсем скоро, 13 февраля в 19:30 MSK состоится Codeforces Round #167, автором которого являюсь я. Это мой четверый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Жене Соболеву и Диме Соболеву (Seyaua и sdya) за помощь в тестировании задач, а также Геральду Агапову (Gerald) за помощь в подготовке раунда. Отдельное спасибо Марии Беловой (Delinur) за перевод условий на английский.

Разбалловка стандартная в обоих дивизионах.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, поздравляю победителей див1:

1). tmt514
2). tourist
3). scott_wu
4). rng_58
5). dreamoon_love_AA

И победителей див2:
1). yefllower
2). Harlos
3). pseudopodia

Разбор по ссылке.

272A - Дима и друзья

We will bruteforce number of fingers that will be show Dima, then if total sum of fingers = 1 modulo (n+1), Dima will clean the room. So we should increase answer if the remaining part after division by (n+1) is not 1.

272B - Дима и последовательность
First of all — f(i) is number of ones in binary presentation of number. We will repair all numbers to functions of them. Now we have to find number of pairs of equal numbers. Lets Q[i] — number of numbers with i bits, the answer will be sum of values Q[i]*(Q[i]-1)/2 for all i.

273A - Дима и лесенка
Lets L will be the answer after last block, last block was (w1, h1), next block is (w2, h2). Next answer will be max(L+h1, A[w2]), where A — given array. At the beggining we can suppose that L = 0, w1 = 0, h1 = 0.

273B - Дима и две последовательности
Not hard to understand that answer will be (number of numbers with first coordinate = 1)! * (number of numbers with first coordinate = 2)! * ... * (number of numbers with first coordinate = 10^9)!/(2^(number of such i = 1..n, that Ai=Bi)). The only problem was to divide number with non prime modulo, it can be easely done if we will count number of prime mulpiplies=2 in all factorials. Then we can simply substract number that we need and multiply answer for some power of 2.

273C - Дима и кони
Not hard to understand that we have undirected graph. Lets color all vetexes in one color. Then we will find some vertex that is incorrect. We will change color of this vertex, and repeat our search, while it is possible. After every move number of bad edges will be decrease by 1 or 2, so our cycle will end in not more then M operations. So solutions always exists and we need to change some vertex not more then M times, so we will take queue of bad vertexes and simply make all operations of changes.

273D - Дима и фигура
Good picture is connected figure that saticfy next condition: most left coordinates in every row of figure vere we have some cells will be almost-ternary, we have the same situation with right side, but here we have another sign. So it is not hard to write dp[i][j1][j2][m1][m2] numbr of figures printed of field size i*m, where last row contain all cells from j1 to j2, the most left coordinate will be m1, the most right coordinate will be m2. But it is not enough. We have to rewrite it in way that m1 will mean — was there some rows j and j+1 that most left coordinate if row j is bigger then most left coordinate in j+1. So now it is not hard to write solution with coplexity O(n*m*m*m*m). But we should optimize transfer to O(1), is can be done using precalculations of sums on some rectangels.

273E - Дима и игра
will be added soon.

Lets discuss problems here.

262A - Рома и счастливые цифры

Просто выполним все то, что просят в условии.

262B - Рома и замена знаков

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

261A - Максим и скидки

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

261B - Максим и ресторан
Если все люди поместятся в ресторан, то выведем ответ — .n. Иначе зафиксируем человека, который не сможет поместиться в ресторан. Напишем ДП: d[i,j,s] сколько существует способов набрать из i первых людей j, что их ширина равна s.
Далее переберем числа i и s и посчитаем, сколько существует способов, что i человек с общей шириной s придут до зафиксированого человека, при том что зафиксированый не влезет. Количество способов такого равна d[n,i,s]*i! далее считаем количество окончаний, их (n-i-1)! перемножаем и добавляем к количеству умноженым на i — количество людей которые поместятся. В конце сумму поделим на n! — общее количество способов.

261C - Максим и матрица
Если выписать последовательность сумм(f[n]), которые выходят на nтом шагу, то можно заметить f[n] = f[n/2], n%2=0, f[n] = f[n-1]*2, n%2=1. Иными словами f[n] = 2^(bit_count(n)-1). Теперь нужно посчитать, сколько чисел больше 1 и меньше-равно (заданного +1) содержат в себе log2(T)+1 двоичных бит. Это стандартная задача, решается с помощью дп. Будем идти по двоичному представлению числа и считать количество чисел, у которых совпадает некоторый префикс, а следующий бит — меньше. Количество окончаний это биномиальный коефициент, с помощью которого считаем, сколько последовательностей из 0 и 1 длины Н содержат К единичных бит.

261D - Максим и возрастающая подпоследовательность

Заведем дп, q[i][j] в какой позиции массива мы можем закончить нашу последовательность, если последнее число в ней i, а длина j. Переход:
будем переносить q[i][j] -> q[i+1][j]. Так как не ухудшим результат.
будем переносить q[i][j] -> q[i+1][next[q[i][j]][i+1]], где next[x][y] — первое вхождения числа y после позиции x. Массив next нужно предподсчитать заранее.

261E - Максим и калькулятор

Сгенирируем все числа меньше равно R, которые содержат в себе простые множители не превышающие 100. Таких чисел порядка 3000000. Теперь будем поддерживать такое ДП. Сколько нужно операций умножения над первыми i числами, что бы получить число j. А так же отдельный массив, где для каждого числа будем хранить общее число умножений и увеличений на 1. Теперь нужно быстро обновлять динамику в первом случае. Будем двумя указателями (число которым обновляем и число которое обновляем) и будем выполнять переход. Указатели будем перемещать слева на право, что бы можно было умножить на одно число два раза, но не добавлять еще один цикл. Дальше будем проходить по нашему текущему дп, и обновлять наш массив, считая что мы сделали количество увеличений равное последнему числу, на которое умножали. .В конце пройдемся по всем числам и найдем те, в которых значение в массиве не больше P, а величина числа не меньше L.

Всем привет!

Совсем скоро, 13 января в 19:30 MSK состоится Codeforces Round #160, автором которого являюсь я. Это мой третий раунд на Codeforces и я надеюсь, что не последний.

Спасибо Жене Соболеву и Диме Соболеву (Seyaua и sdya) за помощь в тестировании задач, а также Геральду Агапову (Gerald) за помощь в подготовке раунда. Отдельное спасибо Марии Беловой (Delinur) за перевод условий на английский.

Разбалловка стандартная в обеих дивизионах.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, надеюсь вам понравилось :)

Поздравляю победителей див1:
1). PavelKunyavskiy
2). Dmitry_Egorov
3). Nerevar
4). Egor
4). gawry

И победителей див2:
1). Pad
2). nirvanafreak
3). pablobce

Разбор по ссылке.

255A - Тренировки Егора

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

255B - Разбор кода

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

256A - Почти арифметическая прогрессия

Заметим, что ответ это длина последовательности: a, b, a, b, ... где a и b — некоторые целые числа. Зафиксируем одно число (допустим a), будем перебирать число b, и считать какой мы получим ответ, если это будет последнее число в последовательности. Заметим, что для фиксированных a, b — ответ считается жадно. Так же будем действовать и тут. Будем искать последнее вхождение числа b до зафиксированного, что между ними есть число a, и будем брать ответ как длина до найденного числа +2 (икасть будем с помощью метода двух указателей). Так же нужно рассмотреть случай, когда это будет 1е или 2е вхождение в последовательность.
Так же существует решение с помощью динамического программирования.
Асимптотика обоих решений O(n^2).
Буду очень рад, если кто то напишет решение с лучшей асимптотикой.

256B - Остап и квадрат

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

256C - Фурло и Рубло и Игра

Заметим, что после первого хода любая кучка превратится в кучку размера не большего чем 1000000. Будем считать функцию Гранди для чисел меньше 1000000. Функция Гранди очень маленькая, по этому можно заводить частичные суммы для каждого вида Функции, что бы быстро говорить какие функции есть на отрезке, а каких нету. Зная ответы для маленьких не сложно посчитать ответ для всех кучек.

256D - Вруны и Сережа

Если человек говорит число x, и в общем число x сказало x человек, то мы не можем сказать: врет этот человек или нет.

Теперь понятно, какие последовательности нам подходят. Будем считать их с помощью динамики: dp[n][m][k], n — какие ответы мы сейчас рассматриваем, m — сколько человек уже сказали свой ответ, k — сколько среди поставленных точно врут.
Переход:
dp[n][m][k]*cnk[N-m][n] -> dp[n+1][m+n][k]
dp[n][m][k]*cnk[N-m][p] -> dp[n+1][m+p][k+p] p = 1 .. N, p != n.
Мы считаем, что N — количество людей всего. Такая ДП не укладывается по времени, по этому нужно завести массив констант. Так как N — степень двойки, массив выйдет не большой.

256E - Счастливые массивы

Решение задачи — дерево отрезков. Будем хранить в вершине динамику f[i,j] — какое количество способов заменит нули на отрезке который соответствует вершине, что в начале отрезка будет число i, а в конце j.

При нормальной реализации данный подход без проблем заходит по времени.