A (Div2) Результат игры

В этой игре можно было просто сделать, то, что просят в условии.А именно, завести счётчик, перебрать все клетки поля, и для каждой клетки найти сумму чисел в клетках, стоящих с ней на одной горизонтали, сумму чисел в клетках, стоящих с ней на одной вертикали, и сравнить эти суммы. Если сумма по вертикали больше, увеличить счётчик на один. После того, как перебраны все клетки, вывести счётчик. Максимальная сумма может быть 2 × 30 × 100 = 6 000, поэтому для её достаточно типа int.

B (Div2) След

Извиняюсь за кривой

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

Первая область, закрашенная в красный цвет (область между первой и второй окружностями) — это вся область внутри первой окружности, из которой выкинули внутреннюю область второй окружности. Значит, площадь это области равна π × (r₁² - r₂²). Аналогично, площадь второй красной области (между третьей и четвёртой окружностями) равна π × (r₃² - r₄²). И так далее. Значит, суммарная их площадь равна π × (r₁² - r₂² + r₃² - r₄² + r₅² - r₆² + ...). Значит, чтобы посчитать ответ можно, например, сложить квадраты радиусов окружностей с нечётным номером, вычесть из полученной суммы квадраты радиусов всех окружностей с чётными номерами, и полученную величину умножить на \pi.

Может возникнуть небольшое затруднение с последней окружностью. Если число окружностей нечётно, то последняя область — не кольцо между двумя окружностями, а круг. Но это, на самом деле, ничего не меняет: тогда последняя окружность имеет нечётный номер, и квадрат её радиуса надо тоже прибавить к сумме.

A (Div1) — C (Div2) Сообщение

Для начала, добавим к строке s с обоих концов по 2000 фиктивному символу — например, <<#>>. Заметим, что это не повлияло на ответ. Действительно, пусть мы взяли подстроку t, частично или полностью состоящую из <<#>>. Тогда все символы <<#>> надо было бы заменить. Но если бы их просто не было, то нужные символы надо было бы добавить.

Рассмотрим оптимальную подстроку t, и последовательность действий, которую надо с ней сделать, чтобы превратить её в строку u. Рассмотрим первое добавление или удаление символа с одного из концов.

Заметим, что это не удаление. Ведь если мы выбрали подстроку t и удалили из неё, к примеру, последний символ, то его не надо было бы и брать, потому что для строки t без последнего символа надо на одно действие меньше, чем для всей строки t.

А теперь заметим, что это и не добавление. Действительно, пусть мы рассмотрели строку t, некоторое время меняли в ней символы на другие, и наконец, добавили один, скажем, в начале. Тогда - Если слева от строки есть символ (то есть, строка там ещё не кончается), то можно было его взять сразу (то есть, рассмотреть не t, а t с ещё одним символом слева). Вместо того, чтобы добавлять символ, можно заменить существующий — это тоже занимает одной действие. - Если слева от строки нету символа (то есть, первый символ t является первым символом строки s), тогда в t есть как минимум 2000 <<#>>. Значит, либо ответ для такой строки как минимум 2000, потому что каждую решётку надо удалить или заменить; либо никаких символов, кроме решёток, в строке t нет, и тогда надо сделать как минимум |u| действий, потому что каждый символ u надо добавить (или сделать из другого символа). Но чтобы получить всего |u| действий, достаточно взять любую подстроку длины |u|.

Таким образом, существует оптимальная подстрока t, из которой получается u без добавлений и удалений. Это ключевой момент решения! Ведь это означает, что длина такой строки равна длине u. Значит, достаточно перебрать подстроки строки s длины |u|. Всего таких подстрок O(|s|), и для каждой подстроки легко за время O(|u|) посчитать необходимое количество изменений — это просто количество символов, которые надо заменить.

Таким образом, получается очень простое в написании решение за время O(|s| × |u|).

B (Div1) — D (Div2) Подозреваемые

