Идея: I_love_myself
Решение: 77904333
Решение: 77904408
Идея: Aleks5d
Решение: 77904455
Решение: 77770331
Решение: 77904646
Решение: 77904714
Решение: 77904971
Огромное спасибо Holidin за помощь в подготовке этой задачи.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Идея: 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.
Название |
---|