Здравствуй, Codeforces!

Сегодня, 17 октября в 17:35 MSK состоится Codeforces Round #377 для участников второго дивизиона. Участники первого дивизиона, как обычно, смогут участвовать в соревновании вне рейтинга.

Задачи раунда взяты из комплекта задач регионального этапа Всероссийской командной олимпиады школьников, проходившем вчера в Саратове. Комплект задач для онсайта соревнования придумывали и готовили Михаил MikeMirzayanov Мирзаянов, Илья IlyaLos Лось, Данил danilka.pro Сагунов, Владимир vovuh Петров и Роман Roms Глазов. Благодарим многих участников команд Саратовского ГУ за прорешивание соревнования. Одна задача будет присутствовать на раунде в несколько усложненной версии.

С подготовкой задач и переводом к раунду нам помогали Николай KAN Калинин и Татьяна Tatiana_S Семенова — спасибо! Спасибо Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

На раунде вам будут предоставлены 6 задач и 2 с половиной часа на их решение. Желаем удачи!

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

UPD Разбалловка: 500-1000-1500-2000-2000-2500

UPD2

Поздравляем победителей!

Div.2

1. gxgod

2. FizzyDavicl

3. dothanhlam97

4. ngkan

5. Judy.Hopps

Div.1

1. dreamoon_love_AA

2. kmjp

3. NVAL

4. eddy1021

5. pekempey

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

Так как в Саратове проводится Южный четвертьфинал, пересчет рейтинга будет осуществлен завтра.

UPD3 Разбор

Добрый день, Codeforces!

Рад сообщить, что в это воскресенье, 8го ноября в 19:30 MSK состоится Codeforces Round #330 для участников обоих дивизионов.

Задачи для вас уже не в первый раз с удовольствием придумывали и готовили Александр fcspartakm Фролов и я, Данил Сагунов. Мы говорим спасибо координатору Codeforces Глебу GlebsHP Евстропову за существенную помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon, Марии Delinur Беловой за перевод условий на английский язык, а также Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за тестирование и прорешивание задач раунда.

Каждому из участников раунда будет предоставлено два часа на решение пяти задач. Мы постарались сделать задачи разнообразными и интересными, и поэтому настоятельно рекомендуем прочитать все задачи во время раунда. Разбалловка, как и всегда, будет объявлена позднее.

Желаем всем удачи и высокого рейтинга!

UPD. Еще раз приносим свои извинения за задачу Cdiv2/Adiv1 — авторское решение неправильно работало в случае нечетных n. Мы очень надеемся, что остальные задачи контеста оказались (или окажутся в дорешивании) для вас полезными и интересными.

В любом случае, хотим поздравить победителей раунда:

Победители первого дивизиона:

1. jcvb
2. 2222
3. KAN

победители второго дивизиона:

1. Tagrimar
2. fsps60312
3. uhateme

Разбор задач можно найти здесь.

UPD. Задача Cdiv2/Adiv1 была исправлена, и теперь имеет то условие и решение, которое предполагали авторы. Задача вернулась в соревнование и доступна для дорешивания.

Adiv2

Для решения задачи будем хранить два массива hused[j] и vused[j] размера n, изначально заполненных false. Будем обрабатывать перекрестки в списке от 1-го к n-му, и если для i-го перекрестка оба значения hused[h_i] и vused[v_i] равны false , i-ый день нужно добавить к ответу и установить значения hused[h_i] и vused[v_i] в true, означающих, что h_i-ая горизонтальная и v_i-ая вертикальная теперь заасфальтирована, а в противном случае нужно просто пропустить очередной перекресток.

Такое решение работает за O(n²).

Авторское решение: 13390628

Bdiv2

Чтобы получить оптимальный ответ, роботу нужно двигаться от первого компьютера к последнему, затем от последнего к первому, потом опять от первого к последнему, и т.д., попутно собирая те части информации, которые он может собрать на момент нахождения рядом с компьютером. Таким образом робот будет по максимуму использовать ресурсы, затраченные на смену направления движения. Несмотря на наличие более быстрых решений, от участников требовалось лишь решение с асимптотикой O(n²).

Авторское решение: 13390612

Adiv1

Пусть ответ представляет собой массив a₁ ≤ a₂ ≤ ... ≤ a_n. Далее будем пользоваться тем, что gcd(a_i, a_j) ≤ a_min(i, j).

Верно, что gcd(a_n, a_n) = a_n ≥ a_i ≥ gcd(a_i, a_j) для любых 1 ≤ i, j ≤ n. Это значит, что a_n равен максимальному элементу таблицы. Запишем в ответ a_n максимальный ответ и удалим его из текущего набора элементов. После удаления gcd(a_n, a_n) в наборе будут содержаться gcd(a_i, a_j) для любых 1 ≤ i, j ≤ n, таких, что 1 ≤ min(i, j) ≤ n - 1.