Будем называть людей, которые сказали <<Убийство совершил подозреваемый номер a_i>> обвиняющими, а людей, которые сказали <<Подозреваемый номер a_i не совершал убийства>> — оправдывающими. Рассмотрим подозреваемого номер k. Предположим, что он совершил убийство и посчитаем, сколько тогда человек сказали правду. Люди, которые сказали правду — это люди, которые обвиняли его, и люди, которые оправдывали не его. Таким образом, их количество — это количество людей, которые обвинили его, плюс количество людей, которые оправдали кого-либо, и минус количество людей, которые оправдали его. Таким образом, нам надо знать - количество людей, которые кого-либо обвиняют (это легко посчитать за O(n)) - для каждого подозреваемого количество людей которые его обвиняют - для каждого подозреваемого количество людей которые его оправдывают Последние две величины легко посчитать за время O(n) для всех подозреваемых. Действительно, пусть i-того человека обвиняют x_i людей и оправдывают y_i людей. Тогда надо просто для каждого человека номер i, если он оправдывающий, то увеличить y_ai, а если обвиняет — увеличить x_ai.

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

С (Div1) — E (Div2) Шифр

Давайте в словах записывать вместо букв цифры: вместо <> — 0, вместо <> — 1, и так далее. Тогда разрешенные операции такие: рассмотреть два соседних числа, и одно из них увеличить на один, а другое — уменьшить на один. Для начала докажем ключевое утверждение задачи: два слова имеют одинаковый смысл тогда и только тогда, когда у них одинаковая длина и одинакова сумма букв.

Я мог бы привести полное и строгое доказательство этого факта, но оно будет длинным и немного занудным и, думается мне, его вряд ли кто-нибудь будет читать. Лучше я просто опишу две переформулировки задачи, в которых этого утверждение становится более очевидным.

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

2. Переформулировка вторая. Рассмотрим последовательность s_i (i = 0, ..., n), такую, что s_i равно сумме первых i чисел в слове. Последовательность неубывает и разность между соседними элементами последовательности не превосходит 25. Тогда разрешенная операция — это изменить одно из чисел на один в любую сторону, так, чтобы разность между любыми двумя соседними числами по-прежнему не превосходила 25, и последовательность по-прежнему неубывала.

Таким образом, нам надо посчитать, сколько слов такой же длинны имеют такую же сумму букв. Это легко сделать сразу для всех слов длины не больше 100. Посчитаем с помощью динамики такую величину x[l][s] : количество слов длины l с суммой букв s. - База динамики: l = 0. Есть ровно одно слово (пустое, оно же единственное слово длины 0) с суммой букв 0, и по 0 слов с любой другой суммой букв. - Переход динамики: очень простой. Чтобы узнать, сколько слов длины l имеют сумму s, надо перебрать, какая может быть последняя буква у этого слова: x[l][s] = x[l - 1][s] + x[l - 1][s - 1] + ... + x[l - 1][s - 25]. Конечно, надо не забыть считать эту величину по модулю 10⁹ + 7.

После того, как мы посчитали эту величину для всех 0 ≤ l ≤ 100, 0 ≤ s ≤ 2500 за O(100² × 25) памяти и O(100² × 25²) времени, надо просто для каждого слова найти его длину сумму букв и вывести ответ (не забыв вычесть 1).

D (Div1) Улики

Как придумать формулу

Простите все, кому это непривычно, но поскольку интерпретатор ТеХа на Codeforces в данный момент несколько кривоват, вместо традиционных нижних индексов будут нетрадиционные верхние. Это не степени, о степенях я буду оповещать отдельно.

Говоря математическим языком, в задаче надо посчитать количество способов дополнить граф до связного минимальным количеством ребер. Понятно, что сам граф не имеет значения — важны только компоненты связности. Более того, сами компоненты связности не важны, важны только их размеры.

Итак, пусть у нас есть k компонент связности размера s¹, s², ..., s^k.Посмотрим, чем равна искомая величина для маленьких k.

Пусть k = 1. Тогда граф уже связный, есть 1 способ добавить ноль ребер.

