I'd like to invite everybody to participate in HourRank 12 on HackerRank. It'll start tomorrow at 19:30 PM MSK.

It's my first HourRank but I've prepared problems for HackerRank several times. I also used to prepare problems for Codeforces long time ago.

There will be three problems and one hour to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!

I'd like to thank wanbo for testing the problems, it's always a pleasure to work with him. I hope you will enjoy the problems and some of you will solve everything.

Scoring will be: 20-40-80. Editorials will be published right after the contest.

Good luck!

A div2

Требовалось просто найти наименьшую отсутствующую в числе цифру и сравнить результат с данным k.

B div2

Хороший отрезок либо содержит все нули, либо длина его мала. Второе следует из того, что длина отрезка не может превосходить длины последовательности {0, 1, 2, 3, 5, 8, ..., x, y} (y > 10⁹; x < 10⁹). Длина этой последовательности, в свою очередь, меньше 50. Тогда второй случай можно разобрать наивным алгоритмом, а второй, например, динамикой (d_i = 0 eсли a_i ≠ 0 и d_i = d_i - 1 + 1 если a_i = 0).

A div1

Заметим, что сумма в прямоугольнике (x1, y1, x2, y2) равна sum(x1, x2)·sum(y1, y2). Здесь sum(l, r) = s_l + s_l + 1 + ... + s_r. Теперь осталось посчитать sum(l, r) для всех (l, r) и посчитать сколько отрезков дают в сумме x для всех возможных x (0 ≤ x ≤ 9·|s|). В итоге нужно пробежать по всем возможным суммам на [x1, x2] и найти . Не стоит забывать про случай a = 0.

B div1

Можно считать, что Джон может x на y, если s(x) + d ≥ s(y) (не важно, если x пересекает y). Можно стандартной динамикой посчитать все возможные суммы в множествах (задача о рюкзаке). Тогда Джон должен всегда менять все свое текущее множество на другое, потому что, если он обменял подмножество x (текущее) z (подмножество) на y, можно сказать, что он поменял x to . Теперь осталось найти кратчайшую последовательность множеств a, такую, что s(a_i + 1) - d ≥ s(a_i) для любого i и a₀ = {}. Это может быть решено следующей жадностью. a_i, i > 0 максимальная корректная сумма, такая, что a_i ≤ a_i - 1 + d. Рассмотрим оптимальный ответ c и ответ жадности a. Пусть k — первая позиция, такая что a_k ≠ c_k, очевидно a_k > c_k (так как a_k выбрано наибольшим). Затем рассмотрим q такое, что q_i = c_i для i ≠ k и q_k = a_k. q так же оптимален. Такими заменами можно получить a. Тогда a оптимально.

C div1

Пока не переведено.

D div1

1. Возьмем случайный элемент a_r из a. С вероятностью где g is ghd of a.
2. Пусть x_i = gcd(a_i, a_r). Существует не более d различных x_i, где d — количество делителей a_r.
3. Можно найти количество a_i, таких, что для любого k за O(d²) обычным перебором. Здесь D — множество делителей a_r.
4. Если повторить пункт 1 x раз, то полученное решение будет корректным с вероятностью 1 - 2^- x.

Можно решать эту задачу O(n·plog + d·2^plog) на итерацию (примерно в 10 раз быстрее решения выше), где plog — максимальное количество различных простых в факторизации a_r. Это решение и предполагалось, но перед контестом оказалось, что можно получить ОК решением выше, если уменьшить количество итераций до минимально возможного. Уменьшать до предела количество итераций в авторском решении мы не стали.

E div1

1. Найдем количество прямоугольников не более чем с k единицами внутри, пересекающих в декартовой системе координат.
2. Можно это сделать за n²·k. Нужно найти k ближайших единиц сверху и снизк от , перебрать все отрезки [l, r] такие, что 1 ≤ l ≤ r ≤ n и найти ближайшие k единиц сверху и снизу от отрезка.
3. Это можно сделать слиянием соответствующих массивов для строк.
4. Найдя ближайшие слева и справа от [l, r] k единиц можно найти количество прямоугольников, пересекающих по отрезку [l, r].
5. Это можно сделать, перебрав количество единиц сверху, которое входит в прямоугольник. По нему однозначно восстанавливается количество единиц снизу и определяются границы, в которых может лежать верхняя и нижняя сторона прямоугольника.
6. Теперь осталось поделить доску пополам и запустить этот алгоритм для половинок. При этом нужно сменить ориентацию разрезающей прямой. Нетрудно увидеть, что такой алгоритм посчитает все прямоугольники.
7. для квадратных досок. Для прямоугольных это сумма соответствующих выражений для n и m.

