Hey everyone!

At the Google Kick Start Round B 2021 I faced a very strange thing. After submitting solution for problem B "Longest Progression" I got RE on the large test. That was weird, because for my solution there was no much difference between small and large tests. But there was one static array in my solution of size (1 << 17). I double-checked that $$$N$$$ is not greater than $$$10^5$$$ in the problem statement. I had no idea, but finally I replaced the array with std::vector of dynamic size and the solution passed.

Then I submitted a question: "Some of my solutions got RE on the large test. After changing the static size of (1 << 17) which is larger than 10^5 to dynamic STL vector of size N the same solution passed this test. Probably something is wrong with the limits specified in the problem statement. Is that so?".

And the response was: "There is no problem with the limit. Please read the problem statement more carefully. Consider looking at the limits and the sample cases if those might help.".

After that I've looked at the problem statement again and the limit for $$$N$$$ was $$$3 \times 10^5$$$. I cannot believe I haven't noticed the $$$3 \times$$$ in the problem statement so many times.

Is there anyone, who faced the same problem during the contest? Or is it time for me to see a doctor?

UPD. I've finally managed to find out what happened. I've picked the wrong problem while asking a question. And for this problem the limits were initially incorrect. That explains everything except for three things:

• Why the one who responded to me haven't guessed that I'm probably talking about another problem? The was only one problem with wrong limits in the problem statement.

• How could I know that I need to refresh the problem statement (without going to questions tab)?

• What is the logic behind ordering the problems in the following order B, A, D, C at the questions tab?

Probably I expect too much from Google Kick Start, but I was left with a lot of questions.

478A - Initial Bet

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

478B - Random Teams

Если переформулировать задачу в терминах теории графов, то ее можно сформулировать следующим образом: Имеется граф, состоящий из n вершин и m компонент связности. Внутри каждой компоненты связности каждая пара вершин этой компоненты связана ребром. Другими словами, каждая компонента связности является полносвязной. Какое наименьшее и какое наибольшее количество ребер может содержать такой граф? Рассмотрим процесс построения графа из n вершин и m компонент связности. Для начала предположим, что каждая из m компонент содержит ровно одну вершину. Остается распределить оставшиеся n - m вершин так, чтобы минимизировать или максимизировать количество ребер. Заметим, что при добавлении новой вершины в компоненту связности размера k, количество ребер увеличивается на k (новая вершина соединяется с каждой из уже существующих одним ребром). Следовательно, для того, чтобы минимизировать количество образованных ребер на каждом шаге, требуется каждый раз добавлять вершину в компоненту связности наименьшего размера. Если действовать согласно такой стратегии, то после распределения вершин по компонентам связности появится компонент размера и компонент размера . Аналогично, для того, чтобы максимизировать количество ребер, на каждом шаге необходимо добавлять очередную вершину в компонентну связности наибольшего размера. Если действовать согласно такой стратегии, то образуется одна компонента связности размера n - m + 1, оставшиеся компоненты связности будут состоять из одной вершины. Зная количество компонент связности и их размеры, можно посчитать общее количество ребер. Для полносвязной компоненты, состоящей из k вершин, количество ребер равняется . Следует помнить про необходимость использовать 64-битный тип данных для хранения количества ребер, которое квадратично зависит от значения n.

478C - Table Decorations

Рассмотрим ситуацию, когда величина max(r, g, b) - min(r, g, b) ≤ 1, в таком случае, очевидно, ответ равен . Мы всегда можем украсить столько столов тремя воздушными шарами разных цветов. Очевидно, что оставшееся количество шаров будет меньше трех и, следовательно, не может быть использовано для украшения стола в любом случае. Все оставшиеся случаи имеет смысл свести к ранее рассмотренному. Если есть один цвет такой, что количество шариков этого цвета больше, чем суммарное количество шариков для оставшихся двух цветов, то всега выгодно украшать стол двумя шарами этого цвета и одним шаром того из оставшихся цветов, которого больше на данный момент. Далее можно разными способами группировать операции и выполнять более одной операции за раз. Другим решением можно назвать тот факт, что ответ будет отличен от , но только тогда, когда max(r, g, b) ≥ 2·(r + g + b - max(r, g, b)), в таком случае ответ r + g + b - max(r, g, b). В этом случае шарики двух наиболее редких цветов закончатся раньше, чем шарики одного наиболее популярного, если украшать каждый стол с использованием двух шариков наиболее популярного цвета.