Из последних двух неравенств следует, что gcd(a_i, a_j) ≤ a_min(i, j) ≤ a_n - 1 = gcd(a_n - 1, a_n - 1). Поскольку в наборе содержится gcd(a_n - 1, a_n - 1), максимальный элемент в наборе равен a_n - 1. Поскольку a_n уже известен, удалим из набора gcd(a_n - 1, a_n - 1), gcd(a_n - 1, a_n), gcd(a_n, a_n - 1) . Теперь в наборе содержатся gcd(a_i, a_j), для любых 1 ≤ i, j ≤ n таких, что 1 ≤ min(i, j) ≤ n - 2.

Далее повторим это операцию для каждого k from n - 2 to 1, устанавливая a_k равным максимальному элементу в оставшемся наборе и удаляя gcd(a_k, a_k), gcd(a_i, a_k), gcd(a_k, a_i) для всех k < i ≤ n из набора.

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

Авторское решение: 13390679

Bdiv1

Можно посчитать матрицу размера n × n mt[i][j] — длина наибольшей неубывающей подпоследовательности в массиве a₁, a₂, ..., a_n, начинающейся с элемента, не меньшего a_i и заканчивающейся непосредственно в элементе a_j.

Теперь, если мы имеем две матрицы размера n × n A[i][j] (ответ для массива a₁, a₂, ..., a_pn начинающегося с элемента, не меньшего a_i и заканчивающейся элементом a_j в последнем блоке массива (a_{(p - 1)n + 1}, ..., a_pn) и B[i][j] (ответ для массива a₁, a₂, ..., a_qn ), то произведение этих матриц

даст подобную матрицу, но для массива из p + q блоков. Так как такое произведение матриц является ассоциативным, воспользуемся быстрым возведением матрицы в степень для подсчета M[i][j] (ответ для массива a₁, a₂, ..., a_nT) — матрица mt[i][j] в степени T. Ответ на задачу — максимум матрицы M. Такое решение имеет асимптотику .

Авторское решение (с матрицами): 13390660

Существует альтернативное решение. Так как a₁, a₂, ..., a_nT содержит максимум n различных элементов, любая его неубывающая подпоследовательность содержит максимум n - 1 последовательных возрастающих соседних элементов. Пользуясь этим фактом, будем считать стандартное динамическое программирование на первых n блоках массива (a₁, ..., a_n²) и на n последних блоках массива (a_{nT - n + 1}, ..., a_nT). Все остальные блоки (а их T - 2n) между ними будут порождать равные элементы в результирующей неубывающей подпоследовательности.

Таким образом, для фиксированного a_i, в котором заканчивается неубывающая подпоследовательность длины p массива из первых n блоков, и для фиксированного a_j ≥ a_i, в котором аналогичная подпоследовательность длины s на последних n блоках массива начинается, нужно обновить ответ величиной p + (T - 2n)count(a_i) + s, где count(x) — количество вхождений x в массив a₁, ..., a_n. Получаем решение за .

Авторское решение ( с динамикой): 13390666

Cdiv1

Зафиксируем s и рассмотрим каждую пару (l, s). Тогда, если превосходящий подмассива содержит a_i, то a_i должен быть не меньше каждого a_j такого, что . Будем использовать этот факт и решать задачу для фиксированного g = gcd(n, s) (g|n). Для последующей проверки того, что a_i может содержаться в превосходящем подмассиве, посчитаем для каждого 0 ≤ r < g

.

Каждый периодический подмассив состоит из и только из них. Для нахождения количества таких подмассивов будем пользоваться методом двух указателей и для каждого подходящего a_i такого, что не является подходящим, найдем такое a_j, что являются подходящими и не является подходящим. Пусть представляет подотрезок из k элементов, т.е. . Любой подотрезок этого подотрезка так же является превосходящим, поэтому к отрезкам длины 1, 2, ..., k мы должны прибавить k, k - 1, ..., 1 соответственно. Так как сумма всех k не превосходит n, можно циклом увеличивать нужные значения. Случай, когда все a_i являются подходящими, нужно обрабатывать отдельно. После подсчета всех необходимых величин, мы должны добавить лишь те количества подотрезков длины x, для которых gcd(x, n) = g.

Описанное решение имеет асимптотику O(d(n)n), где d(n) — количество делителей n.

Авторское решение: 13390645

Ddiv1

Известно, что для простого p и натурального n максимальное α такое, что p^α|n!, вычисляется по формуле , где p^w ≤ n < p^w + 1. Так как , максимальное α для вычисляется по формуле .

Примечательно, что если представить n, k и n - k в p-ичной системе счисления, деление числа с округлением вниз на p^x соответствует отбрасыванию последних x цифр в его p-ичном представлении. Поскольку k + (n - k) = n, i-ое слагаемое в формуле для α соответствует величине переноса разряда с i - 1-ой к i-ой цифре в сложении k и n - k в p-ичной системе счисления и может принимать значения ноль или один.

Переведем A в p-ичную систему счисления и будем далее работать только с этим его представлением. В случае, если α превышает количество цифр в представлении A то, как описано выше, ответ равен 0. Далее будем считать динамическое программирование на представлении числа A.

dp[i][x][e][r] — ответ, если мы рассмотрели первые i цифр числа n и k, при этом эти цифры в n могут равняться первым цифрам A (булева e), x-ая степень p уже была набрана, и величина переноса с текущего в следующий разряд равна r . Переходы будем осуществлять вперед, имея, таким образом, не более p² вариантов расстановки цифр в n и k. Поскольку перебор всех таких вариантов невозможен, нужно заметить, что для перехода в фиксированное состояние (его первый параметр равен i + 1) количество вариантов расстановки цифр равняется сумме арифметической прогрессии, поэтому переход с помощью умножения на сумму прогрессии можно осуществлять за O(1).

Крайне рекомендуется ознакомиться с авторским решением за O(|A|² + |A|min(|A|, α)).

Авторское решение: 13390698

Ediv1

Количество бинарных функций на 4 переменных равняется 2²⁴, и каждую из них можно закодировать двоичным числом из 2⁴ бит , где значение каждого бита соответствует значению функций в наборе переменных, соответствующему номеру бита. Верно, что если mask_f и mask_g соответствуют функциям f(A, B, C, D) и g(A, B, C, D), то функции (f|g)(A, B, C, D) соответствует mask_f|mask_g bitmask.

Построим бинарное дерево разбора выражения. Замечу, что количество нелистовых вершин в нем равно . Будем считать динамическое программирование для каждой вершины v дерева разбора — dp[v][mask] равно количеству способов вставить символы в выражение, образованное поддеревом вершины v так, чтобы оно соответствовало функции, задающейся маской mask. Для листовых вершин значения динамики вычисляются ``в лоб'' перебором каждой из 16 функций и подстановкой переменной в функцию. Для нелистовых вершин существует способ перебирать все пары варинтов функций в сыновьях за 4¹⁶: dp[v][lmask|rmask] +  = dp[l][lmask] * dp[r][rmask].

Однако вся задача в том, чтобы делать это быстрее. Давайте посчитаем s[mask], где s[mask] равняется сумме ответов динамики для всех подмасок mask (submask&mask = submask) за 2⁴·2²⁴ операций с помощью следующего кода:

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = dp[x][mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] += s[mask];

Посчитаем sl[mask] и sr[mask] для dp[l][mask] и dp[r][mask] соответственно. Если приравнять s[mask] = sl[mask] * sr[mask], s[mask] будет хранить сумму произведений пар значений масок левого и правого сына, таких, что обе эти маски являются подмасками mask. Так как нам нужны пары, побитовый OR которых даст ровно mask, нужно исключить пары, побитовый OR которых дает подмаску mask, не равную mask. Для этого будем пользоваться формулой включений-исключений:

, где p равно количеству единичных бит в mask^submask.

Такую сумму можно посчитать аналогичному выше образом, но используя вычитание вместо сложения:

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = sl[mask] * sr[mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] -= s[mask];

Таким образом можно пересчитывать значения динамики в вершине за 3·2⁴·2¹⁶ операций.

Авторское решение: 13390713

Здравствуй, Codeforces!

Меня зовут Данил Сагунов, и когда-то я был красным... Впрочем, поздравляю всех со Второй Революцией!

Рад сообщить, что в эту субботу, 3 октября в 19:30 MSK состоится Codeforces Round #323 для обоих дивизионов. Задачи для вас придумывали и готовили я и Виталий gridnevvvit Гриднев. Это не первый раунд, в котором мы являемся авторами, и я уверен, что не последний.

В подготовке задач нам помогали мои друзья Максим Neon Мещеряков, Владимир vovuh Петров и Роман Roms Глазов, за что отдельное им спасибо. Благодарю Макса Zlobober Ахмедова за координаторскую деятельность, Михаила MikeMirzayanov Мирзаянова за создание и поддержку систем Codeforces и Polygon, благодаря которым проведение раунда стало возможным, и Марию Delinur Белову за перевод условий задач на английский язык.

Спасибо Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за прорешивание задач раунда!

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

UPD В e-mail рассылке была указана неправильная продолжительность раунда. Соревнование будет длиться 2 часа.

UPD2 Раунд успешно завершен! Благодарим всех за участие.

Поздравляем победителей первого дивизиона:

1. ecnerwala
2. ikatanic
3. uwi
4. PavelKunyavskiy
5. sd0061

И второго дивизиона:

1. wrong_order
2. ahwhlzz
3. kefaa

Мои поздравления fotiIe96, единственному решившему задачу D!

UPD3 Разбор можно найти здесь

534A - Экзамен

Легко убедиться в том, что k = n для всех n ≥ 4. Существует множество алгоритмов, позволяющих построить нужную последовательность длины n при n ≥ 4. Например, можно сажать студентов слева направо, при этом сначала сажать студентов с нечетными номерами в порядке убывания, начиная с самого большого нечетного номера, а затем аналогично ставить студентов с четными номерами. В такой последовательности модуль разности между двумя соседними нечетными (или двумя четными) номерами будет равна 2, а единственная пара соседних нечетного и четного номера будет образовывать разность, большую 3 (поскольку n ≥ 4).

Случаи n = 1, n = 2, n = 3 рассматриваются отдельно, и ответы для них равны 1, 1, 2 соответственно. Асимптотика решения — O(n).

Авторское решение: 10691992

534B - Пройденный путь

Покажем, что в каждую секунду i (0 ≤ i ≤ t - 1) максимально возможная скорость равняется . Действительно, если бы значение v_i было больше, то автомобиль не успел бы разогнаться или затормозить вовремя. Тот факт, что разность между соседними v_i при такой формуле не превышает d по модулю каждый может доказать самостоятельно.

Пользуясь вышеописанной формулой, можно просто перебрать i от 0 до t - 1 и просуммировать значения v_i, получая асимптотику решения O(t).

Возможно написать немного другое решение, которое пользуется следующим фактом. Если до конца пути осталось t секунд, текущая скорость равна u, а скорость в конце должна быть равна v₂, то существует способ доехать до конца пути требуемым образом тогда и только тогда, когда |u - v₂| ≤ t·d. Имея этот критерий существования ответа, можно просто каждый раз пытаться перейти к следующей секунде, выбирая максимальную из скоростей (просто в цикле от u + d до u - d), чтобы из состояния на следующей секунде был способ дойти до конца пути.

Авторские решения: 10692136 и 10692160

534C - Кости Поликарпа

Решение задачи использует факт, что с помощью k костей d₁, d₂, ..., d_k можно набрать любую сумму от k до . Это легко объясняется тем, что если существует способ набрать сумму s > k с помощью костей, то существует способ набрать сумму s - 1, который получается уменьшением значения одной кости на 1.

Обозначим сумму значений всех n костей как . Зафиксируем очередную кость d_i (значение на ней обозначим как x (1 ≤ x ≤ d_i). С помощью остальных костей мы можем набрать сумму s (n - 1 ≤ s ≤ S - d_i). Мы знаем, что общая сумма s + x = A, а значит n - 1 ≤ A - x ≤ S - d_i, откуда следует, что A - (n - 1) ≥ x ≥ A - (S - d_i).

С помощью вышеописанных неравенств для каждой кости вычисляется отрезок возможных значений, с помощью которого вычисляется количество значений, которые выпасть не могли. Асимптотика решения — O(n).

Авторское решение: 10692192

534D - Рукопожатия

Очевидно, порядок чисел в последовательности a значения не имеет. Ниже будем считать, что порядок чисел совпадает с порядком появления в ЦОПП соответствующих студентов (т.е. сначала пришел студент с индексом 1, потом 2 и так далее).

Для того, чтобы итоговая последовательность чисел a_i удовлетворяла условию задачи, необходимо и достаточно, чтобы выполнялись условия a_i + 1 ≤ a_i + 1 и . Для построения такой последовательности можно воспользоваться следующим жадным алгоритмом: первым числом, очевидно, поставим 0, а среди всех возможных вариантов последующих чисел a_i + 1 будем выбирать максимальное, удовлетворяющее вышеописанным условиям (т.е. первое число, меньшее либо равное a_i + 1, имеющее такой же остаток от деления, как и a_i + 1). Корректность такого алгоритма обосновывается тем, что любую правильную последовательность можно привести к такому же виду с помощью перестановки чисел последовательности.

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

Авторское решение: 10692252

534E - Берляндская система локального позиционирования

Предположим, что автобус начинал движение в остановке с номером 1 и промоделируем отрезок движения автобуса по m остановкам. Посчитаем для каждой из n остановок, сколько раз ее посетил автобус. Проверим, подходят ли эти количества к входным данным и обновим ответ, если нужно. Теперь попробуем сдвинуть стартовую остановку на остановку с номером 2. Поскольку отрезок пути автобуса должен иметь фиксированную длину, сдвинуть вперед нужно и последнюю остановку, смоделировав движение автобуса еще на одну остановку (после последней остановки).

Таким образом, чтобы получить количества остановок, сдвинув стартовую остановку на одну вперед, нужно сделать обновления всего для четырех остановок. Каждый раз, сдвигая стартовую остановку таким образом, нужно обновлять ответ. Стоит учесть, что всевозможных стартовых остановок (учитывая направление движения) ровно 2n - 2.

Асимптотика решения — O(n).

Авторское решение: 10705354

534F - Упрощенный японский кроссворд

Задачу можно решать несколькими способами.

Один из них можно описать следующим образом. Разделим поле кроссворда на две примерно равные части по столбцам (n × k и n × m - k). Решим для каждой части поля задачу отдельно с помощью перебора (который учитывает ограничения на количества блоков в столбцах) с запоминаниями по количествам блоков в строках. Поскольку каждая часть поля, в худшем случае, имеет размер 5 × 10, всевозможных полей с ограничениями на количество блоков будет не очень много. Посчитав все варианты полей для левой и правой половины поля, нужно перебрать левую часть поля и подобрать возможную правую часть (с учетом ограничений на количества блоков в строках). Такое решение требует аккуратной реализации автора.

Так же возможно решение с использованием динамики по профилю, где профиль — количество блоков в строке.

Авторское решение пользуется обеими идеями: 10705343

499A - Просмотр фильма

Задача решается жадным алгоритмом — если мы на текущем моменте времени можем пропустить x минут, не пропустив при этом ни одного хорошего момента, то мы пропускаем x минут, в противном случае — смотрим очередную минуту фильма.

499B - Лекция

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

498A - Сумасшедший город / 499C - Сумасшедший город

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

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

Итоговая сложность решения — O(n).

498B - Музыкальная пауза / 499D - Музыкальная пауза

Для удобства будем нумеровать песни с нуля.

Задачу будем решать методом динамического программирования. Состояние динамики будем описывать парой чисел i и j: dp[i][j] — вероятность того, что мы угадали ровно i песен, угадав последнюю из них ровно перед началом j-ой секунды (то есть Петя еще не включал следующую (i-ую) песню). База динамики, очевидно, dp[0][0] = 1.

Чтобы из состояния (i, j) сделать переход в состояние (i + 1, j + k) (1 ≤ k < t_i), нужно угадать i-ую песню ровно после k-ой секунды воспроизведения, не угадывая ее до этого — вероятность такого перехода равна (1 - p_i)^k - 1·p_i.

Для фиксированного состояния (i + 1, j) сумму таких переходов можно записать в виде суммы . Простое вычисление такой суммы для каждого состояния займет O(nT²) времени, поэтому нужно заметить, что при фиксированном i такую сумму можно поддерживать двумя указателями (в общем случае они задают отрезок длиной t_i) для каждого j за O(T) времени. Таким образом, подсчет переходов такого типа займет O(nT) времени.

Переход в (i + 1, j + t_i) следует рассмотреть отдельно. Также существует и вариант не успеть угадать песню в отведенное время — это переход из (i, j) в (i, (j + k) = T). Переходы этих двух типов считаются за O(nT).

Итоговая сложность решения — O(nT).

498C - Массив и операции / 499E - Массив и операции

Прежде всего заметим, что делить на составные числа невыгодно.

Теперь построим граф, где каждому числу соответствует некоторая группа вершин:

Разложим каждое число на простые делители. Каждому из простых делителей будет соответствовать некоторая вершина в графе, при этом, если число p входит в i-ое число в степени a_i, то ему будет соответствовать ровно a_i вершин в группе i-го числа.

Количество вершин в таком графе будет составлять .

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

Ребер при таком построении будет .

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

Итоговая асимптотика решения, использующего алгоритм Куна . Можно также заметить, что некоторые ребра лишние, и свести эту оценку к .

498D - Пробки в стране

Решение задачи — 60 (НОК чисел от 2 до 6) деревьев отрезков.

В v-ом дереве отрезков будем поддерживать для каждого отрезка [l, r] следующую величину: минимальное количество времени, необходимое, чтобы добраться от l до r, если мы начинаем в момент времени, равный v по модулю 60. Используя значения этих деревьев, несложно быстро отвечать на запросы, аккуратно изменяя деревья.

498E - Палочки и лесенки

Задача решается динамикой dp[i][mask] — количество способов покрасить первые i ступеней лестницы так, что последний уровень вертикальных палочек соответствует маске mask. Ее значения несложно пересчитывать, если знать матрицу M[mask1][mask2] — количество способов покрасить горизонтальные палочки между двумя соседними слоями вертикальных палочек, закрашенных соответственно маскам mask1 и mask2.

Поскольку вертикальных слоев для фиксированного i ровно w_i, то эту матрицу нужно возвести в степень, равную этому числу. После этого матрица очень просто используется для выполнения переходов динамики (подробнее в авторском решении).

Итоговая сложность решения —

Hello, Codeforces!

Some minutes ago I got accepted with problem on SPOJ resource. But a hour ago my correct solution was getting Runtime Error (Non-Zero Exit Code) because of in.close() in following code:

in = new BufferedReader(new InputStreamReader(System.in));
...
in.close();

Removing that line brings me accepted. Could anyone explain that?

483A - Опровержение гипотез

Автор задачи gridnevvvit

В задаче предполагалось два решения:

1. Перебрать всевозможные тройки, и проверить, правда ли, что для этой тройки гипотеза неверна. Асимптотика такого решения O(n³logA)
2. Разобрать несколько случаев. Например, это можно сделать так:

  if (l % 2 != 0)
      l++;
   
  if (l + 2 > r)
    out.println(-1);
  else
    out.println(l + " " + (l + 1) + " " + (l + 2));
 

Авторское решение: 8394832

483B - Друзья и подарки

Автор задачи gridnevvvit

Авторское решение — бинпоиск по ответу. Во-первых, заметим, что если из набора 1, 2, ..., v можно собрать подарки, то и из набора 1, 2, ..., v, v + 1 можно собрать подарки. Пусть f(v) — функция, возвращающая ответ на вопрос: правда ли, что из набора 1, 2, ..., v можно собрать подарки друзьям. пусть f₁ — количество чисел, которые делятся на x, а f₂ — количество чисел, которые делятся на y. и число both — количество чисел которые делятся и на x, и на y. Тогда в первую очередь первому другу мы постараемся отдать f₂ - both чисел, а второму — f₁ - both чисел. После этого нужно проверить, сможем ли мы раздать числа, которые не делятся ни на одно из чисел x и y.
Таким образом, решение за

Авторское решение: 8394846

483C - Разнообразная перестановка / 482A - Разнообразная перестановка

Автор задачи gridnevvvit

Разберем, как работает решение на большом примере, например

1 10 2 9 3 8 4 7 5 6

На нечетных местах мы имеем возрастающую последовательность 1, 2, 3 .., а на четных — убывающую последовательность n, n - 1, n - 2, ... Получим таким образом решение, выведем первые k чисел указанной выше последовательности, а потом сделаем так, чтобы соседние разности были равны единице.

Решение за асимптотику O(n).

Авторское решение: 8394876

483D - Интересный массив / 482B - Интересный массив

Автор задачи gridnevvvit

Будем решать задачу отдельно для каждого бита. Предположим, что пришло новое ограничение: l[i], r[i], q[i]. Если в числе q[i] бит с номером pos единичный, то у всех чисел на отрезке [l[i], r[i]] этот бит тоже будет единичным. Теперь можно воспользоваться стандартной идеей прибавления на отрезке оффлайн. Сделаем два прибавления в массиве s[bit] — в позиции l[i] мы сделаем прибавление 1, а еще одно в позиции r[i] + 1, там мы прибавим -1. Таким образом, если мы насчитаем частичные суммы на массиве s[bit], то, если s[bit][i] > 0, то бит bit в этом числе будет единичным, иначе — нет. После этого можно реализовать дерево отрезков, чтобы проверить выполнимость изначальных запросов.

Авторское решение: 8394894

483E - Игра со строками / 482C - Игра со строками

Автор задачи gridnevvvit

Переберем все пары строк, и подсчитаем маску mask — единичные биты будут находится только в позициях, в которых эти две пары строк имеют одинаковые символы. Таким образом, используя биты, соответствующие любой подмаске маски mask, мы не сможем отличить эту пару строк, поэтому добавим в маску d[mask] биты в позиции i и j. Таким образом, в d[mask] мы храним маску тех строк, которые мы не сможем отличить по заданной маске mask. Используя указанную выше информацию, мы сможем просто насчитать эту динамику.

Теперь, когда у нас имеется эта динамика, нетрудно восстановить ответ. Переберем маску mask. Попробуем задать еще один вопрос, то есть добавить в эту маску еще один бит. После этого мы могли отгадать некоторые строки, а именно те, что останутся в виде единичных битов в маске s = d[mask] ^ d[mask | (1 << pos)] (pos — позиция нового вопроса). Осталось аккуратно подсчитать количество бит в маске s и пересчитать искомое математическое ожидание.

Авторское решение: 8394918

482D - Случайная функция и дерево

Автор задачи RoKi

Посчитаем динамику d[v][p] — ответ на задачу для поддерева вершины v с размером, имеющим четность p.

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

Рассмотрим четности поддеревьев потомков, которых посетила наша функция (0 или 1). Первое, что нужно заметить: если среди этих величин есть различные значения, то такое поддерево при разных обходах будет раскрашено по-разному (это вы можете доказать сами). Теперь все наши посещенные потомки имеют одинаковые по четности размеры поддеревьев. Если размеры поддеревьев четные, то очевидно, что такое дерево учтется 2 раза. А вот если размеры поддеревьев нечетные, то нас интересуют только случаи, когда мы посетили нечетное количество потомков. Таким образом, из нашей динамики нужно вычесть количество способов раскрасить любое количество потомков с четным размером поддерева и нечетное количество потомков с нечетным размером поддерева.

Авторское решение: 8394936

482E - ELCA

Автор задачи danilka.pro

Будем обрабатывать M запросов блоками по штук (таких блоков, очевидно, тоже ). Каждый блок обрабатывается следующим образом:

Сначала поиском в глубину посчитаем для каждой вершины v значение , где u — любой предок v, а size_i — размер поддерева вершины i, включая саму вершину. Эта величина характеризует изменение ответа при 'отрывании' или 'прикреплении' вершины v, а именно, после выполнения одной из этих операций ответ изменится на path_v·size_v (уменьшится или увеличится соответственно).

Тем же образом посчитаем значение ch_v — количество всевозможных пар вершин, наименьший общий предок которых равен v. Эта величина характеризует изменение ответа при изменении V_v, а именно, при изменении величины V_v на dV_v ответ изменится на ch_v·dV_v.

Выделим вершины, номера которых хотя бы один раз встречаются в нашем блоке (в худшем случае таких вершин ). Теперь запустим поиск в глубину, который отметит вершины, являющиеся наименьшими общими предками каких-либо двух выделенных вершин. С помощью метода математической индукции нетрудно доказать, что в худшем случае таких вершин будет ровно . Таким образом мы получили 'сжатое' дерево, содержащее только необходимые вершины. Предка вершины i сжатого дерева обозначим за P_i.

На следующем рисунке представлен пример такого 'сжатия'. Красным обозначены вершины в блоке запроса, синим — помеченные вершины, пунктиром — ребра P_v → v сжатого дерева.

На таком сжатом дереве нужно посчитать для каждой вершины v еще одну величину C_v — размер поддерева вершины исходного дерева, которая лежит на пути от P_v до v в исходном дереве после P_v (непосредственный сын P_v).

Попробуем обработать запрос на смену родителя вершины v с p_v на u в сжатом дереве. Ответ, как уже было сказано выше, сначала уменьшится на path_v·size_v. Теперь для каждой вершины i, лежащей на пути от корня до P_v, изменятся две величины: size_i уменьшится на size_v, а ch_i уменьшится на величину, равную size_v·(size_i - C_t), (P_t = i), а path_i останется прежним. Для всех остальных вершин j, напротив, изменится лишь величина path_j — она уменьшится на . Теперь мы получили сжатое дерево, в котором все величины посчитаны с учетом того, что поддерево вершины v было удалено. Аналогичным образом происходит пересчет величин с учетом добавления вершины v в качестве сына вершины u (не забываем обновлять также и C_v).

Посмотрим, как будет выглядеть обработка запроса на смену значения V_v вершины v. Ответ, как было описано, изменится на ch_v·dV_v. Также изменятся все path_i для вершин, лежащих в поддереве v (их несложно пересчитать с помощью значений C_to, все остальные значения останутся прежними.

Таким образом, сложность решения составляет , что в случае N = M составляет .

Авторское решение: 8394944

441A - Валера и антиквариат

Автор задачи gridnevvvit

Нужно реализовать то, что записано в условии. Например, это можно сделать так: посчитаем q_i — минимальная цена товара у продавца i Тогда если q_i < v, то мы можем заключить сделку с продавцом i. Иначе не сможем.

Авторское решение: 6850474

441B - Валера и фрукты

Автор задачи gridnevvvit

Будем последовательно перебирать дни от 1 до 3001. Пусть текущий день это день i. Кроме того, дополнительно будем поддерживать величину cur --- количество фруктов, которые мы не успели собрать в предыдущие дни. Предположим, что в день и созреет now фруктов. Если now + cur ≤ v, то нужно добавить к ответу now + cur и обновить значение cur (cur = 0). Иначе к ответу нужно прибавить величину v, а величину cur обновить следующим образом. Пусть tv = max(v - cur, 0). Тогда cur будет равен величине cur = now - tv. Иначе говоря, сначала мы пытаемся собрать те фрукты, которые завтра уже испортятся.

Кроме того, можно решить задачу и за . Однако, этого не требовалось.

Авторское решение: 6850502

Бонус. Предположим, что фрукты можно собирать в дни a_i, a_i + 1, ..., a_i + T_i, где T_i — некоторое заданное число для каждого дерева. Как решить оптимально такую задачу? Да, еще. Кроме того, для каждого дня заданное свое значение v (производительность труда в каждый день).

441C - Валера и трубы

Автор задачи gridnevvvit

Задача решается довольно просто. Сначала построим такой обход прямоугольной таблицы, который посещает все его клетки. Его построить очень просто:

1. Пусть сначала мы стоим клетке (1, 1). Слева направо дойдем до самой правой клетки поля в этой строке, до клетки (1, m).
2. Перейдем на следующую строку, в ячейку (2, m). Справа налево дойдем до самой левой клетки поля в этой строке, до клетки (2, 1).
3. Перейдем на следующую строку. Повторим действия из пунктов 1. и 2. до тех пор, пока не посетим все клетки.

После того, как мы построили такой обход, получить ответ не трудно: достаточно первые (k - 1) трубу сформировать из 2 ячеек, а последнюю трубу из оставшихся.

Авторское решение: 6850508

441D - Валера и обмены

Aвтор задачи danilka.pro

В данной задаче удобно представить перестановку в виде ориентированного графа c n вершинами, а из каждой вершины i проведено единственное ребро в вершину p[i]. Очевидно, что этот граф полностью состоит из простых циклов.

Если провести операцию обмена (i, j), то ребра и станут ребрами и соответственно. Тогда, если i и j находятся в одном цикле, то этот цикл разорвется:

а если в разных, то циклы, в которых они содержатся, соединятся в один:

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

На основании всего вышеизложенного, чтобы получить перестановку q из перестановки p, нужно увеличить (или уменьшить) число циклов в перестановке p до n - m. Пусть с — число циклов в перестановке p. Тогда k всегда равно |(n - m) - c|.

Для выполнения условия лексикографической минимальности, рассмотрим три случая:

1) n - m < c

Очевидно, что в этом случае выгоднее всего уменьшать число циклов, соединяя их с циклом, содержащим вершину 1. Таким образом, в этом случае любой обмен имеет вид (1, v), где v > 1. Поскольку вершина каждого последующего цикла больше предыдущей, данный случай решается за O(n).

2) n - m > c

В этом случае необходимо для каждой вершины разрывать ее цикл, совершая обмен с наименьшей возможной вершиной (она так же должна находится в цикле). Это можно сделать, если представить цикл в виде строки . Поскольку каждый цикл разрывается за линейную сложность, такое решение работает за O(n²).

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

3) n - m = с