На рисунке 1 ближайшие сверху единицы (помечены черным) лежат на 4й и 2й горизонтали. Ближайшие снизу — на 5й и 7й. Тогда при k = 2 Корректных прямоугольников, которые содержат две единицы сверху и пересекают красную прямую нет. Есть 4 прямоугольника, которые содержат по одной единице сверху и снизу. На рисунках 2, 3 и 4 показано расширение имеющегося отрезка. Каждый раз требуется слить текущий массив ближайших единиц с массивом ближайших к строке единиц.

Привет всем! В этот вторник пройдет Codeforces Round #213, задачки для которого придумал я. Спасибо caustique, el_sanchez, KAN, malcolm, они тестировали задачи, помогали с составлением тестов и условий. Спасибо Gerald, который координировал работу и помогал в решении возникающих трудностей, MikeMirzayanov за создание возможности проводить соревнования и Delinur за перевод условий на английский.

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

Контест закончился, можно поздравить победителей

div1:

1. lovelymoon
2. niyaznigmatul
3. cerealguy
4. ainu7
5. cgy4ever

div2:

1. dotato
2. netman
3. kybconnor_4

Прошу прощения за косяки в условиях, которые вызвали тонны вопросов. Впредь я постараюсь внимательнее относиться к условиям.

У меня возник вопрос. Требуется найти наибольшее по мощности множество и не существует i ≠ j таких, что .

Предположительно нужно взять все множества, где элементов. Но доказать это у меня не получилось. Где можно почитать об этом?

Коровники (задача с российских летних сборов 2007 года)

Дано дерево из n <= 50000 вершин. Нужно зафиксировать k <= n вершин так, чтобы минимизировать максимальное расстояние от вершины дерева до ближайшей фиксированной. Нужно восстановить ответ.

Я придумал что-то похожее на решение для этой задачи, но, увы, у меня не получается это довести: Сначала сделаем бинпоиск по ответу. Теперь dp[i][j][k] — минимальное количество коровников, необходимое для того, чтобы в поддереве вершины i (рассмотрены только первые k сыновей вершины i) все непокрытые вершины были на расстоянии не более j от корня, либо, если j < 0, была фиксированная вершина такая, что d — maxd = j (d — расстояние до этой фиксированной вершины, maxd — текущий ответ). Тогда переход — это добавление новой ветки. Его можно просто делать за O(maxd) для одного состояния. Но я предположу, что умею делать этот переход за O(1).

Можно посчитать другую динамику dp2[i][j][k] — минимальная функция предыдущей динамики, такая, что нам понадобилось j коровников. (i и k не меняют роли). Тогда, можно заметить, что k * ans <= 2*n и считать динамику, которая считается быстрее. Тогда мы получим асимптотику O(n sqrt(n) log(n)).

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

Есть ли в этой задаче что-то проще и с меньшим количеством случаев?

Сегодня на контест мы дали задачку про обратный рюкзак.

Мы, кроме того, умеем почти так же решать обычный рюкзак с бесконечными предметами, если решить его для отрезка [1..m], то есть получить многочлен с коэффициентами 1 там, где можно получить такую сумму и 0 — там где нельзя. К этому многочлену нужно на отрезкок [m+1..2m] добавить единицы в те позиции, где есть предметы. Потом полученный многочлен возвести в квадрат. Тогда мы решили задачу за . Мне интересно, это боян?