478D - Red-Green Towers

Для начала можно заметить, что для того, чтобы построить красно-зеленую башню высоты h потребуется кубиков. Следовательно, высота полученной башни для заданных ограничений никогда не превысит 893. Эту высоту можно определить заранее, если предположить, что все кубики одного цвета. Попробуйте доказать это самостоятельно. Далее можно решить задачу с использованием динамического программирования. Пусть F(t, r) — количество способов собрать башню наибольшей высоты, если собрано t верхних этажей и остались незадействованными r красных кубиков. Среди аргументов функции нет количества оставшихся зеленых кубиков g — его можно однозначно определить из значений t и r: , где r₀ и g₀ — изначальное количество красных и зеленых кубиков, соответственно. Ну а дальше следует рассмотреть лишь два перехода: пострить t + 1-ый уровень из красных или из зеленых кубиков: F(t, r) = F(t + 1, r - t) + F(t + 1, r). Очевидно, кешировать данные в массиве размера 893 × 2·10⁵ — не лучшая затея. В таком случае можно подсчитывать значения функции для всех значений t от 0 до h, храня в памяти только значения для текущего значения t и для предыдущего, от которого оно будет зависеть.

478E - Wavy numbers

Для решения этой задачи необходимо было заметить, что волнистых чисел на интервале от 0 до 10⁷ намного меньше, чем 10⁷. В таком случае можно решить задачу с использованием подхода meet-in-the-middle. То есть отдельно решить эту задачу для первых семи цифр ответа, и для последних семи цифр ответа. Для этого потребуется отдельно сгенерировать все волнистые числа на интервале от 0 до 10⁷, которые начинаются с возрастания двух соседних цифр, и аналогичные волнистые числа, которые начинаются с убывания двух соседних цифр. Дальше для каждой первой половины мы можем посчитать r_l — ее остаток от деления на n и, затем, определить количество подходящих вторых половин, которые должны иметь остаток от деления равный .

Для задачи было установлено ограничение времени равное 1.5 сек. На самом деле, если написать решение с подходом meet-in-the-middle достаточно оптимально, то решению потребуется гораздо меньше времени. Приведенная авторская реализация (8271836) умеет решать аналогичную задачу для 1 ≤ n, k ≤ 10¹⁶ примерно за 2.5 сек.

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

16 октября 2014 года в 19:30 MSK состоится очередной раунд Codeforces #273 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Автор задач: pkhaustov (Хаустов Павел, Россия, Томск, Томский ПУ)

За подготовку раунда отдельное спасибо коллективу Codeforces и, в частности, Максиму Ахмедову (Zlobober) за помощь в подготовке и Марии Беловой (Delinur) за перевод условий задач на английский язык.

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

Распределение баллов по задачам: 500-1000-1500-2000-2500

UPD: Старт сдвинут на 10 минут

Желаю удачи всем участникам!

424A - Паша и приседания

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

424B - Город-миллионер

Можно отсортировать все города по возрастанию расстояния до города Томска. После чего требуется найти наименьший индекс t, для которого общее население p₀ + p₁ + ... + p_t >  = 10⁶. Для такого t значение d_t является ответом. Ограничения на N позволяют использовать сортировку с асимптотикой O(N²) или любое другое решение с такой асимптотикой.

424C - Волшебные формулы

Рассмотрим следующие формулы:

Пусть . Посчитаем значение этой функции для всех значений i (0 ≤ i ≤ n). Это можно сделать за O(n), используя соотношение .

Преобразуем c_i:

Также:

Таким образом:

Это означает, что если n / i нечетно, , иначе — . c_i может быть вычислено за O(1), благодаря чему итоговая асимптотика решения — O(n).

424D - Биатлонная трасса

Из-за лояльных ограничений по времени для Java, некоторые решения с асимптотикой O(N⁴) были зачтены. Авторское решение имеет сложность O(N³logN). Основная идея — зафиксировать верхнюю и нижнюю границы. Затем, используя какой-либо абстрактный тип данных, для каждой правой границы найти наиболее подходящую левую границу за время не хуже O(logN). Например, можно использовать контейнер set в языке программирования C++ и его метод lower_bound. Для лучшего понимания можно посмотреть на следующее изображение.

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

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

424E - Цветная Jenga

Классическая задача на динамическое программирование для нахождения математического ожидания.

Определим некоторую функцию F(S) для некоторого состояния S — математическое ожидание количества минут до конца игры, если мы находимся в этом состоянии. Для каждого цвета мы можем вычислить вероятность, с которой этот цвет выпадет при броске кубика по тривиальной формуле , где c — количество граней такого цвета на кубике. Теперь требуется найти вероятность того, что мы останемся в том же состоянии еще хотя бы на одну минуту. Это можно сделать сложив вероятность выпадения черной грани и вероятности выпадения цветов, блоки цвета которых нельзя достать из башни на данный момент. Теперь мы можем найти значение это функции используя формулу:

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

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

25 апреля в 11:00 MSK состоится очередной раунд Codeforces #242 для участников из 2 дивизиона. Традиционно, участники из первого дивизиона могут написать соревнование вне конкурса.

Подготовкой задач занимался коллектив программистов Национального исследовательского Томского политехнического университета: Павел Хаустов (pkhaustov), Олеся Голуб (Taube), Николай Кузиванов (Carups), Дмитрий Саввинов (Dsavvinov), Алексей Ветров (noxwell).

Отдельное спасибо Владимиру Чалышеву (cmd) и Алексею Дергунову (dalex) за огромную помощь в подготовке раунда.

Кроме того, выражаем благодарность коллективу Codeforces и, в частности, Геральду Агапову (Gerald) за помощь в подготовке и Марии Беловой (Delinur) за перевод условий задач на английский язык.

Распределение баллов по задачам: 500-1000-1500-2500-3000

Желаем всем участникам удачи!

Вот и пролетела вереница новогодних праздников, большинство из нас неохотно возвращаются к трудовым будням. Кроме того, конец новогодних праздников совмещен и с началом последнего этапа голосования "Итоги 2012 года" на сайте проекта SnarkNews. Собственно, об этом событии мне бы и хотелось поговорить в этом посте.

Казалось бы, обычное голосование, которое вполне может быть результатом субъективности и чувства юмора участников олимпиадного движения. Но если взглянуть на это голосование под хотя бы сколько-нибудь отличным углом, то в нем можно увидеть неплохую попытку собрать в одном месте все самые значимые события и результаты прошедшего года, выделить людей, которые внесли наиболее значимый вклад в олимпиадное движение. Хотелось бы попросить не относиться пренебрежительно к такого рода голосованию. Если нет желания голосовать объективно — лучше просто не голосуйте.