Так как в этом случае k = 0, никаких обменов делать не нужно.

Крайне рекомендуется ознакомиться с авторским решением: 6850515

441E - Валера и число

Автор задачи gridnevvvit

Решать задачу будем следующим образом: будем считать динамическое программирование d[i][mask][last][cnt] — вероятность получить через i шагов такое число v, что его последние 8 бит равны маске mask, 9-ый бит равен значению last, а cnt — это количество подряд идущих бит (начиная с 9-го бита) которые равны по величине значению last.

Хорошо, а почему мы отбросили остальные биты? Понятно, что используя операцию  +  = 1 мы сможем изменить только первый нулевой бит, индекс которого  ≥ 9.

Переходы достаточно очевидны: либо мы прибавим единицу, либо  *  = 2 (Подробнее их можно изучить в моем решении). Возможно, следует задать вопрос такой. Например, мы имеем число в двоичном представлении x = 1011111111.

И в текущий момент, мы делаем  +  = 1. Согласно тому, что я написал выше, мы должны перейти в состояние d[1][0][1][2], однако мы не сможем этого сделать, поскольку у нас нет никакой информации о 1 в 10-ой позиции. Однако, поскольку мы не сможем больше изменить никакой бит с индексом  >  = 9 (так как mask = 0) мы сделаем переход в состояние d[1][0][1][1].

Авторское решение: 6850523

Бонус. Предположим, что мы имеем немного другой псевдокод.

// input x, k, p
 
for(i = 0; i < k; i += 1) {
   if (x четное) {
     rnd = случайное число на отрезке [1, 100]
     if (rnd <= p)
       x *= 2;
     else
       x += 1;
   } else {
      x *= 2;
   }
}
 
s = 0;
 
while (x четное) {
  x /= 2;
  s += 1;
}
 

Как и прежде, нужно найти математическое ожидание s.

Насколько эффективно вы можете решать такую задачу? Можете ли вы доказать свое решение?

Tired of being loser at Codeforces? Do your best and reach the International Grandmaster rank at least here: http://games.usvsth3m.com/2048/codeforces-edition/