Добрый вечер, друзья!

За обсуждением животрепещущей темы использования чужого кода в своих решениях можно и не заметить, что приближается зима 188 раунд платформы Codeforces!

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

Мы — это авторы задач yaro и Rei, куратор раундов Codeforces Gerald и автор системы MikeMirzayanov. Отдельное спасибо Паше (PavelKunyavskiy) и Артему (RAD) за тестирование и дельные замечания.

Последний раз, когда я участвовал в проведении соревнования на Codeforces, раунды еще носили статус "beta". Но чем меньше "beta", тем больше ответственность. В связи с этим желаю организаторам и авторам еще одного успешно проведенного раунда. Участникам же — нестандартных задач и идей, чистого кода (а также чистой клавиатуры) и побольше правильно сданных решений!

Нам представляется непростой задачей оценить уровень сложности задач для всей массы участников, поэтому разбалловка будет динамическая. Все же ради любопытства сделаем следующее предположение об относительной сложности задач: div.1: B-B-C-C-E, div.2: A-B-C-C-E. Угадаем ли?

UPD Приносим извинения за проблемы с очередью тестирования Codeforces.

В любом случае, нам будет очень приятно, если вы оцените наш раунд (после его завершения): short survey.

В упорной борьбе с отрывом в один взлом победителем div.1 стал meret (Jakub Pachocki)!

Доступны результаты первого дивизиона, результаты второго дивизиона.

Разбор.

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

Возьмем, к примеру, ключевой момент кода — переход динамики. Один из этих вариантов (угадайте, какой) прошел вчера претесты, но этим дело и ограничилось — получил вердикт WA (по точности) на каком-то объемном тесте.

А теперь вопрос: как вы думаете, какие из этих вариантов получают ОК по задаче? Почему?

Версия 1:

for (int j = 0; j < p[u].length; j++) {
	double np = (1 - (double) j / a[u]) * p[u][j];
	if (j < p[u].length - 1) {
		np += (double) (j + 1) / a[u] * p[u][j + 1];
	}
	p[u][j] = np;
}

Версия 2:

double frac = (double) 1 / a[u];
for (int j = 0; j < p[u].length; j++) {
	double np = (1 - j * frac) * p[u][j];
	if (j < p[u].length - 1) {
		np += (j + 1) * frac * p[u][j + 1];
	}
	p[u][j] = np;
}

Версия 3:

for (int j = 0; j < p[u].length; j++) {
	double np = (double) (a[u] - j) / a[u] * p[u][j];
	if (j < p[u].length - 1) {
		np += (double) (j + 1) / a[u] * p[u][j + 1];
	}
	p[u][j] = np;
}

D. Мощный массив.
Будем решать задачу оффлайн за время O(n sqrt(t)) и O(n) памяти. Для простоты рассуждений будем считать, что запросов n.

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

Обход запросов в произвольном порядке, разумеется, обойдется нам в O(nt) шагов.
Пусть p = sqrt(n). Разобьем массив на p равных частей Q_1, ... Q_p. Теперь рассмотрим запросы вида (Q_i, Q_j) по всем i и j (их будет приблизительно n). Очевидно, никакой порядок обхода не даст нам количество шагов, меньшее O(n sqrt(n)), так как на переход от одного интервала к другому в
любом случае потребуется хотя бы sqrt(n) шагов.

Тем не менее, порядок обхода, гарантирующий O(n sqrt(n)) ходов в худшем случае, существует.
Отсортируем интервалы запросов по следующему правилу: сначала идут те, левый конец которых лежит в Q_1, затем те, левый конец которых лежит во Q_2 и так далее до Q_p. Если же левые концы запросов лежат в одной части, то раньше идет тот запрос, у которого правый конец меньше.

Проследим за шагами левых и правых концов при таком подходе. Левые концы в одной группе Q_i совершают <= n / p шагов, при переходе к Q_{i+1} <= 2 * n / p шагов. Поэтому всего левые концы совершают <= n / p * n + 2*n шагов (второе слагаемое порядка O(n), оно неинтересно).
Правые концы в одной группе движутся только вправо, это дает <= n * p шагов в ходе всего процесса, при переходе же к следующему Q_i грубо оценим переход n шагами, поэтому в итоге имеем <= 2 * n * p шагов.
Итого количество шагов <= n/p * n + 2 * n * p. Выбирая p, равное sqrt(n), получаем нужную асимптотику.