Год выдался крайне богатым на события: ИТМО стал четырехкратным чемпионом Мира, Евгений Капун стал третьим в истории двукратным абсолютным чемпионом Мира, Роман Андреев стал победителем Facebook Hacker Cup 2012, Егор Куликов стал победителем TopCoder Open 2012, Геннадий Короткевич поступил в ИТМО, Владислав Епифанов первым откликнулся на слова Петра Митричева "Попробуйте, отберите в следующем году" на Russian Code Сup, школьники сборной России отрешались на четыре золотых медали на IOI, СпбГУ #4 уверенно победили на Всесибирской олимпиаде, а под конец года настоящий action развернулся в последние минуты заморозки на NEERC, победителем которого в третий раз подряд стала команда Национального исследовательского университета ИТМО. И это — только самые крупные победы команд и участников из России на сравнительно крупных соревнованиях. Если приглядеться повнимательнее, то можно вспомнить несколько не столь приятных для постсоветского сообщества олимпиадных программистов событий, таких как победа Johnny Ho на IOI 2012, победа Китая в суммарном зачете все того же IOI 2012, просто необъяснимуя неудача MIPT The Sun на NEERC с несданной задачей G, "железное" доминирование Saratov SU #3 над другими командами этого университета все на том же NEERC 2012. Если говорить о чем-то более радужном, то можно также отметить огромное количество раундов в 2012 году на Codeforces, золотое выступление MIPT Waterogers на финале ACM ICPC 2012, два Белорусских комплекта медалей все на том же финале ACM ICPC 2012, проведенные VK Cup и AI Cup. Об этих событиях помнят все, они обсуждались, многие из них неоднократно становились причинами разного рода шуток. Но есть события и, связанные с ними, люди, которые не столь заметны и обсуждаемы, насколько они этого заслуживают, исходя из их важности для нас и нашего сообщества. На одном из таких событий я бы и хотел сделать серьезный акцент. Но... Обо всем по порядку.

На дворе начало августа. Близятся Петрозаводские сборы. Я усиленно готовлю контест для этих сборов. Во время подготовки я понимаю, что одну из задач неплохо бы было сделать интерактивной, но я не имею ни малейшего представления о том, как же грамотно подготовить интерактивную задачу. Я пытаюсь придумать хоть сколько-нибудь подходящую замену интерактивности, но получается какая-то ерунда. Как итог, одна из малопригодных замен интерактивности оформляется в polygon. К моему счастью, Павел Абизяев (Nyatl) и Владимир Чалышев (cmd) согласились мне помочь с подготовкой контеста (за что им отдельное "спасибо"). От Паши Абизяева я узнал о том, что уже в сентябре планируется Гран-При Удмуртии, автором которого является он сам (если я не ошибаюсь, идея одной из задач принадлежит его тренеру — Юрию Когану). И, казалось бы, нет в этом ничего удивительного, это — далеко не первый Гран-При Удмуртии, в подготовке которого участвует Паша Абизяев. Но дело в том, что контест этот — особенный, все десять предложенных в нем задач — интерактивные. Да, Паша сам разобрался с тем, как разрабатываются интерактивные задачи, сам подготовил десять интерактивных задач достаточно высокой сложности (за исключением окончательных условий, с ними отдельная песня была). Более того, он лично предложил модифицированные варианты этих же задач для второго дивизиона Открытого кубка, опять же, всех десяти. Чтобы больше не возвращаться к теме моего контеста, скажу, что с непосредственной помощью Паши Абизяева мы подготовили интерактивный вариант той самой злополучной задачи и дали его на Петрозаводские сборы. Да, не все так гладко прошло на контесте, как хотелось бы, но эта задача стала первой интерактивной задачей в истории Петрозаводских сборов. С ее помощью мы предупредили несколько серьезных ошибок на будущем Гран-При Удмуртии. Кроме того, тренер Саратовского ГУ и один из авторов проекта Codeforces — Михаил Мирзаянов на фоне всей этой Петрозаводской шумихи на тему интерактивных задач опубликовал на Codeforces пост, в котором описал свой взгляд на интерактивные задачи и поднял на обсуждение детали реализации интерактивных задач. Позже, это вылилось в модификацию библиотеки testlib и проекта polygon, а также первую интерактивную задачу на Саратовском четвертьфинале.