Пусть k = 2. Тогда в графе две компоненты связности и надо добавить одно ребро между ними. Существует s¹ способ выбрать вершину из первой компоненты, s² способов — из второй, всего s¹s² способов.

Пусть k = 3. Тогда в графе три компоненты связности, и надо провести два ребра, которые будут соединять различные пары компонент связности. Общее количество способов будет равно s¹s² × s¹s³ + s¹s² × s²s³ + s¹s³ × s²s³ = s¹s²s³ × (s¹ + s² + s³) = s¹s²s³ × n.

Участники с самой богатой фантазией могли уже сейчас догадаться до правильной формулы. Но лучше посмотрим на следующее значение k:

Пусть k = 4. Тогда в графе 4 компоненты связности размера s¹, s², s³, s⁴. Надо провести три ребра. Немного подумав, можно понять, что эти рёбра либо будут соединять одну из компонент связности с остальными тремя, либо первую со второй, вторую — с третьей, а третью — с четвёртой (разумеется, компоненты могут следовать в любом порядке).

Количество способов первого типа: (s¹)³ × s²s³s⁴ + (s²)³ × s¹s³s⁴ + (s³)³ × s¹s²s⁴ + (s⁴)³ × s¹s²s³ = ((s¹)² + (s²)² + (s³)² + (s⁴)²) × (s¹s²s³s⁴).

Количество способов второго типа: есть две компоненты связности, из которых выходит по два ребра. Пусть это первая и вторая. Тогда одно ребро проведено между ними, и ещё одно — из них в другие компоненты связности. Эти два ребра могут быть проведены двумя способами: от первой к третьей, а от второй к четвёртой, или наоборот. Значит, количество таких способов равно 2 × (s¹)² × (s²)² × s³ × s⁴ = 2s¹s² × (s¹s²s³s⁴). И Таких слагаемых 6 штук. Просуммировав их всех и прибавив к ним способы первого типа, можно вынести множитель (s¹s²s³s⁴) за скобки, и останется аккурат формула квадрата суммы 4-х слагаемых. Значит, общее количество способов будет равно (s¹s²s³s⁴) × n².

На этом месте можно было уже легко догадаться до формулы (s¹s²... s^k) × n^k - 2, тем более, что в первом случае получается как раз 1 = (s¹) × n^- 1.

Как доказать формулу

Осталось только эту формулу доказать (хотя, конечно, для того, чтобы сдать задачу, доказательства не требовалось =))

Итак, пусть есть некий набор из k - 1 ребра, который дополняет граф до связного. Построим по нему две последовательности чисел: (x^1, x^2, ..., x^{k-2}) и (a^1,a^2,...,a^k). При это каждое x может быть любым числом от 1 до n, а aⁱ может быть любым числом от 1 до sⁱ. Легко понять что таких пар последовательностей аккурат столько же, сколько (якобы!) способов дополнить наш граф до связного.

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

Для начала заметим, что этот набор из k - 1 ребра как бы образует дерево, в вершинах которого — компоненты связности.

1. Рассмотрим минимальную по номеру компоненту связности, из которой выходит только одно дополняющее ребро. Пусть это компонента номер i и ребро соединяет вершину номер t в компоненте номер i и вершину номер b в другой компоненте. Тогда x¹ = b, а aⁱ равно (внимание!) номеру вершины t среди вершин компоненты i, то есть, числу от 1 до sⁱ.

2. Одна из компонент связности теперь отвалилась от графа. Остальные k - 2 ребер дополняют оставшиеся k - 2 компоненты до связного графа. Повторим ту же процедуру еще k - 1 раз.

3. Осталось одно ребро. Оно соединяет две компоненты связности u и v, которые ещё не упомянуты во второй последовательности. Первая же последовательность заполнена — в ней как раз k - 2 элемента. Осталось во вторую последовательность на места номер u и v записать номера концов оставшегося ребра среди вершин компонент номер u и v соответственно.