UPD: это все бред, недостаточно просто возводить в квадрат =(

UPD: но достаточно два раз возвести в квадрат!

Всем привет! Этот раунд готовим я и KAN. Надеюсь, многим понравятся наши задачи.

Хочу сказать спасибо PavelKunyavskiy, который тестировал задачи, вычитывал условия и вообще помог. Еще раунд решали alger95, Skird, fdoer, sand-martin, спасибо им за это.

Конечно же огромное спасибо Gerald за организацию нашей работы, MikeMirzayanov за отличную систему и Delinur за перевод условий.

Надеюсь, что в этом раунде будет решено больше задач, чем в нашем предыдущем. Удачи!

Обратите внимание, раунд будет проведен в нестандартное время.

Разбалловка:

div1: 500-1500-1500-2000-2500

div2 : 500-1500-1500-2500-2500

Поздравляю победителей.

div1:

1. al13n
2. tomek
3. niyaznigmatul
4. voover
5. Egor
6. Zlobober
7. White_Bear
8. seanwu
9. wjmsbmr
10. peter50216

div2:

1. fotiIe96
2. zfmdhy786
3. wzc1995
4. gjh
5. mynameisverylong

Разбор на русском: здесь

Решаю задачу 1745 с тимуса.

Кратко: есть n <= 1000 каких-то скобочных последовательностей суммарной длиной не более 10000. нужно из них составить правильную максимальной длины.

Решаю так:

• Пусть есть какое-то множество последовательностей, такое, что кол-во левых и правых скобок в них одинаково (суммарно во всех)
• От каждой последовательности нам нужны две величины: минимальный баланс и суммарный баланс. То есть минимум по (кол-во откр. скобок) — (кол-во закр. скобок) на префиксе и эта же величина для всех строки.
• Отсортируем строки сначала по знаку суммарного баланса, затем, для тех, у которых знак неотрицательный, по невозрастанию минимального баланса, а для тех, у которых знак суммарного баланса отрицательный, по неубыванию.
• Будем делать динамику dp[i][j] — макс. длина последовательности, составленной из первых i строк в отсортированном порядке (возможно, не все используются), такой, что ее суммарный баланс равен j. Переходы можно делать вперед, добавляя очередную i+1 ю строку в этом порядке.

Казалось бы, все стандартно, сомнения только в третьем пункте, но и там, казалось бы, все очевидно. Однако получаю ва9 уже раз эдак в 10й, тщетно выискивая баги.

Буду благодарен за любую помощь!

http://pastebin.com/0C4VYbwJ

Ууупс. Нашел ошибку в решении. Неверно, что строки с отрицательным балансом надо так располагать =(

Просто, для отрицательных нужно считать не (минимальный баланс), а суммарный баланс — минимальный баланс.

Прошу прощения за этот флуд, но решил не прятать в черновики, вдруг кому пригодится.

Да, задача зашла.

Задачи, которые не успели написать, разберу кратко. Задавайте вопросы.

233A - Идеальная перестановка

Идея: Gerald Реализация: tunyash Разбор: fdoer

Эту задачу можно было решать разными способами, например, таким: рассмотрим перестановку p, в которой p_i = i, то есть просто последовательность чисел от 1 до n. Очевидно, для неё условие p_pi = i выполняется всегда. Осталось только преобразовать её таким образом, чтобы выполнялось и второе условие: p_i ≠ i. Для этого поменяем местами каждые два соседних элемента, т.е. для каждого k: k * 2 ≤ n поменяем местами значения p_2k - 1 и p_2k. Нетрудно убедиться, что для полученной перестановки оба условия выполняются всегда.

233B - Неквадратное уравнение

Идея: tunyash Реализация: tunyash, Gerald Разбор: fdoer

Для начала найдем диапазон значений, которые может принимать s(x). Так как из уравнения x² ≤ n, а по условию n ≤ 10¹⁸, x ≤ 10⁹, иначе говоря, десятичная запись любого решения не длиннее 10 цифр. Значит, максимальное значение s_max = s(9999999999) = 10·9 = 90 (на самом деле это грубая оценка, s_max даже меньше, но нам достаточно и её).

Переберем значение s(x): 0 ≤ s(x) ≤ 90. Получаем обычное квадратное уравнение относительно переменной x. Осталось решить его и проверить равенство того значения s(x), что мы зафиксировали, сумме цифр в разрядах полученного корня. Если корень нашелся и равенство выполнено, обновим ответ.

Пожалуй, самое важное в этой задаче — аккуратно и без ошибок вычислений считать дискриминант.

Подчеркну, что для решения задач div2.A и div2.B не требовалось знание массивов.

232A - Циклы

Идея: tunyash, fdoer Реализация: tunyash Разбор: tunyash

Будем добавлять ребра в порядке сортировки сначала по вершине в меньшим номером, затем с большим (просто два for'a). Если добавление ребра вызывает переполнение кол-ва циклов, не добавляем его. Считать количество циклов, которые добавятся можно за O(n) (могут появиться только циклы, содержащие добавленное ребро, следовательно достаточно перебрать третью вершину). Очевидно, что это найдет какой-то ответ, потому что, добавив два ребра из вершины мы всегда можем получить 1 треугольник. Тогда получается, что ответ всегда есть. Можно довольно просто доказать, что мы уложимся в 100. Асимптотика решения O(n³).

Доказательство

• Первыми несколькими шагами алгоритма мы сгенерируем полный граф. Потому что каждое ребро можно будет добавить
• Полученное количество треугольников — C(p, 3) для какого-то p. C(p, 3) ≤ k при этом p максимально.
• Для данных ограничений p ≤ 85.
• После первой фазы алгоритма, если из некоторой вершины мы добавляем u ребер, то количество треугольников увеличивается на C(u, 2).
• Получается, мы представляем маленькое число  ≤ C(85, 2) в виде суммы C(i, 2).
• Первое число, которое мы вычтем, будет отличаться от нашего не более чем на C(85, 1) = 85, поскольку C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
• Второе число — не более чем на C(14, 1) = 14.
• Далее можно применять данную оценку аналогично.
• Для всех возможных k данный алгоритм укладывается в 90 вершин.

Может быть есть что-то более красивое, но вообще на контесте можно было остановиться пункте на пятом и забить.

232B - Таблица

Идея: tunyash, Skird Реализация: tunyash Разбор: tunyash

• Пусть s_i — количество точек в столбце i.

• На картинке изображены два соседних квадрата n × n, A — количество вершин в левой части рисунка (это один столбец), B — количество точек в средней области и C — количество точек в правой области (это тоже один столбец). По условию, имеем:

• Следовательно A = C.
• Таким образом
• Разделим столбцы на классы эквивалентности по признаку . Для всех a и b из одного класса s_a = s_b.
• cnt_a — количество столбцов в классе с .
• Существует (C_n^k)^cnt_a способов нарисовать по x точек в каждом из столбцов этого класса независимо от других классов.
• dp[i][j] — количество способов заполнить классы 1, ... i таким образом, что .
• cnt_i принимает и . Посчитаем (C_n^a)^cnt_i для всех a и cnt_i и будем использовать при подсчете дп. Получаем сложность O(n²·k).

232C - Графы Доу

Идея: tunyash, Gerald Реализация: tunyash, Gerald Разбор: tunyash

Будем рекурсивно разворачивать граф, сводя задачу к поиску кратч. пути в графаз меньших порядков. Заметим, что вершина |D(n - 1)| + 1 — точка сочленения (кроме случаев n ≤ 2, но для них описанные ниже равенства так же выполняются).

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

Пусть dist(a, b, n) — длина кратчайшего пути между a и b в графе порядка n.

Красным обозначены ребра, синим — пути. Записанная формула обозначает, что мы можем пойти из вершины a по пути 1 в вершину 1, затем по прямому ребру в вершину |D(n - 1)| + 1 и по пути 3 в вершину b, либо пойти по пути 2, попасть в вершину |D(n - 1)|, пройти по ребру в вершину |D(n - 1)| + 1, а затем по пути 3 в вершину b. Если обе вершины лежат в меньшей половине графа — то

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

Если искомый путь проходит через точку сочленения, то для каждой вершины мы можем пройти либо в вершину 1, либо в вершину |D(n - 1)| + 1, а затем по прямому ребру в вершину |D(n - 1)| + 1. Если путь не проходит через точку сочленения, то рассмотрим его в графе меньшего порядка.

Можно заметить, что для каждого k будет не более 4 различных запусков dist(i, j, n).

Как это понять? Во первых, если отбросить запросы, где либо a = 1, либо b = |D(n)|, все запросы получаются из первого последовательным отнятием от изначальной пары (a_i, b_i) одинаковых чисел Фибоначчи (по построению D(i) — числа Фибоначчи). Получается, таких запросов будет O(n). Запросы вида (1, a) и (a, |D(n)|) можно рассмотреть отдельно, они хорошо выражаются из самих себя. Учитывая то, что все другие запросы получаются друг из друга прибавлением или отнятием чисел Фибоначчи, запросы этого вида тоже будут получаться друг из друга таким образом. Таким образом, у нас будет не более O(1) серий по O(n) запросов. Это не совсем строго, но, вроде, понятно. Это довольно нетривиальный момент, рекомендую задавать вопросы, если непонятно.

Получим асимптотику на запрос (логарифм возникает из соображения о том, что размеры графов в зависимости от порядка растут экспоненциально). Важно было запускать алгоритм не для данного n, а для наименьшего n, такого, что max(a, b) ≤ D(n - 1)

232D - Забор

Идея: tunyash, Gerald Реализация: fdoer Разбор: fdoer

В разборе этой задачи подразумевается, что читатель имеет представление о суффиксных массивах и о быстром нахождении lcp (наибольшего общего префикса) двух суффиксов строки. Об этом можно почитать, например, на e-maxx.ru.

Итак, пусть d и d' — массивы такие, что d_i = h_i - h_i + 1, d'_i =  - d_i для любого 1 ≤ i ≤ (n - 1). Тогда мы можем переформулировать условие, при котором два куска забора считаются подходящими, следующим образом:

• куски не пересекаются, то есть, нет ни одной доски, такой, что она содержится в обоих кусках забора;
• куски имеют одинаковую ширину;
• для любого i (0 ≤ i ≤ r₁ - l₁ - 1) выполняется d_l1 + i = d'_l2 + i (если ширина забора — 1, это выполняется всегда).

Отсюда возникает следующая идея: для ответа на запрос нам достаточно узнать, сколько подотрезков массива d' длины (r - l) совпадают с отрезком массива d, соответствующим этому запросу, и при этом не пересекаются с ним ни в каком индексе. Построим суффиксный массив sa на последовательности-конкатенации массивов d и d', между которыми поставим еще разделитель — число, которого ни в одном из этих массивов нет. Запомним также для каждого суффикса d_i его позицию pos_i в суффиксном массиве. При поступлении нового запроса на отрезке l...r все куски забора, подходящие по второму и третьему условиям, будут началами суффиксов, лежащих в суффиксном массиве подряд на позициях bound_left...bound_right, причем bound_left ≤ pos_l ≤ bound_right и lcp(bound_left...bound_right) ≥ (r - l). Поэтому границы этого отрезка можно найти с помощью бинарного поиска. В зависимости от реализации функции lcp для отрезка значения bound мы определим за или за .

Теперь осталось найти число позиций из sa_{boundleft...boundright}, удовлетворяющих еще и первому условию, т.е. таких, которые соответствуют суффиксам d', префикс длины r - l которых не пересекается по индексам с отрезком (l...r - 1). Иными словами, количество i (bound_left ≤ i ≤ bound_right) таких, что либо n + 1 ≤ sa_i ≤ n + l - (r - l) - 1, либо sa_i ≥ n + r (суффиксы d' начинаются в конкатенации с позиции n + 1, т.к. в массиве d (n - 1) элемент, а на n-ном месте расположен разделитель). Это тоже классическая задача поиска количества чисел из заданного диапазона на заданном отрезке массива, она может быть решена за на запрос.

Её можно решать, например, offline с помощью метода scanline и любой структуры данных, поддерживающей запросы суммы на отрезке и увеличения в точке, либо online с помощью персистентных/двумерных структур вроде дерева отрезков.

Таким образом, вкратце алгоритм выглядит примерно так:

• построение массивов d и d'. Построение на конкатенации суффиксного массива.
• препроцессинг для вычисления lcp на отрезке

Для каждого запроса:

• определение промежутка (bound_left...bound_right) с помощью двух бинарных поисков, обращающихся к lcp на отрезке.
• запрос на число суффиксов, которые лежат в суффиксном массиве на этом промежутке и которые соответствуют подотрезкам, не пересекающимся с отрезком запроса.

Если массив строить за , запрос lcp выполнять за O(1) с предподсчетом за (с RMQ на разреженных таблицах), а числа из диапазона искать за на запрос, итоговая асимптотика получается . Однако решения, выполняющие запрос lcp за логарифм с использованием, например, дерева отрезков, тоже укладывались в ограничения.

232E - Быстрая Черепаха

Идея: tunyash Реализация: tunyash, KAN Разбор: tunyash

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

С помощью этих данных мы получим ответы на все запросы, точки которых лежат по разные стороны от выбранного столбца за n/32 на запрос (просто сделаем and битсетов). На картинке кружочками обведены две клетки, через которые может проходить путь между точками запроса.

Далее запустимся от двух половинок доски, выполняя тот же алгоритм. Получается время работы .

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

Альтернативное решение от mrNobody. Оно оказалось быстрее и проще авторского, но, к сожалению, он не смог сдать его на контесте.

• Будем считать динамику range[i][j][k] — самую верхнюю и самую нижнюю клетку столбца k, доступную из клетки (i, j). Ее можно считать аналогично динамике из авторского решения.
• Кроме того посчитаем динамику able[i][j][k] — доступна ли хотя бы одна клетка столбца k из клетки (i, j) при движении влево и вверх.
• Обе эти динамики можно посчитать за O(n·m²) времени и памяти (потом будет понятно, что на памяти можно сэкономить).
• Рассмотрим запрос (x₁, y₁) (x₂, y₂). Утверждается, что путь из (x₁, y₁) (x₂, y₂) существует тогда и только тогда, когда и верно able[x₂][y₂][y₁].

• Действительно, рассмотрим три пути. 1 — из (x₁, y₁) в самую верхнюю доступную клетку столбца y₂. 2 — из (x₁, y₁) в самую нижнюю доступную клетку столбца y₂ и 3 — из (x₂, y₂) в одну из клеток столбца y₁. Если эта клетка расположена ниже (x₁, y₁), то путь 3 пересекает путь 2, а значит мы можем пройти по пути два до точки пересечения, а затем по пути 3 до точки (x₂, y₂).
• Случай пересечения путей 1 и 3 аналогичен.
• Мы получили решение за O(n·m² + q) времени и такое же количество памяти, однако можно заметить, что хранить все состояния динамики не обязательно, достаточно только q из них. Пользуясь этим, можно сократить используемую память до O(nm + q).

Всем привет!

Сегодня состоится очередной codeforces-round. Он пройдет в обоих дивизионах, в каждом из которых будет предложено пять задач разной сложности.

В его подготовке, принимало участие несколько человек: KAN, fdoer, Skird, tunyash. Огромное спасибо Gerald, за координацию подготовки задач, множество клевых идей и понятизацию условий. Так же благодарю MikeMirzayanov за отличную систему подготовки задач, Delinur за перевод условий.

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

Удачи!

UPD: разбалловка стандартная (500-1000-1500-2000-2500) в обоих дивизионах.

UPD: появился очень кратенький разбор

UPD:

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

1. tourist
2. rng_58
3. Mimino
4. Dmitry_Egorov, Egor

div2:

1. debug22
2. ryz
3. dvdreddy
4. vinodreddy
5. rdivyanshu

UPD: есть полный разбор на русском.

GSS4.

Собственно, нужно уметь брать сумму на отрезке и уметь каждый элемент отрезка заменять квадратным корнем из него, округленным вниз. Сумма всех элементов изначально не превосходит 10¹⁸

Я придумал решение за ( и я не уверен ли это). Идея тупая: каждое число станет единицей, если взять корень 7 раз. Тогда заведем 7 декартовых деревьев, первое из которых будет хранить текущий массив, второе — корни из его элементов, третье — корни из корней и так далее. при запросе на замену на корень вырежем из каждого нужный отрезок и сделаем циклический сдвиг вырезанных отрезков. Отрезок дерева, который мы вытащили из самого первого дерева зальем единичками (после этого вставим в последнее).

Такое решение дает ТЛ. Интересно, можно ли быстрее и/или проще?

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

Задача <<Экзамены>> По условию 2n ≤ k ≤ 5n. Если k < 3n то некоторые экзамены мы сможем сдать только на 2. Таких будет 3n - k. Если же 3n ≤ k, то мы все экзамены сдадим как минимум на три.

Задача <<Квадрат>> Пусть карандаш идет по прямой и ставит крестики через каждые (n + 1) точку. Поставим в соответствие положению на прямой положение на квадрате. А именно, точке x на прямой будет соответствовать точка, в которую придет карандаш, сдвинувшись по периметру квадрата на x. Тогда левому нижнему углу квадрата соответствуют все точки вида 4np для некоторого целого неотрицательного p. Поставленным крестиками будут соответствовать точки k(n + 1). Самая ближайшая точка совпадения двух семейств, за исключением начальной, будет в LCM(n + 1, 4n) (LCM — НОК). Тогда всего мы поставим крестиков.

Задача <<Разрезание фигуры>>

Основная идея: учитывая, что ответ не превышает двух, проверим существование ответа 1.

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

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

Еще нужно было не забыть, что иногда ответа может просто не существовать. Это бывает тогда, когда площадь фигуры меньше либо равна двум (площадь фигуры — кол-во клеток в ней)ю

Асимптотика решения O(n⁴). Еще можно было воспользоваться алгоритмом поиска точек сочленения и решить эту задачу за O(n²). Но это, наверное, требовало больших трудозатрат.

Задача <>

Основная идея: перебор за O(F_un). F_u — u-е число Фибоначчи.

У этой задачи было довольно сложное условие. С массивом a можно было проводить операции двух типов. Нужно было провести ровно u таких операций, чтобы максимизировать сумму значений массива с заданными коэффициентами.

Если просто перебрать все возможные комбинации операций, а потом промоделировать их, то получится решение за O(2^u·nu). Это слишом долго. Можно было улучшить это решение, перебирая комбинации операций рекурсивно и по ходу рекурсии моделируя их. Тогда асимптотика улучшается до O(2^u·n). Собственно, ничего сильно лучше этого решения не требовалось. Возникает лишь одно соображение: если у нас были две операции подряд, то они ничего не изменили и их можно переместить в любое место нашего алгоритма, не изменив его результат. Тогда можно перебирать только те алгоритмы, в которых все парные операции стоят в конце. Это тоже можно было делать рекурсивно, не идя в ветки с двумя, подряд идущими операциями и обновляя лучший ответ не только в конце рекурсии, но и тогда, когда в конце осталось четное число операций. Это работает сильно лучше. Вспомнив известную задачу "кол-во последовательностей из нулей и единиц, без двух единиц подряд" можно понять, что кол-во таких последовательностей, длиной k, равно F_k + 1, где F_i — i-е число Фибоначчи. Тогда кол-во допустимых алгоритмов равно сумме первых u чисел Фибоначчи. Эта сумма примерно равна (u + 2)-му чмслу Фибоначчи. Итоговая асимптотика составляет O(F_u·n). Для максимальных значений входных данных эта величина равна примерно 30 миллионам.

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

Задача <<Расстояние Хемминга>>

Основная идея: сведение к СЛАУ и решение ее методом Гаусса.

Заметим, что если мы одинаковым образом переставим символы во всех строках, то ответ не изменится. Рассмотрим <<столбцы>> ответа, то есть строки s_1, i + s_2, i + s_3, i + s_4, i для некоторого i. Всего существует 2⁴ = 16 типов таких строк. Получается, что, если существует ответ на задачу, длины l, то существует и ответ той же длины в котором столбцы упорядочены по типу. Тогда, чтобы перебрать ответ, достаточно перебрать 16 чисел — количества столбцов каждого типа. По этим числам легко восстановить все расстояния Хемминга. Расстояние между строками s_i и s_j будет равно сумме количеств столбцов в которых различны символы c номерами i и j.

Однако перебирать все возможные количества столбцов каждого типа слишком долго. Заметим, что мы можем записать систему из 6 уравнений с 16 неизвестными (вспомнив, что расстояние между строками s_i и s_j будет равно сумме количеств столбцов в которых различны символы c номерами i и j). Неизвестными в этой системе уравнений будут количества столбцов каждого из типов. Заметим, что некоторые варианты столбцов полностью идентичны с точки зрения вклада, вносимого в расстояния Хемминга. А именно, столбцы, получаемые друг из друга инвертированием всех букв (заменой <> на <> и наоборот) вносят идентичный вклад в расстояния Хемминга. Например, если добавить в ответ столбец <>, расстояния Хемминга между всеми парами строк изменятся тем же образом, что и при добавлении столбца <>. Получается, что мы можем рассматривать лишь 8 возможных столбцов. Кроме того, столбцы <> и <> вносят нулевой вклад во все расстояния Хемминга. Один из них мы уже исключили из рассмотрения, но можно исключить и второй. Таким образом, мы сократили количество переменных до 7. Решим СЛАУ относительно каких-нибудь шести переменных. Свободным осталось значение одной из переменных. Так как столбцы, количеству которых соответствует эта переменная, вносят ненулевой вклад хотя бы в одно расстояние Хемминга, значение этой переменной не может превосходить максимума из заданных расстояний Хемминга. Тогда можно перебрать его и выбрать наилучший из получившихся ответов.

Алгоритм получается следующий:

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

Асимптотика этого решения составляла O(max(d_i, j)), если пользоваться типом double и , если решать задачу в рациональных числах.

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

Задача <<Два отрезка>>

Основная идея: обратить перестановку и решать упрощенную задачу (см. ниже), рассмотреть функцию <<количество отрезков в перестановке, которые образуют данный отрезок натурального ряда>>.

Чтобы решить эту задачу, можно решить обратную: <<дана перестановка p_n, нужно посчитать в них количество отрезков, элементы которых образуют 1 или 2 отрезка натурального ряда>>.

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

Первое решение, которое приходит в голову: переберем отрезок перестановки и в булевом массиве отметим элементы, принадлежащие ему. Проверим, что в булевском массиве получилось два отрезка. Такое решение будет иметь асимптотику O(n³).

После некоторых размышлений можно понять, что при переходе от отрезка пере [l, r] к [l, r + 1] количество отрезков изменится некоторым предсказуемым образом. Обозначим s([a, b]) количество отрезков, которые образуют элементы отрезка [a, b] перестановки. Если новый элемент p_r + 1 будет находиться между уже поставленными элементами (то есть, элементы со значениями p_r + 1 - 1 и p_r + 1 + 1 будут принадлежать отрезку [l, r]), то s([l, r + 1]) = s([l, r]) - 1. Новый элемент <<склеит>> два отрезка между которыми появится. Если у элемента p_r + 1 будет один сосед, принадлежащий отрезку [l, r], то s([l, r]) = s([l, r + 1]) (один из существующих отрезков удлинится). Если же у элемента p_r + 1 не будет соседей на отрезке [l, r], то новый элемент образует новый отрезок и s([l, r + 1]) = s([l, r]) + 1. Это иллюстрирует рисунок ниже:

Новый элемент помечен красным, уже поставленные — черным.

Из этих соображений можно получить следующее решение: переберем левую границу и, перебирая правую слева направо, будем пересчитывать количество отрезков, которые образует текущий отрезок перестановки. Если это число равно 1 или 2, прибавим к ответу единицу. Получаем асимптотику O(n²). Это решение работало достаточно быстро даже на n = 20000. Но, разумеется, этого было недостаточно, чтобы решить задачу.

Перейдем к полному решению. Оно основывается на предыдущем. Мы уже умеем пересчитывать число отрезков при движении правой границы. Теперь нужно понять, как найти s([l - 1, r]) для любых r, используя s([l, r]). Будем перебирать позицию левой границы отрезков справа налево и поддерживать структуру данных, которая позволит нам хранить s([l, r]) для всех r и сможет считать в себе количество чисел 1 и 2.

Обозначим за Δ_i s([l - 1, i]) - s([l, i]). Δ_l = 1 так как один элемент образует ровно 1 отрезок. Далее, если мы будем увеличивать i, Δ_i будет зависеть от количества соседей элемента l на отрезке [l - 1, i].

• Если на отрезке нет соседей l, то количество отрезков, которым он соответствует увеличится на 1 при добавлении элемента l (так как l не присоединится ни к какому существующему отрезку).
• Если на отрезке ровно один сосед l, то количество отрезков, которым он соответствует не изменится при его добавлении (так как l просто присоединится к отрезку своего соседа).
• Если на отрезке два соседа l, то при его добавлении, количество образуемых отрезков уменьшится на 1.

Найдем соседей l, лежащих после него. Обозначим их за a и b. (если после l лежит только один его сосед, b = inf) тогда для всех i, таких что l ≤ i < a Δ_i = 1. Для всех i, таких что a ≤ i < b Δ_i = 0 и для всех i удовлетворяющих b ≤ i ≤ n Δ_i =  - 1. Тогда, чтобы обновить нашу структуру достаточно сделать два прибавления на отрезке.

На картинке выше видно, что у элемента 5 оба соседа лежат правее его. Поэтому получается три отрезка эквивалентности Δ_i (первый из них находится в самом элементе 5). После первого встреченного соседа (4) Δ_i принимает значение 0 и, наконец, начиная с соседа 6, Δ_i принимают значение  - 1.

Остается только придумать структуру, позволяющую прибавлять на отрезке +1 и -1 и искать в семе числа 1 и 2. Во-первых, заметим, что неположительных чисел структура хранить не будет. Тогда числа 1 и 2 будут являться первым или вторым минимумом в структуре. Тогда структуре достаточно уметь искать два минимума в себе и уметь прибавлять +1 и -1 на отрезке. Два минимума ищутся почти так же, как и один, поэтому можно адаптировать дерево отрезков или sqrt-декомпозицию под эти цели. Сумма ответов структуры на каждой итерации будет ответом на задачу. Авторская sqrt-декомпозиция работала 1.3 секунды, авторское дерево отрезков — 1.1 секунды. sqrt-декомпозиция на Java — 3.6 секунд.

Задача <<Число Фибоначчи>>

Решение: baby-step-giant-step

В этой задаче было дано некоторое число Фибоначчи f по модулю 10¹³, требовалось определить его первое вхождение в последовательность (позицию).

• Рассмотрим два взаимно простых модуля, делящих 10¹³. Пометим их как a и b.
• Остаток от деления f на a будет равен остатку от деления настоящего числа Фибоначчи F, такого, что . ().
• Найдем вхождения в период последовательности Фибоначчи по модулю a.
• Найдем вхождения в период последовательности Фибоначчи по модулю b.
• Зафиксируем пару этих вхождений. Пусть вхождение в последовательность Фибоначчи по модулю a будет в позиции i, а по модулю b — в позиции j.
• Обозначим за t(m) период последовательности Фибоначчи по модулю m.
• Из Китайской Теоремы об Остатках следует, что t(ab) = LCM(t(a), t(b)) (так как a и b выбраны взаимно простыми).
• Тогда по зафиксированным вхождениям f по модулям a и b можно восстановить вхождение f в последовательность по модулю ab. Это можно сделать, решив Диофантово уравнение i + t(a)·x = j + t(b)·y. Это уравнение можно решить перебором одного из корней.
• Если найденное вхождение в последовательность по модулю ab обозначить за u, то все вхождения f в последовательность по модулю 10¹³ будут представимы в виде t(ab)·k + u. Тогда переберем k и найдем все вхождения f в последовательность Фибоначчи по модулю 10¹³. Чтобы получить из числа Фибоначчи на позиции α, чиcло Фибоначчи на позиции α + t(ab) нужно домножить вектор из F_α и F_α + 1 на некоторую матрицу.
• Выберем a = 5⁹ и b = 2¹³. Заметим, что никакое число не входит в период последовательности Фибоначчи по каждому из этих модулей более 8 раз. Тогда пар вхождений будет не более 64. Для каждого вхождения мы переберем до чисел.

Еще можно было более эффективно воспользоваться тем, что число вхождений любого числа в период последовательности Фибоначчи по модулям вроде 10^k невелико. Можно было получать из вхождений числа f в последовательность по модулю 10ⁱ получить вхождения по модулю 10(i + 1) подобно тому, как в авторском решении осуществляется переход от модуля ab к модулю 10¹³.

Привет всем! Я автор задач сегодняшнего раунда. Меня зовут Артур, я учусь в лицее №31 города Челябинска.

Благодарю Gerald за координацию подготовки контеста, Delinur за перевод условий, MikeMirzayanov за замечательную систему, dolphinigle за прорешивание контеста, вычитывание условий и множество ценных советов, fdoer, grey_wind, Skird и alger95 за помощь в придумывании задач.

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

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

UPD: Разбалловка следующая:

В первом дивизионе: 500-1000-2000-2000-2500.

Во втором дивизионе: 500-1000-1500-2000-3000.

UPD2: появился разбор Пока частичный и на русском. скоро будет больше.

Поздравляю победителей, особенно решивших задачу D.

Div1:

1. Petr
2. tourist
3. yeputons
4. peter50216
5. aram90

Div2:

1. lucien
2. tomasz.kociumaka
3. sjynoi
4. DimaPhil

http://www.ioi-jp.org/apio2012/ — asian pacific informatics olympiad. Был утренний тур, который недавно закончился, но будет еще второй, такой же, вечером. Предлагаю после него обсудить задачи.

Недавно прочитал, что узнавать, кто выигрывает в ним, в котором разрешено брать камни из не более, чем k кучек (при этом нужно взять хотя бы один камень хотя бы из одной кучки), довольно легко. Оказывается, достаточно просто выписать все двоичные записи величин кучек и просуммировать биты каждого столбика по модулю (k+1). Если в результате везде нули — первый игрок проиграл. К сожалению, моих знаний языка и математики не хватило, чтобы понять доказательство. Был бы благодарен, если бы кто-нибудь растолковал.

Я нашел задачу, где, собственно, просто надо вывести, кто выигрывает и восстановить выигрышный первый ход: ipc.susu.ac.ru

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