Стоит отметить, что Паша до последнего заботился о том, чтобы участники получали наиболее объективные и информативные вердикты. Буквально за считанные часы до начала Гран-При Удмуртии в ejudge еще вносились изменения с целью исправить неправильные вердикты, которые он периодически выдавал. Удивительно, но контест (не смотря на достаточно большую очередь тестирования, что вполне объясняется интерактивностью) удался на славу. После него — море положительных отзывов и огромное количество обсуждений на тему интерактивных задач. Стоит ведь задуматься над тем, что такое интерактивные задачи. Это — огромный пласт принципиально новых задач, решать и тестировать которые намного сложнее. Многие из этих задач без интерактивности вообще не имеют смысла. Без всякого преувеличения этот Гран-При можно назвать настоящим прорывом. Это был невероятный по сложности и времени подготовки эксперимент, который дал огромный толчок развитию спортивного программирования. Что касается самого Паши Абизяева, то мне бы хотелось отметить его невероятное умение придумывать задачи. Он видит задачи во всем, что его окружает. Фанатизм? Может быть. В плане участия в олимпиадах он не был настолько же заметен, насколько и такие гранды подготовки контестов, как Андрей Станкевич и Петр Митричев, но как автора задач я бы вполне мог поставить его с ними в один ряд. Если посмотреть на тот проблемсет, который удался ему на последнем Гран-При Удмуртии, то можно заметить, что кроме двух задач, каждую из задач решила хотя бы одна команда, но лишь одной команде удалось решить хотя бы половину задач. А одна из задач и вовсе ушла на Новогодний "Простой" контест.

Возвращаясь к теме, которую я затрагивал в самом начале этого поста, я бы хотел сказать, что этот проблемсет действительно заслуживает звания "Лучший проблемсет 2012 года". Хотелось бы, чтобы такая инициатива и такой труд были вознаграждены хотя бы таким образом. Все сравнимые с ним проблемсеты готовились целыми группами разработчиков, в то время как этот (за исключением окончательных текстов условий) Паша подготовил сам, без всякой помощи. Можно говорить о том, что это — агитация. Словом, я проконсультировался с Олегом Богдановичем, агитация отнюдь не запрещается. Моей основной задачей было обратить внимание общества на этот проблемсет и его важность для сообщества спортивных программистов.

На этом, господа, мои мысли и мой словарный запас исчерпаны. Спасибо за внимание.

Задача A (div2) — Шкафы

Автор: max777alex

В этой задаче можно рассмотреть независимо все левые дверцы шкафов и, аналогично, все правые. Очевидно, чтобы привести все левые дверцы шкафов в одинаковое положение, нужно определить какое из двух состояний ("левая дверца открыта" или "левая дверца закрыта") встречается чаще. Все левые дверцы, которые находятся в другом состоянии требуется привести к этому. Аналогично надо поступить и с правыми дверцами. Если аккуратно посчитать в таком случае количество операций изменения состояния дверцы, то это оно и будет ответом.

Задача B (div2) — Котенок Гав

Авторы: max777alex, pkhaustov

В данной задаче требовалось найти минимальное положительное N-значное число, которое делится без остатка на 2, 3, 5 и 7. Очевидно, раз все эти четыре числа являются простыми, то число, которое делится на все эти четыре числа, должно делиться на их произведение 2·3·5·7 = 210. Для N < 3 такого числа не существует. Для N = 3, конечно же, ответ равен 210. Для N > 3 следуем следующему алгоритму.

Найдем остаток R от деления 10^N - 1 на 210. Далее требуется добавить 210 - R к 10^N - 1, чтобы получилось число, кратное 210. Учитывая, что 0 ≤ R < 210, получаем, что последние три разряда числа определяются значением R, а оставшиеся разряды — совпадают с соответствующими разрядами числа 10^N - 1.

Можно также было заметить закономерность для последних трех разрядов с изменением N и заменить вычисления остатков аккуратным разбором случаев.

Задача A (Div1), C (div2) — Электроник-футболист

Авторы: am-real