Решение: сортируем запросы по описанному правилу, затем в лоб переходим от одного запроса к другому в этом порядке.

Замечание 1. Никакой особенности, кроме неаддитивности, у функций из условия не было.

Замечание 2. В случае n, не равного t, получается оценка 2 * n * sqrt(t), и она точна (если внимательно проследить за доказательством, легко построить подпирающий оценку тест).

E. Длинная последовательность.

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

Для начала решим чуть более частную задачу. Предположим, что c₁, c₂, ..., c_k и a₀, a₁, ..., a_k - 1 нам уже даны и мы хотим проверить является ли последовательность {a_i} построенная по ним длинной. Если она периодична, то среди k-кортежей a_s, a_s + 1, ..., a_{s + k - 1} встречаются все ненулевые k-кортежи. Поэтому нет разницы с какого из них начинать последовательность. Поэтому свойство последовательности <<быть длинной>> зависит только от c_i, и a₀, a₁, ..., a_k - 1 мы можем выбрать любыми удобными. Будем теперь считать, что a₀, a₁, ..., a_k - 2 --- нули и a_k - 1 = 1.

Рассмотрим матрицу перехода A последовательности: при i < k ее i-ая строка равна (0, 0, ... 0, 1, 0, ..., 0), где 1 стоит на (i + 1)-ой позиции, а последняя строка равна (c_k, c_k - 1, ..., c₂, c₁).

Обозначим x_s вектор-столбец (a_s, a_s + 1, ..., a_{s + k - 1})^T.
Тогда для любого целого s: A· x_s = x_s + 1.
Последнее равенство это просто переформулировка рекуррентного соотношения:

Но мы выбрали x₀ = (0, 0, ..., 0, 1), поэтому ясно, что вектора x₀, x₁, x₂, ..., x_k - 1 образуют базис. Отсюда если A^p· x_i = x_i для всякого i, то A^p --- единичная матрица.

Таким образом, нам достаточно сделать следующее:

1) Построить матрицу A по коэффициентам c_i.

2) Проверить, что A^2k - 1 --- единичная матрица. (Если нет, то 2^k - 1 не период.)
Если 2^k - 1 период, то нам осталось проверить, что он минимальный. Любой период делится на минимальный, поэтому нам надо проверить лишь делители 2^k - 1.

3) Построить все максимальные делители 2^k - 1 и проверить, что они не периоды (снова с помощью A).

(Под максимальным делителем n подразумевается делитель вида n/q, где q --- простое).

Все что нам осталось заметить, так это то, что такие последовательности всегда существуют. Более того, количество подходящих наборов c_i довольно велико. Можно показать, что их ровно (так как они соответствуют коэффициентам неприводимых множителей круговых многочленов над ). Поэтому можно просто брать произвольный набор и проверять его, достаточно скоро мы получим подходящий.

Добрый день, участники и зрители!

Напоминаю вам, что подходит к концу отборочная стадия открытого турнира Яндекса по программированию "Яндекс.Алгоритм".
Вместе с тем это означает, что пришло время самого главного её события: отбора на финальный раунд, который пройдет в июле, на базе Летней школы Яндекса.
Это значит, что сегодня двести лучших участников турнира (по результатам предыдущих отборочных раундов) сразятся за право попасть в Топ-15 мирового олимпиадного сообщества.

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

Обращаю внимание, что сегодня стоимости задач будут следующие - 500, 1000, 2000, 2500, 2500.
В связи с этим у меня персональная просьба к участникам: не забудьте прочитать условия всех задач,
ведь упорядочивание по сложности - вещь сугубо субъективная.

Раунд будет рейтинговым для всех участников.

Желаю удачи участникам, всем же остальным - зрелищного раунда!

Раунд завершен. Согласно результатам, 19 участников решило хотя бы три задачи, один (победитель) решил четыре. Первые три места заняли Петр Митричев, Геннадий Короткевич и Сергей Копелиович.

Кроме того, определились пятнадцать финалистов, и это: Petr, tourist, Burunduk1, ivan.metelsky, dzhulgakov, e-maxx, LayCurse, rng_58, pieguy, zeliboba, ktuan, levlam, wata, dolphinigle, Progger .

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