Идея: I_love_myself
Решение: 77904333

Привет, Codeforces!

Рад пригласить вас на Codeforces Round 637 (Div. 1) - Thanks, Ivan Belonogov! и Codeforces Round 637 (Div. 2) - Thanks, Ivan Belonogov!, которые пройдут в 23.04.2020 17:45 (Московское время). Раунд будет рейтинговым для обоих дивизионов (я надеюсь).

Все задачи были придуманы и подготовлены Алексеем Aleks5d Упирвицким, Алексеем alexX512 Перевышиным и мной, Денисом I_love_myself Сапожниковым.

Большое спасибо нашим многочисленным тестерам: 300iq, voidmax, ashmelev, Akulyat, okwedook, Minnakhmetov, divanik, Zakoden, Jostic11, Nakinamo, 4qqqq и allisyonok за тестирование задач и ценные советы, isaf27 за координирование и помощь в подготовке раунда и MikeMirzayanov за отличные системы Codeforces и Polygon.

Вам будет дано 6 задач в обоих дивизионах и 2.5 часа на их решение. Советую прочитать все задачи. Удачи, высокого рейтинга и удовольствия от решения задач!

Разбаловка будет объявлена ближе к началу раунда.

Уже заметили необычное в названии раунда? Вот короткое сообщение от MikeMirzayanov:

Этим раундом мы хотим передать пламенный привет и еще раз сказать спасибо за поддержку Ивану Belonogov Белоногову. И дело не только в существенном подарке по случаю 10-летия платформы. Начав участвовать в 2011-м, Иван прошел долгий путь от участника раундов второго дивизиона до международного гроссмейстера, стал чемпионом мира ICPC в составе команды ИТМО. Такой вот яркий мотивационный пример success story! Спасибо, Иван!

UPD1: Разбаловка будет следующая:
Div1: 500-750-1250-1750-2250-3000
Div2: 500-1000-1500-1750-2250-2750

UPD2: Из-за технических проблем раунд переносится на 10 минут. Извините за неудобства!

UPD3: Разбор опубликован!

UPD4: Это был наш первый раунд на codeforces и мы сделали ошибки везде где только можно, приношу свои огромные извинения. Мы обсудили всё и приняли решение: Div1 раунд будет не рейтинговым, Div2 останется рейтинговым. Более подробно вы можете прочитать в этом посте. Надеемся, что вы насладились решением интересных задач и не стали обращать внимание на наши ошибки.

Добрый день, я знаю, что сейчас все предложения контестов рассматриваются очень-очень долго, некоторые ждут по полгода и это весьма обоснованно.
Но тем не менее, хотелось бы узнать, как можно ускорить рассмотрение любого конеста (чтобы тратить меньше времени с обеих сторон) : может быть подготовить задачи на полигоне, добавить в соавторов красно-желтых друзей, которые уже видели эти задачи и тоже могут немного помочь с подготовкой, подружиться с MikeMirzayanov?

Добрый день, мой вклад упал я давно не писал ничего полезного, поэтому надо что-то написать.
0) Постановка задачи и реализация. Хотим лексикографически отсортировать все суффиксы (или циклические сдвиги) строки s по возрастанию. Суффиксный массив — это такая перестановка p чисел от 0 до n — 1, что p[i] — обозначает позицию начала лексикографически i-того суффикса строки, то есть это то, что позволит решить нашу задачу.
Для построения суффиксного массива мы будем использовать классы эквивалентности — c[i][len], которое обозначает, что циклический сдвиг, начиная с i-той позиции длины len имеет класс эквивалентности $$$c[i][len]$$$. При чем для двух классов эквивалентности $$$c[i][len]$$$ и $$$c[j][len]$$$ будет верно, что $$$c[i][len] == c[j][len]$$$ тогда и только тогда, когда соответствующие подстроки равны, а $$$c[i][len] < c[j][len]$$$ тогда и только тогда, когда i-тая подстрока лексикографически меньше j-той. Таким образом, если мы расставим классы для длины $$$len >= len(s)$$$, то мы очень просто сможем восстановить перестановку p.
Пусть мы расставили классы для длины len. Расставим для длины 2 * len. Но заметим, что класс c[i][2 * len] описывается парой $$$\{c[i][len], c[i + len][len]\}$$$, то есть какой результат сравнения будет у двух таких пар, такой будет и у соответствующих суффиксов. Поэтому мы можем отсортировать все пары и расставить новые классы для длины 2 * len, а сложность будет $$$O(\log n * n \log n) = O(n \log^2 n)$$$, так как мы будем увеличивать длину как степень двойки ($$$\log n$$$), а на каждой итерации мы будем сортировать n пар обычной сортировкой ($$$n \log n$$$).

Многие (в том числе и я) не любят суфмасс из-за его громоздкости и не очень понятной реализации, в которой легко набагать. На e-maxx, например, он занимает 50 строк и строки вида $$$p[--cnt[c[pn[i]]]] = pn[i];$$$ не очень крутые.

1) Моя реализация за $$$O(n \log^2 n)$$$:

vector<int> sufmas(vector<int> c) {
	int n = c.size();
	vector<pair<pair<int, int>, int>> t(n); //t[i] = { { first class, second class }, position }
	for (int i = 1; i < n; i <<= 1) {
		for (int j = 0; j < c.size(); j++)
			t[j] = { { c[j], c[(j + i) % n] }, j };
		sort(t.begin(), t.end());
		for (int cnt = 0, j = 0; j < n; j++) {
			if (j && t[j].first != t[j - 1].first)
				cnt++;
			c[t[j].second] = cnt;
		}
	} 

	vector<int> p(n);
	for (int i = 0; i < n; i++)
		p[c[i]] = i;
	return p;
}

2) Чтобы убрать лишний логарифм в сложности, можно воспользоваться цифровой сортировкой, которая лучше использует то, что на предыдущем шаге мы уже отсортировали суффиксы меньшей длины.
Тут задумывалась моя короткая реализация суффиксного массива за $$$O(n \log n)$$$, однако на практике мы выяснили, что она работает дольше первой, поэтому я оставлю здесь ссылку на короткую реализацию от Пядеркина за аналогичную асимптотику.
Также хочу сказать спасибо за помощь в написании этого поста Holidin, ismagilov.code и SpeedOfMagic

Добрый день, каждый раз, когда я пишу длинку, мне больно

Всем привет, не могли бы вы покидать мне задачки на персистентное ДО разных уровней сложности?
Спасибо!

Всем привет, мне так понравилось как растет мой вклад я вижу, что вам понравился разбор в предыдущем посте, поэтому я решил периодически рассказывать о разных задачах, во многом, с применением не очень сложных структур данных.
Сегодня я рассажу вам об оптимизациях дерева отрезков и декартовых деревьях(все вещи аналогичны ДО), позволяющих скинуть лишний логарифм в асимптотике, также разберу одну подзадачу, позволяющую решать кучу задач.
Будут разобраны:
1. Двоичный спуск
2. Fractional cascading
3. Задачи с удалением и добавлением элементов

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

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

Необходимо реализовать структуру данных, выполняющих 2 типа запросов:
- Изменить элемент в массиве
- Найти сумму различных элементов с L по R.