Для начала временно избавимся от радиуса мяча — сдвинем верхнюю стену на радиус вниз. Мяч, в таком случае, можно считать материальной точкой. Штанги не трогаем. Отразим центр мяча относительно сдвинутой верхней стены. Соединим полученный отраженный центр мяча и точку (0, y₁ + r).

Далее остается аккуратно определить, не касается ли мяч левой стены. Очевидно, что точкой стены, наиболее близко лежащей к траектории центра мяча, будет штанга (0, y₂). Таким образом достаточно проверить расстояние от этой точки до траектории мяча. Если оно меньше радиуса, значит ответа нет, иначе — точка пересечения проведенной ранее линии и сдвинутой на радиус вниз стеной и будет ответом.

Если целиться выше точки (0, y₁ + r), траектория центра мяча только приблизится к штанге (0, y₂), поэтому целиться в другие точки смысла не имеет.

Задача B (Div1), D (div2) — Конфеты — каждому!

Автор: pkhaustov

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

С ростом количества изначально имеющихся с собой конфет, время, которое требуется для угощения всех жителей может либо не изменяться, либо уменьшаться. Следовательно, здесь применим бинарный поиск по количеству конфет. С помощью бинарного поиска закрепим количество конфет, которые мы изначально взяли с собой. Идем слева направо (от первого участка, до последнего). Если находимся на участке с магазином — обязательно покупаем конфеты (денег у нас бесконечно много, значит, нет смысла не покупать конфеты). Если мы находимся на участке с домом, то при наличии конфет — угощаем жителей этого дома. Если же конфет у нас нет, то пропускам этот дом. Несложно доказать, что возвращаться назад выгодно только тогда, когда у нас достаточно конфет, чтобы угостить жителей всех пропущенных домов. Пусть первый пропущенный дом оказался на участке L. На участке R мы купили конфеты, и теперь их достаточно, чтобы угостить жителей всех пропущенных домов. Тогда участок от L до R мы дополнительно пройдем еще на два раза. Если попытаться угостить жителей пропущенных домов раньше, чем мы достигнем участка R (на участке T), то участок от L до T нам так же придется преодолеть дополнительно на два раза. Однако, так как мы не можем угостить всех жителей на отрезке от L до T, это говорит о том, что придется преодолеть некоторую часть этого интервала еще два раза, для чего нам еще на два раза придется преодолеть отрезок от T + 1 до R. Очевидно, что преодолев на два раза отрезки (L, T) и (T + 1, R) мы, фактически, преодолели на два раза отрезок от L до R. Помимо этого, какую-то часть отрезка от L до T нам потребуется преодолеть еще два раза. Получается, что количество времени, которое нам потребуется, будет строго больше, чем в первом случае. Аккуратно моделируем процесс за O(N), чтобы определить минимальное количество времени, которое потребуется на выполнение прохода по улице.

Теперь предложим модификацию для случая, когда закончить свое путешествие друзья могут на любом участке. В таком случае некоторую часть P улицы вовсе не обязательно посещать. Такая часть улицы представляет собой несколько (возможно ноль) последних участков этой улицы и не содержит домов. Определить такую часть можно за O(N) для каждого имеющегося изначально количества конфет на руках у друзей. Назовем улицу за вычетом ее части P полезной частью. В какой-то момент времени может оказаться так, что выгоднее дойти до конца полезной части и пойти обратно до тех пор, пока жители всех пропущенных домов не получат свои конфеты, после чего раздача сладостей прекращается. Такую проверку можно осуществлять за O(1) на каждом шаге вышеописанного решения.

Результирующая асимптотика O(N·logN) (логарифм возникает из-за использования бинарного поиска).

Задача C (Div1), E (div2) — День рождения ослика Иа-Иа

Авторы: am-real, pkhaustov