Итого, для каждого способа дополнить граф до связного существует такая пара последовательностей. Заметим, что если компонента i была <<висячей>>, то есть, соединялась только с одной другой компонентой, то её вершины не упоминаются в первой последовательности. А если не была висячей — то упоминаются, потому что все рёбра, которые выходят из этой компоненты, надо выкинуть. Каждое ребро, которое мы выкидываем, упирается одним концов в висячую компоненту. И когда было выкинуто первое ребро, выходящее из компоненты i, компонента i не была висячей. Значит, при выкидывании этого ребра в первую последовательность была записана вершина из компоненты i.

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

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

Итак, пусть у нас есть какой-то, неизвестный способ дополнить граф до связного и мы построили по нему две последовательности (x¹, x², ..., x^k - 2) и (a¹, a², ..., a^k). Восстановим по ним дополнение графа до связного.

1. Рассмотрим x¹. Это число говорит нам, что сначала было выкинуто ребро одним концом в x¹, а другим — в наименьшей по номеру висячей компоненте связности. Мы можем её определить, так как знаем текущий список висячих компонент. Пусть это компонента i. Тогда в aⁱ записан номер вершины в компоненте i, которая соединена с x¹. Итак, одно ребро восстановили. Выкидываем компоненту номер i.

2. Делаем эту операцию ещё k - 1 раз. Выкинуты k - 2 компоненты и восстановлены k - 2 ребра. Осталось два неиспользованных элемента второй последовательности, которые определяют вершины в двух оставшихся компонентах. Эти вершины и надо соединить k - 1-ым ребром.

Итого, по каждой паре последовательностей восстанавливается дополнение до связного графа, из которого эта пара последовательностей была получена. Значит, количество способов дополнить граф до связного равно количеству пар последовательностей, которое и равно (s¹s²... s^k) × n^k - 2.

E (Div1) Оладьи миссис Хадсон

Для начала заметим, что легко придумать очень простое решение этой задачи. Можно просто хранить остаток от деления каждой из цен на каждое из 25 простых чисел от 2 до 97. Тогда каждый запрос будет выполняться за O(25 × 10000). И всего решение будет работать за O(25 × 10000 × 30000) = O(7, 5 × 10⁹) взятий по модулю. К сожалению, это не укладывается в ограничение по времени =)

Первая идея авторского решения: если результаты наших действий класть с мап и доставать оттуда при необходимости, это сильно ускорит работу программы. Но мапить надо с умом! Во-первых, надо класть в мап остатки от произведения цен баночек, подходящих под шаблон, по модулю простых чисел. Во-вторых, все шаблоны, под которые подходят все номера, надо считать идеинтичными, независимо от основания системы исчисления.

Нет смысла приводить здесь нудные вычисления, показывающие, что это действительно дает прирост производительности — гораздо проще написать программу, которая это подсчитает. Получается порядка 3 × 10⁷ чисел, остатки которых надо перемножить, вместо 10 000 × 30 000 = 3 × 10⁸.

Однако всё же 3 × 10⁷ × 25 = 7, 5 × 10⁸ взятий по модулю. Понятно, что это всё равно не уложится в 5 секунд.

Вторая идея авторского решения.

Рассмотрим 4 модуля:

1224469897 = 7 × 17 × 37 × 47 × 61 × 97

1503325967 = 11 × 13 × 41 × 43 × 67 × 89

1336143462 = 2 × 3 × 23 × 31 × 53 × 71 × 83

937397015 = 5 × 19 × 29 × 59 × 73 × 79

Квадрат всех этих 4 чисел влезает в знаковый 64-битный тип данных и их произведение делится на все простые числа до 100. Для каждой из 10 000 цен чисел будем хранить остаток этой цены по каждому из четырех модулей. Легко посчитать остаток произведения и прибавить к нему константу. По четырём остаткам легко определить, какой будет минимальный делитель — перебрать 25 вариантов.

Итого, такая оптимизация дает асимптотику O(4 × (3 × 10⁷)) = O(1, 2 × 10⁸).