codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

157.md (29914B)


      1 Source: https://codeforces.com/blog/entry/4005
      2 
      3 ## A (Div2) Результат игры
      4 
      5 В этой игре можно было просто сделать, то, что просят в условии.А именно, завести счётчик, перебрать все клетки поля, и для каждой клетки найти сумму чисел в клетках, стоящих с ней на одной горизонтали, сумму чисел в клетках, стоящих с ней на одной вертикали, и сравнить эти суммы. Если сумма по вертикали больше, увеличить счётчик на один. После того, как перебраны все клетки, вывести счётчик. Максимальная сумма может быть 2 × 30 × 100 = 6 000, поэтому для её достаточно типа *int*.
      6 
      7 ## B (Div2) След
      8 
      9 Извиняюсь за кривой
     10 
     11 Давайте для начала отсортируем радиусы окружностей по убыванию. Пусть у нас теперь радиус первой окружности — *r*1, второй окружности — *r*2, ..., последней окружности — *r**n*, где *r*1 > *r*2 > ... > *r**n*. Внешняя область — так, которая снаружи первой окружности — покрашена в синий цвет, значит, область между первой и второй окружностью покрашена в красный. Далее, область между второй и третьей окружностью покрашена в синий цвет, между третьей и четвёртой — в красный, между четвёртой и пятой — в синий, и так далее.
     12 
     13 Первая область, закрашенная в красный цвет (область между первой и второй окружностями) — это вся область внутри первой окружности, из которой выкинули внутреннюю область второй окружности. Значит, площадь это области равна π × (*r*12 - *r*22). Аналогично, площадь второй красной области (между третьей и четвёртой окружностями) равна π × (*r*32 - *r*42). И так далее. Значит, суммарная их площадь равна π × (*r*12 - *r*22 + *r*32 - *r*42 + *r*52 - *r*62 + ...). Значит, чтобы посчитать ответ можно, например, сложить квадраты радиусов окружностей с нечётным номером, вычесть из полученной суммы квадраты радиусов всех окружностей с чётными номерами, и полученную величину умножить на \pi.
     14 
     15 Может возникнуть небольшое затруднение с последней окружностью. Если число окружностей нечётно, то последняя область — не кольцо между двумя окружностями, а круг. Но это, на самом деле, ничего не меняет: тогда последняя окружность имеет нечётный номер, и квадрат её радиуса надо тоже прибавить к сумме.
     16 
     17 ## A (Div1) — C (Div2) Сообщение
     18 
     19 Для начала, добавим к строке *s* с обоих концов по 2000 фиктивному символу — например, <<#>>. Заметим, что это не повлияло на ответ. Действительно, пусть мы взяли подстроку *t*, частично или полностью состоящую из <<#>>. Тогда все символы <<#>> надо было бы заменить. Но если бы их просто не было, то нужные символы надо было бы добавить.
     20 
     21 Рассмотрим оптимальную подстроку *t*, и последовательность действий, которую надо с ней сделать, чтобы превратить её в строку *u*. Рассмотрим первое добавление или удаление символа с одного из концов.
     22 
     23 Заметим, что это не удаление. Ведь если мы выбрали подстроку *t* и удалили из неё, к примеру, последний символ, то его не надо было бы и брать, потому что для строки *t* без последнего символа надо на одно действие меньше, чем для всей строки *t*.
     24 
     25 А теперь заметим, что это и не добавление. Действительно, пусть мы рассмотрели строку *t*, некоторое время меняли в ней символы на другие, и наконец, добавили один, скажем, в начале. Тогда - Если слева от строки есть символ (то есть, строка там ещё не кончается), то можно было его взять сразу (то есть, рассмотреть не *t*, а *t* с ещё одним символом слева). Вместо того, чтобы добавлять символ, можно заменить существующий — это тоже занимает одной действие. - Если слева от строки нету символа (то есть, первый символ *t* является первым символом строки *s*), тогда в *t* есть как минимум 2000 <<#>>. Значит, либо ответ для такой строки как минимум 2000, потому что каждую решётку надо удалить или заменить; либо никаких символов, кроме решёток, в строке *t* нет, и тогда надо сделать как минимум |*u*| действий, потому что каждый символ *u* надо добавить (или сделать из другого символа). Но чтобы получить всего |*u*| действий, достаточно взять любую подстроку длины |*u*|.
     26 
     27 Таким образом, существует оптимальная подстрока *t*, из которой получается *u* без добавлений и удалений. Это ключевой момент решения! Ведь это означает, что длина такой строки равна длине *u*. Значит, достаточно перебрать подстроки строки *s* длины |*u*|. Всего таких подстрок *O*(|*s*|), и для каждой подстроки легко за время *O*(|*u*|) посчитать необходимое количество изменений — это просто количество символов, которые надо заменить.
     28 
     29 Таким образом, получается очень простое в написании решение за время *O*(|*s*| × |*u*|).
     30 
     31 ## B (Div1) — D (Div2) Подозреваемые
     32 
     33 Будем называть людей, которые сказали <<Убийство совершил подозреваемый номер *a**i*>> *обвиняющими*, а людей, которые сказали <<Подозреваемый номер *a**i* не совершал убийства>> — *оправдывающими*. Рассмотрим подозреваемого номер *k*. Предположим, что он совершил убийство и посчитаем, сколько тогда человек сказали правду. Люди, которые сказали правду — это люди, которые обвиняли *его*, и люди, которые оправдывали *не его*. Таким образом, их количество — это количество людей, которые обвинили его, плюс количество людей, которые оправдали *кого-либо*, и минус количество людей, которые оправдали *его*. Таким образом, нам надо знать - количество людей, которые кого-либо обвиняют (это легко посчитать за *O*(*n*)) - для каждого подозреваемого количество людей которые его обвиняют - для каждого подозреваемого количество людей которые его оправдывают Последние две величины легко посчитать за время *O*(*n*) для всех подозреваемых. Действительно, пусть *i*-того человека обвиняют *x**i* людей и оправдывают *y**i* людей. Тогда надо просто для каждого человека номер *i*, если он оправдывающий, то увеличить *y**a**i*, а если обвиняет — увеличить *x**a**i*.
     34 
     35 После этих действий можно за *O*(1) посчитать для каждого подозреваемого число людей, которые говорят правду в том случае, если он преступник, и если это количество равно *m*, то данный человек может быть преступником. А после того, как мы нашли список возможных преступников, то не составляет труда для каждого человека определить, может ли он говорить правду и может ли он врать.
     36 
     37 ## С (Div1) — E (Div2) Шифр
     38 
     39 Давайте в словах записывать вместо букв цифры: вместо <> — 0, вместо <**> — 1, и так далее. Тогда разрешенные операции такие: рассмотреть два соседних числа, и одно из них увеличить на один, а другое — уменьшить на один. Для начала докажем ключевое утверждение задачи: *два слова имеют одинаковый смысл тогда и только тогда, когда у них одинаковая длина и одинакова сумма букв*.**
     40 
     41 Я мог бы привести полное и строгое доказательство этого факта, но оно будет длинным и немного занудным и, думается мне, его вряд ли кто-нибудь будет читать. Лучше я просто опишу две переформулировки задачи, в которых этого утверждение становится более очевидным.
     42 
     43 **1.** Переформулировка первая. Представим себе, что у нас вместо каждого числа — стопка монет, от 0 до 25 штук. Тогда разрешенные действия — это переложить одну монету из какой-то стопки в соседнюю так, чтобы во всех стопках оставалось от 0 до 25 монет.
     44 
     45 **2.** Переформулировка вторая. Рассмотрим последовательность *s**i* (*i* = 0, ..., *n*), такую, что *s**i* равно сумме первых *i* чисел в слове. Последовательность неубывает и разность между соседними элементами последовательности не превосходит 25. Тогда разрешенная операция — это изменить одно из чисел на один в любую сторону, так, чтобы разность между любыми двумя соседними числами по-прежнему не превосходила 25, и последовательность по-прежнему неубывала.
     46 
     47 Таким образом, нам надо посчитать, сколько слов такой же длинны имеют такую же сумму букв. Это легко сделать сразу для всех слов длины не больше 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.
     48 
     49 После того, как мы посчитали эту величину для всех 0 ≤ *l* ≤ 100, 0 ≤ *s* ≤ 2500 за *O*(1002 × 25) памяти и *O*(1002 × 252) времени, надо просто для каждого слова найти его длину сумму букв и вывести ответ (не забыв вычесть 1).
     50 
     51 ## D (Div1) Улики
     52 
     53 ### Как придумать формулу
     54 
     55 Простите все, кому это непривычно, но поскольку интерпретатор ТеХа на Codeforces в данный момент несколько кривоват, вместо традиционных нижних индексов будут нетрадиционные верхние. Это не степени, о степенях я буду оповещать отдельно.
     56 
     57 Говоря математическим языком, в задаче надо посчитать количество способов дополнить граф до связного минимальным количеством ребер. Понятно, что сам граф не имеет значения — важны только компоненты связности. Более того, сами компоненты связности не важны, важны только их размеры.
     58 
     59 Итак, пусть у нас есть *k* компонент связности размера *s*1, *s*2, ..., *s**k*.Посмотрим, чем равна искомая величина для маленьких *k*.
     60 
     61 Пусть *k* = 1. Тогда граф уже связный, есть 1 способ добавить ноль ребер.
     62 
     63 Пусть *k* = 2. Тогда в графе две компоненты связности и надо добавить одно ребро между ними. Существует *s*1 способ выбрать вершину из первой компоненты, *s*2 способов — из второй, всего *s*1*s*2 способов.
     64 
     65 Пусть *k* = 3. Тогда в графе три компоненты связности, и надо провести два ребра, которые будут соединять различные пары компонент связности. Общее количество способов будет равно *s*1*s*2 × *s*1*s*3 + *s*1*s*2 × *s*2*s*3 + *s*1*s*3 × *s*2*s*3 = *s*1*s*2*s*3 × (*s*1 + *s*2 + *s*3) = *s*1*s*2*s*3 × *n*.
     66 
     67 Участники с самой богатой фантазией могли уже сейчас догадаться до правильной формулы. Но лучше посмотрим на следующее значение *k*:
     68 
     69 Пусть *k* = 4. Тогда в графе 4 компоненты связности размера *s*1, *s*2, *s*3, *s*4. Надо провести три ребра. Немного подумав, можно понять, что эти рёбра либо будут соединять одну из компонент связности с остальными тремя, либо первую со второй, вторую — с третьей, а третью — с четвёртой (разумеется, компоненты могут следовать в любом порядке).
     70 
     71 Количество способов первого типа: (*s*1)3 × *s*2*s*3*s*4 + (*s*2)3 × *s*1*s*3*s*4 + (*s*3)3 × *s*1*s*2*s*4 + (*s*4)3 × *s*1*s*2*s*3 = ((*s*1)2 + (*s*2)2 + (*s*3)2 + (*s*4)2) × (*s*1*s*2*s*3*s*4).
     72 
     73 Количество способов второго типа: есть две компоненты связности, из которых выходит по два ребра. Пусть это первая и вторая. Тогда одно ребро проведено между ними, и ещё одно — из них в другие компоненты связности. Эти два ребра могут быть проведены двумя способами: от первой к третьей, а от второй к четвёртой, или наоборот. Значит, количество таких способов равно 2 × (*s*1)2 × (*s*2)2 × *s*3 × *s*4 = 2*s*1*s*2 × (*s*1*s*2*s*3*s*4). И Таких слагаемых 6 штук. Просуммировав их всех и прибавив к ним способы первого типа, можно вынести множитель (*s*1*s*2*s*3*s*4) за скобки, и останется аккурат формула квадрата суммы 4-х слагаемых. Значит, общее количество способов будет равно (*s*1*s*2*s*3*s*4) × *n*2.
     74 
     75 На этом месте можно было уже легко догадаться до формулы (*s*1*s*2... *s**k*) × *n**k* - 2, тем более, что в первом случае получается как раз 1 = (*s*1) × *n*- 1.
     76 
     77 ### Как доказать формулу
     78 
     79 Осталось только эту формулу доказать (хотя, конечно, для того, чтобы сдать задачу, доказательства не требовалось =))
     80 
     81 Итак, пусть есть некий набор из *k* - 1 ребра, который дополняет граф до связного. Построим по нему **две последовательности чисел**: (x^1, x^2, ..., x^{k-2}) и (a^1,a^2,...,a^k). При это каждое *x* может быть любым числом от 1 до *n*, а *a**i* может быть любым числом от 1 до *s**i*. Легко понять что таких **пар последовательностей** аккурат столько же, сколько (якобы!) способов дополнить наш граф до связного.
     82 
     83 Пара последовательностей же строится следующим образом.
     84 
     85 Для начала заметим, что этот набор из *k* - 1 ребра как бы образует дерево, в вершинах которого — компоненты связности.
     86 
     87 1. Рассмотрим минимальную по номеру компоненту связности, из которой выходит только одно дополняющее ребро. Пусть это компонента номер *i* и ребро соединяет вершину номер *t* в компоненте номер *i* и вершину номер *b* в другой компоненте. Тогда *x*1 = *b*, а *a**i* равно (внимание!) номеру вершины *t* среди вершин компоненты *i*, то есть, числу от 1 до *s**i*.
     88 2. Одна из компонент связности теперь отвалилась от графа. Остальные *k* - 2 ребер дополняют оставшиеся *k* - 2 компоненты до связного графа. Повторим ту же процедуру еще *k* - 1 раз.
     89 3. Осталось одно ребро. Оно соединяет две компоненты связности *u* и *v*, которые ещё не упомянуты во второй последовательности. Первая же последовательность заполнена — в ней как раз *k* - 2 элемента. Осталось во вторую последовательность на места номер *u* и *v* записать номера концов оставшегося ребра среди вершин компонент номер *u* и *v* соответственно.
     90 
     91 Итого, для каждого способа дополнить граф до связного существует такая пара последовательностей. Заметим, что если компонента *i* была <<висячей>>, то есть, соединялась только с одной другой компонентой, то её вершины не упоминаются в первой последовательности. А если не была висячей — то упоминаются, потому что все рёбра, которые выходят из этой компоненты, надо выкинуть. Каждое ребро, которое мы выкидываем, упирается одним концов в висячую компоненту. И когда было выкинуто первое ребро, выходящее из компоненты *i*, компонента *i* не была висячей. Значит, при выкидывании этого ребра в первую последовательность была записана вершина из компоненты *i*.
     92 
     93 Более того, как следует из рассуждений выше, в любой момент в процессе записи первой последовательности, если выясняется, что в ней больше не будет упомянуты вершины из компоненты *i*, то это означает, что компонента *i* либо уже выкинута, либо в данный момент висячая.
     94 
     95 Значит, в начальный момент, и каждый момент в процессе построения первой последовательности, по оставшемуся куску последовательности можно судить, какие вершины в данный момент висячие.
     96 
     97 Итак, пусть у нас есть какой-то, неизвестный способ дополнить граф до связного и мы построили по нему две последовательности (*x*1, *x*2, ..., *x**k* - 2) и (*a*1, *a*2, ..., *a**k*). Восстановим по ним дополнение графа до связного.
     98 
     99 1. Рассмотрим *x*1. Это число говорит нам, что сначала было выкинуто ребро одним концом в *x*1, а другим — в наименьшей по номеру висячей компоненте связности. Мы можем её определить, так как знаем текущий список висячих компонент. Пусть это компонента *i*. Тогда в *a**i* записан номер вершины в компоненте *i*, которая соединена с *x*1. Итак, одно ребро восстановили. Выкидываем компоненту номер *i*.
    100 2. Делаем эту операцию ещё *k* - 1 раз. Выкинуты *k* - 2 компоненты и восстановлены *k* - 2 ребра. Осталось два неиспользованных элемента второй последовательности, которые определяют вершины в двух оставшихся компонентах. Эти вершины и надо соединить *k* - 1-ым ребром.
    101 
    102 Итого, по каждой паре последовательностей восстанавливается дополнение до связного графа, из которого эта пара последовательностей была получена. Значит, количество способов дополнить граф до связного равно количеству пар последовательностей, которое и равно (*s*1*s*2... *s**k*) × *n**k* - 2.
    103 
    104 ## E (Div1) Оладьи миссис Хадсон
    105 
    106 Для начала заметим, что легко придумать очень простое решение этой задачи. Можно просто хранить остаток от деления каждой из цен на каждое из 25 простых чисел от 2 до 97. Тогда каждый запрос будет выполняться за *O*(25 × 10000). И всего решение будет работать за *O*(25 × 10000 × 30000) = *O*(7, 5 × 109) взятий по модулю. К сожалению, это не укладывается в ограничение по времени =)
    107 
    108 Первая идея авторского решения: если результаты наших действий класть с мап и доставать оттуда при необходимости, это сильно ускорит работу программы. Но мапить надо с умом! Во-первых, надо класть в мап остатки от произведения цен баночек, подходящих под шаблон, по модулю простых чисел. Во-вторых, все шаблоны, под которые подходят все номера, надо считать идеинтичными, независимо от основания системы исчисления.
    109 
    110 Нет смысла приводить здесь нудные вычисления, показывающие, что это действительно дает прирост производительности — гораздо проще написать программу, которая это подсчитает. Получается порядка 3 × 107 чисел, остатки которых надо перемножить, вместо 10 000 × 30 000 = 3 × 108.
    111 
    112 Однако всё же 3 × 107 × 25 = 7, 5 × 108 взятий по модулю. Понятно, что это всё равно не уложится в 5 секунд.
    113 
    114 Вторая идея авторского решения.
    115 
    116 Рассмотрим 4 модуля:
    117 
    118 1224469897 = 7 × 17 × 37 × 47 × 61 × 97
    119 
    120 1503325967 = 11 × 13 × 41 × 43 × 67 × 89
    121 
    122 1336143462 = 2 × 3 × 23 × 31 × 53 × 71 × 83
    123 
    124 937397015 = 5 × 19 × 29 × 59 × 73 × 79
    125 
    126 Квадрат всех этих 4 чисел влезает в знаковый 64-битный тип данных и их произведение делится на все простые числа до 100. Для каждой из 10 000 цен чисел будем хранить остаток этой цены по каждому из четырех модулей. Легко посчитать остаток произведения и прибавить к нему константу. По четырём остаткам легко определить, какой будет минимальный делитель — перебрать 25 вариантов.
    127 
    128 Итого, такая оптимизация дает асимптотику *O*(4 × (3 × 107)) = *O*(1, 2 × 108).