Сформулируем ряд утверждений, которые помогут нам решить задачу. При любом действии Винни-Пуха количество нетронутых горшков на любой из полок не может быть увеличено. Таким образом, если на полке с номером i изначально находилось A_i горшков, то в любой момент времени нетронутых горшков на этой полке будет C, причем 0 ≤ C ≤ A_i. Несложно поддерживать вероятность P(i, C) того, что на полке с номером i находится C нетронутых горшков для всех возможных значений i и C. Это можно сделать с помощью динамического программирования.

Очевидно, ответом после каждой операции будет сумма P(i, 0) по всем возможным значениям i. Заметим, что после каждой операции число нетронутых горшков может измениться только на полке, с которой Винни-Пух берет горшки. Формулы для переходов между состояниями динамического программирования достаточно тривиальны. Какие-то трудности могут возникнуть при выводе формул для k_i ≠ 1. Этих трудностей можно избежать, если разбивать запросы с k_i ≠ 1 на k_i запросов с k_i = 1, ведь 1 ≤ k_i ≤ 5, и, следовательно, время выполнения существенно увеличено не будет. Допустим и вариант, когда запросы не разбиваются. Для этого требуется аккуратно вывести несложные формулы переходов.

Несложно заметить, что перед первым запросом можно посчитать сумму P(i, 0) по всем значениям i. Далее, при выполнении каждого запроса u_i, v_i, k_i, до его выполнения отнимать P(u_i, 0) от ответа, а после его выполнения — добавлять новое значение P(u_i, 0) к ответу.

Если обозначить наибольшее значение A_i по всем i, как MaxA, то асимптотика такого решения, очевидно, будет O(N·MaxA). Памяти такое решение так же требует O(N·MaxA).

Задача D (Div1) — Ежик и звезды

Авторы: am-real, pkhaustov

Для начала заметим, что задачу можно свести к более простому варианту аналогичной задачи. В первую очередь, можно избавиться от точек, которые не находятся между двумя заданными во входных данных лучами, выходящими из начала координат. После чего можно повернуть все точки относительно начала координат на такой угол, чтобы один из лучей совпал с одной из осей координат. Для определенности положим, что мы повернули все точки на угол α₁ так, чтобы луч, который был пущен под этим углом совпал с осью O_X.

Теперь задача существенно упрощается. Все точки лежат в первой координатной четверти (то есть все координаты строго положительны), и имеется прямая L₀ под углом α₂ - α₁, которая проходит через начало координат и все точки лежат ниже нее. Добавим точку начала координат в наш набор, как фиктивную. Проведем через каждую из точек прямую L_i параллельную прямой L₀. Отсортируем точки в порядке убывания ординаты пересечения прямой L_i с осью O_y. Пойдем с конца. Для каждой точки i будем считать длину наибольшей цепочки MaxL(i), которая начинается из этой точки (смотреть будем на те точки, которые уже рассмотрены в нашем обратном порядке обхода). Для каждой точки i мы будем рассматривать все точки j между заданными лучами и выбирать такую, что MaxL(j) максимально, после чего полагать MaxL(i) = MaxL(j) + 1.

Чтобы рассмотреть только те точки, которые находятся в области между лучами выходящими из точки i, требуется выбрать такие точки j, для которых L_i пересекает ось O_y выше, чем L_j, и ордината Y_j не меньше, чем ордината Y_i. Заметим, что из-за порядка сортировки первое условие всегда выполняется, если аккуратно обработать точки с одинаковыми прямыми L_i. Для соблюдения оставшегося ограничения достаточно воспользоваться стандартной идеей с деревом интервалов. Но гораздо лучше заметить, что эта задача эквивалентна задаче нахождения поиска наибольшей возрастающей последовательности. Ответом будет значение MaxL для фиктивной точки начала координат.

Как результат, имеем решение с асимптотикой O(N·logN) и O(N) затратами памяти.

Задача E (Div1) — Бесконечная матрица

Автор: pkhaustov

