Sammarize's blog

By Sammarize, 9 years ago, In Russian

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

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

B (Div2) След

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

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

Первая область, закрашенная в красный цвет (область между первой и второй окружностями) — это вся область внутри первой окружности, из которой выкинули внутреннюю область второй окружности. Значит, площадь это области равна π × (r12 - r22). Аналогично, площадь второй красной области (между третьей и четвёртой окружностями) равна π × (r32 - r42). И так далее. Значит, суммарная их площадь равна π × (r12 - r22 + r32 - r42 + r52 - r62 + ...). Значит, чтобы посчитать ответ можно, например, сложить квадраты радиусов окружностей с нечётным номером, вычесть из полученной суммы квадраты радиусов всех окружностей с чётными номерами, и полученную величину умножить на \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) Подозреваемые

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

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

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

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

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

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

2. Переформулировка вторая. Рассмотрим последовательность si (i = 0, ..., n), такую, что si равно сумме первых 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]. Конечно, надо не забыть считать эту величину по модулю 109 + 7.

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

D (Div1) Улики

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

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

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

Итак, пусть у нас есть k компонент связности размера s1, s2, ..., sk.Посмотрим, чем равна искомая величина для маленьких k.

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

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

Пусть k = 3. Тогда в графе три компоненты связности, и надо провести два ребра, которые будут соединять различные пары компонент связности. Общее количество способов будет равно s1s2 × s1s3 + s1s2 × s2s3 + s1s3 × s2s3 = s1s2s3 × (s1 + s2 + s3) = s1s2s3 × n.

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

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

Количество способов первого типа: (s1)3 × s2s3s4 + (s2)3 × s1s3s4 + (s3)3 × s1s2s4 + (s4)3 × s1s2s3 = ((s1)2 + (s2)2 + (s3)2 + (s4)2) × (s1s2s3s4).

Количество способов второго типа: есть две компоненты связности, из которых выходит по два ребра. Пусть это первая и вторая. Тогда одно ребро проведено между ними, и ещё одно — из них в другие компоненты связности. Эти два ребра могут быть проведены двумя способами: от первой к третьей, а от второй к четвёртой, или наоборот. Значит, количество таких способов равно 2 × (s1)2 × (s2)2 × s3 × s4 = 2s1s2 × (s1s2s3s4). И Таких слагаемых 6 штук. Просуммировав их всех и прибавив к ним способы первого типа, можно вынести множитель (s1s2s3s4) за скобки, и останется аккурат формула квадрата суммы 4-х слагаемых. Значит, общее количество способов будет равно (s1s2s3s4) × n2.

На этом месте можно было уже легко догадаться до формулы (s1s2... sk) × nk - 2, тем более, что в первом случае получается как раз 1 = (s1) × n - 1.

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

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

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

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

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

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

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

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

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

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

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

Итак, пусть у нас есть какой-то, неизвестный способ дополнить граф до связного и мы построили по нему две последовательности (x1, x2, ..., xk - 2) и (a1, a2, ..., ak). Восстановим по ним дополнение графа до связного.

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

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

Итого, по каждой паре последовательностей восстанавливается дополнение до связного графа, из которого эта пара последовательностей была получена. Значит, количество способов дополнить граф до связного равно количеству пар последовательностей, которое и равно (s1s2... sk) × nk - 2.

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

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

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

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

Однако всё же 3 × 107 × 25 = 7, 5 × 108 взятий по модулю. Понятно, что это всё равно не уложится в 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 × 107)) = O(1, 2 × 108).

 
 
 
 
  • Vote: I like it
  • +25
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the editorial's English version available?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 C , Google translate

For starters, add a dummy character to the string s from both ends, for example, << # >>. Note that this did not affect the answer. Indeed, let us take the substring t partially or completely consisting of << # >>. Then all the characters << # >> would have to be replaced. But if they simply did not exist, then the necessary symbols would have to be added.

Consider the optimal substring t, and the sequence of actions that must be done with it in order to turn it into a string u. Consider the first addition or removal of a character from one end.

Note that this is not a deletion. After all, if we selected the substring t and, for example, deleted the last character from it, then we would not have to take it, because for a string t without the last character we need one less action than for the entire string t.

Now note that this is not an addition. Indeed, let us consider the string t, for some time change the characters in it to others, and finally add one, say, at the beginning. Then — If there is a character to the left of the line (that is, the line does not end there), then you could take it right away (that is, consider not t, but t with one more character to the left). Instead of adding a character, you can replace the existing one — this also takes one action. — If there is no character to the left of the line (that is, the first character t is the first character of the string s), then there is at least 2000 << # >> in t. So either the answer for such a row is at least 2000, because each lattice must be removed or replaced; or there are no symbols except grids in line t, and then at least | u | actions, because each u character must be added (or made from another character). But to get everything | u | action, it is enough to take any substring of length | u |.

Thus, there exists an optimal substring t from which u is obtained without additions or deletions. This is the key to the decision! After all, this means that the length of such a string is equal to the length u. Therefore, it suffices to iterate over the substrings of the string s of length | u |. The total number of such substrings is O (| s |), and for each substring it is easy to calculate the required number of changes during O (| u |) time — this is just the number of characters that need to be replaced.

Thus, it turns out to be a very easy-to-write solution in time O (| s | × | u |).