Несложно заметить ряд закономерностей. Для начала обратим внимание на первую строку матрицы. В i-ом столбце первой строки находится элемент со значением (i - 1)² + 1. Несложно найти закономерность для первого столбца — там в чистом виде квадраты натуральных чисел. Диагональ тоже задается легкой закономерностью i² - i + 1.

Дальше несложно заметить, что в любом столбце до элемента главной диагонали значения увеличиваются с шагом в единицу. После элемента главной диагонали элемент в i-ой строке равен i² - i + 1. Как видим, можно и диагональный элемент отнести к этой же закономерности.

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

Теперь стоит выполнить все вычисления по модулю 10¹⁰. Для того, чтобы отследить, имеет ли число более десяти знаков, будем хранить (помимо остатка) частное от деления на 10¹⁰ по модулю нескольких различных простых чисел порядка 10⁹. На практике достаточно и одного простого числа, но для генерации тестов использовалось сразу четыре.

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

Всем привет!

Одним из авторов Codeforces Round #152 являюсь я.

Также авторами Codeforces Round #152 являются студенты Национального исследовательского Томского политехнического университета: am-real и max777alex.

Задачи Codeforces Round #152 будут посвящены литературным произведениям, отечественным кинематографу и мультипликации.

После всего вышесказанного авторы раундов обычно рассказывают о себе или пишут о том, что это — их первый раунд. Я не буду заниматься тем же самым, ведь существенной части сообщества Codeforces и без того известно, кто я такой. И мне даже интересно отношение количества смешлявых репризок в комментариях до и после раунда. Они только приветствуются.

Стоит, как обычно, поблагодарить тех, кто помогал нам готовить этот раунд. Спасибо Gerald за помощь в подготовке раунда. Спасибо Delinur за перевод задач на английский язык. И особенное спасибо Seyaua и sdya за то, что они согласились (ценой собственного времени) вычитать и прорешать задачи.

Обратите внимание, что раунд состоится 25 ноября в 19:30 по московскому времени.

Разбалловка div1: 1000 1000 1500 1500 2500

Разбалловка div2: 500 1000 2000 2000 2500

Контест окончен.

Мы приносим свои извинения за двусмысленность, допущенную в условии задачи A. Не было ясно, можно ли касаться штанги в момент, когда мяч пересекает линию ворот. Тем не менее, оба понимания условия проходили. Эти решения отличаются на бесконечно малую величину. Единственное, на что это оказало непосредственное влияние — взломы. Все взломы, которые базировались на утверждении о том, что касание штанги в момент пересечения линии ворот невозможно, будут удалены. Пожалуйста, те, кто делал такие взломы сообщите об этом Геральду Агапову (Gerald).

Мы также приносим свои извинения за перебои в работе сервера и сбои при отображении условий.

Далеко не единогласным решением жюри было решено сделать раунд рейтинговым. Рейтинг будет пересчитан 26.11.2012 после того, как будут удалены все соответствующие взломы.

Опубликован русскоязычный разбор задач раунда.

Мы ждали этого, и это свершилось. В Новосибирске стартует онсайт элитного соревнования по программированию «Всесибирская олимпиада по программированию им. И.В. Поттосина». Миллионы взглядов прикованы к этому сверхзнаменательному событию.

Уже сегодня лучшие команды России и стран СНГ будут сражаться за престижное звание победителя Всесибирской олимпиады по программированию.

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

1) Указан возраст посетителя и он меньше 18 лет

2) Указан напиток посетителя и он является алкогольным

F(x + 1, y + 1), при x < N, y < M и A[x] = B[x]

F(x + 1, y + 1) + 1, при x < N, y < M

F(x + 1, y), при x < N

F(x, y + 1), при y < M

1) Если толкнуть какую-либо доминошку вправо, то среди упавших доминошек все (кроме самой доминошки) будут находиться справа от той, что толкнули.

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

3) Для каждой доминошки можно определить номер наиболее правой доминошки такой, что она упадет, если толкнуть данную.