This blog is a submission for the Third Codeforces Month of Blog Posts, thanks to cadmiumky for the initiative!

Thanks to TeaTime and k1r1t0 for giving feedback on the post.

Hi everyone!

I want to talk about Gale-Ryser Theorem and some of its applications. I've provided proofs for each fact in the blog, they're hidden under the spoilers.

Gale-Ryser Theorem

We have an array of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ and an array of $$$m$$$ positive integers $$$b_1, b_2, \ldots, b_m$$$, $$$b_i \le n$$$. The array $$$b$$$ describes a sequence of operations, in the $$$i$$$-th operation we need to decrease the values at $$$b_i$$$ positions by $$$1$$$, formally pick $$$b_i$$$ unique indices $$$j_1, j_2, \ldots, j_{b_i}$$$ and decrease $$$a_{j_p}$$$ by $$$1$$$ for $$$1 \le p \le b_i$$$. We want to know if it's possible to have all $$$a_i \ge 0$$$ after the operations.

Without loss of generality $$$b_1 \ge b_2 \ge \ldots \ge b_m$$$. The Theorem says that it's possible iff $$$\sum \limits_{i=1}^n \min(a_i, k) \ge \sum \limits_{j=1}^k b_j$$$ for $$$\forall 1 \le k \le m$$$.

Proof by induction also suggests a strategy for the construction, which turns out to be the natural greedy strategy — always selecting $$$b_i$$$ maximum positions. However, the proof by induction requires us to do the operations in decreasing order. While it doesn't follow from this proof, it's actually not needed to sort $$$b$$$ to run the greedy. In other words, the order of operations doesn't matter, if we always pick only the maximum positions.

Tasks for practice

Problem from AtCoder ABC

Problem from JOISC 2023

1740F - Conditional Mix

An important special case, all $$$b_i = t$$$. That is, in each of $$$m$$$ operations times $$$t$$$ positions are decreased. Then it is only needed to check that $$$\sum \limits_{i=1}^n \min(t, a_i) \ge mt$$$

Another example is 1774B - Coloring. Here's the short statement: we have $$$n$$$ cells and $$$m$$$ colors, each cell must be colored. For each color there must be exactly $$$a_i$$$ cells painted with that color ($$$\sum a = n$$$). Also, every window of given size $$$k$$$ cannot have cells of one color.

Here is a problem where you can try applying the idea yourself 1893D - Colorful Constructive

Dual

There is also a dual version of this problem. Suppose on each operation we decrease at most $$$b_i$$$ elements by $$$1$$$, but the goal now is to get all $$$a_i = 0$$$. Just swap $$$a$$$ and $$$b$$$ and we'll get the same problem as before! Originally all $$$b_j$$$ required $$$b_j$$$ positions in $$$a$$$ and each position $$$a_i$$$ could've been picked at most $$$a_i$$$ times. And here each $$$a_i$$$ must be picked exactly $$$a_i$$$ times (we need to pick exactly $$$a_i$$$ positions in $$$b$$$) and each $$$b_j$$$ can be picked at most $$$b_j$$$ times.

Sometimes all of the operations are the same. Usually in this case we want to find the minimum number of operations $$$m$$$ which we need to make all $$$a_i = 0$$$. Suppose all operations decrease at most $$$t$$$ positions. How do we find the $$$m$$$?

Right now I can only remember this problem 2181G - Greta's Game, which uses this fact, but this idea appears sometimes, usually where $$$t = 2$$$.

Also an application of this idea in Meta Hacker Cup, problem B

Lastly, there is problem D2 from Open Olympiad 24-25 day 2 XIX Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules), which motivated me to understand this theorem. The fact below is crucial for the solution, so it's under a spoiler as well.

Hi everyone!

This is a pretty basic blog about dp on trees, nothing advanced. Like always, I write blogs about something which I found both not obvious while solving the problem and it's a general idea which can be used in other problems.

The problem is as follows:

A weighted tree on $$$n$$$ vertices is given, as well as $$$n$$$ values $$$d_v$$$. The task is to run Dijkstra algorithm with these initial values. Usual setup for Dijkstra is $$$d_v = \infty$$$ and $$$d_{root} = 0$$$, but here all vertices have a start value. We need to do that in $$$O(n)$$$.

Solution: Root the tree arbitrarily. All pathes in a tree look like first going up and then going down. We'll do two dfs-es, the first will relax values from children to vertex, the second will relax values from vertex to children. This way every shortest path is accounted.

using ll = long long;
using pii = pair<int, int>;

vector<pii> g[N];
ll dist[N];

void dfsUp(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dfsUp(u, v);
            dist[v] = min(dist[v], dist[u] + w);
        }
}

void dfsDown(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dist[u] = min(dist[u], dist[v] + w);
            dfsDown(u, v);
        }
}

If we need to run a single Dijksta, $$$O(n \log n)$$$ gets TLE rarely, where $$$O(n)$$$ works. But if we need to run many Djikstras, for example, in binary search or in centroid decomposition, this will give a big speed up.

The problem where this optimisation is used is below, though it's not the hardest part of the problem.

1859F - Teleportation in Byteland

Since we're about to have communication problems on CF rounds, it would be really great if a new tag could be added for them. This way we can separate communication problems from usual interactves, and communication+interactive from the usual communication problems.

Hi everyone!

I need some help with the problem 2147G - Modular Tetration. In the editorial there is this identity

$$$\sum_{x|\varphi(m), rad(x) | k} cnt(x) = \sum_{d_1| q_1^{\beta_1}, \ldots , d_t | q_t^{\beta_t}} \prod \varphi(d_i)$$$

Where $$$k$$$ is a square-free number with $$$gcd(k, m) = 1$$$ and $$$k | \varphi(m)$$$. $$$cnt(x)$$$ is the number of remainders $$$1 \le a \lt m$$$ for which $$$ord_m(a) = x$$$. $$$k = q_1 q_2 \ldots q_t$$$ and $$$\beta_i$$$ is the exponent of $$$q_i$$$ in $$$\varphi(m)$$$

It is some counting in 2 ways, as far as I understand. I tried to prove this for several days, now I am desperate to know the proof since the editorial mentions this as something obvious and the author of the problem doens't respond.

Hi everyone!

This blog is totally not about asking to debug my code

On some recent div 1 rounds there were problems (this 2147F - Exchange Queries and that 2150C - Limited Edition Shop) which had one extra permutation in the input array. There were two given, but one of the permutations could be transformed to identidy. However, in order to do that, I need to permute other arrays accordingly. And that caused me a lot more trouble than I wish it did.

Usually I do something like this

void permute(vector<int> &a, const vector<int> &p) {
    int n = a.size();
    vector<int> tmp(n);
    for (int i = 0; i < n; i++)
        tmp[p[i]] = a[i];
    a = tmp;
}

but then a question arises "Why $$$tmp_{p_i} = a_i$$$ and not $$$tmp_i = a_{p_i}$$$?". And when do I use which variant?

In problem 2150C - Limited Edition Shop I also need to remake $$$b$$$ with a different rule, I can't simply call permute(v, a) and permute(b, a). I can kinda see why it's not working, but I don't see why it shouldn't work. If somebody knows some way to understand how to permute the array depending on the situation, please explain it in the comments.

P.S.: calling permute(p, p) is a bit funny because I give a const and a regular reference at the same time

Hello everyone!

As a person who had two horrible contest, I found a common trend in both rounds. It was due to lack of good samples me believing something that felt obvious but in reality is just wrong. And I wonder, how can I avoid these mistakes in the future.

Some obvious answer, that I usually try do to on the contest, if I struggle, is stress-testing. It's a really useful tool which can really help with either finding small wrong test cases or checking some assumptions about the problem. But sometimes you can't just stress test, because I am not able to bruteforce all matrices or some other object with just absurd number of combinations. So there aren't always dumb solutions which are easy to code and somewhat efficient.

If so, then how often do you usually overcheck the assumptions that you do? I can't write down every step of my solution, as it takes too much time and after a while I'm just left confused on the mess that I've written (even though I use a tablet and technically have infinite board), but I also can't trust in every idea which comes to me (even if it feels obvious, sometimes)

May you share some ideas? Thanks in advance

Всем привет!

На контестах периодически попадаются задачи на запросы на отрезках. Большая часть задач даёт запросы в оффлайне, что даёт большую свободу действий, но всё же часто они сводятся к дереву отрезков, а иногда и алгоритму Мо. Однако иногда в задачах может оказаться так, что оффлайн её решает простой Мо, а в онлайне она становится интересной. В таких ситуациях некоторые люди пытаются поддерживать что-то типа $$$500$$$ разных состояний алгоритма Мо, я вообще не понимал, что имеется в виду.

Сегодня же я сумел придумать версию онлайн Мо, работающую за $$$O(n^{\frac{5}{3}})$$$ времени и памяти в нормальных задачах (в которых движение границ делается за $$$O(1)$$$). Для анализа асимптотики я буду считать, что $$$n = q$$$. Я не первый, кто такую идею придумал. Как оказалось, здесь и здесь было обсуждение, где такая идея была предложена, но я хочу сам о ней рассказать, потому что я о ней раньше не знал.

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

2043G - Problem with Queries

Тут слишком много всего наворочено — запросы изменения, да ещё и закодированы. Попробуем сначала решить версию оффлайн и без запросов обновления. Стоит оговориться, что я буду считать не количество индексов $$$i \lt j$$$ таких, что $$$a_i \neq a_j$$$, а наоборот, что $$$a_i = a_j$$$. Из этой величины легко получить ответ на исходную задачу, однако количество пар индексов с равными значениями поддерживать несколько проще.

Сама задача — несложное упражнение на алгоритм Мо.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 10;
const int B = 320; // roughly sqrt N
int a[N];
int cnt[N];
ll sum = 0;

void add(int v) {
    sum += cnt[v];
    cnt[v]++;
}

void del(int v) {
    cnt[v]--;
    sum -= cnt[v];
}

int L = 0, R = -1; // the pointers

void move(int l, int r) { // move pointers to the query point
    while (R < r) {
        ++R;
        add(a[R]);
    }
    while (R > r) {
        del(a[R]);
        R--;
    }
    while (L > l) {
        L--;
        add(a[L]);
    }
    while (L < l) {
        del(a[L]);
        L++;
    }
}

struct query {
    int l, r, i;
};

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    int queries;
    cin >> queries;
    vector<query> q(queries);
    vector<ll> ans(queries);
    for (int i = 0; i < queries; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        q[i] = {l, r, i};
    }
    sort(all(q), [&](const query &a, const query &b) {
        int al = a.l / B;
        int bl = b.l / B;
        if (al != bl)
            return al < bl;
        return a.r < b.r;
    });
    for (auto &[l, r, i] : q) {
        move(l, r);
        ans[i] = sum;
    }
    for (int i = 0; i < queries; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

Я хочу взглянуть на анализ асимптотики с геометрической стороны. Размер блока для алгоритма Мо обозначим за $$$B \approx \sqrt{n}$$$. Вкратце, мы делим плоскость на квадратики со стороной $$$B$$$ и обходим квадратики в правильном порядке.

Теперь добавим ограничение в виде онлайн запросов. К сожалению в этой версии мы не можем выбирать порядок обхода квадратиков, да и в каждый квадратик нам может понадобиться заходить несколько раз, поэтому нужен другой подход. Понятно, что лишь одной парой указателей нам не обойтись, поскольку в таком случае на каждый запрос мы будем отвечать за $$$O(n)$$$, что долго. Назовём состоянием всю необходимую информацию, которую мы обычно поддерживаем для одного отрезка. В данном случае это массив количеств $$$cnt$$$, количество пар равных индексов $$$sum$$$ и указатели $$$L$$$ и $$$R$$$. Я хочу создать несколько состояний, чтобы от какого-то из них можно было быстро дойти до нашего запроса.

Выберем $$$B \approx n^{\frac{2}{3}}$$$. Теперь у нас мало квадратиков, всего $$$\frac{n^2}{B^2} = n^{\frac{2}{3}}$$$. Я хочу сделать так, чтобы в каждом квадратике было состояние, чтобы от него было недалеко идти до очередного запроса. Действительно, внутри квадратика расстояние между точками не превосходит $$$2B$$$, а это уже приемлемое время работы для запроса. Алгоритм можно описать так:

Определим квадратик, в котором находится запрос.

• Если в нём ранее не было запросов, то можно за $$$O(n)$$$ инициализировать этот блок. Создадим состояние, например, в точке самого запроса.
• Иначе у нас есть состояние на расстоянии не более $$$2B$$$, поэтому мы можем за $$$O(B)$$$ ответить на запрос.

Так как блоков мало, суммарно все инициализации отработают за $$$O(n^{\frac{5}{3}})$$$, а суммарное количество движений указателей не превосходит $$$O(qB) = O(nB) = O(n^{\frac{5}{3}})$$$.

Отлично, мы научились делать Мо в онлайне быстрее чем за $$$O(nq)$$$. А можно ли прикрутить запросы изменения? И если да, то надо ли нам чем-либо жертвовать? Оказывается, ответы на эти вопросы — да и нет! Обычно при запросах изменения используется 3D Мо, который вводит время в качестве третьего измерения, и обходится уже не плоскость, а трёхмерное пространство. Тогда чтобы двигать третий параметр $$$T$$$, нужно проверить, лежит ли изменяемая позиция в текущем состоянии, и если да, то сделать del и add. Но нам ведь ничего не мешает сделать то же самое, просто для всех блоков. Поскольку их, опять же, мало, $$$O(n^{\frac{2}{3}})$$$, время работы никак не ухудшается.

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

Моё решение: 329249141

Это просто феноменально, имхо, что настолько простая идея, как алгоритм Мо, может работать в онлайне, да ещё и с изменениями!

P. S.: Правда, как оказалось, это некоторая интерпретация разбора задачи, а не другое решение. Разбиение на квадратики — то же самое, что и разбиение на блоки. Инициализация состояния в каждом квадратике эквивалентна предпосчёту ответа для каждой пары блоков, а движение указателей — добавление элементов с краёв неполных блоков.

Недавно я встретил задачу 2046D - За императора!, которая напомнила мне про существование L-R потоков. Я их узнал очень давно, да и в тот момент задачи помимо "просто напиши L-R поток" нам не дали, так что я не запомнил алгоритм и мне пришлось узнать его заново, уже более детально. К сожалению блога на кфе, который бы всё понятно объяснил, не было, так что пришлось лазить по всяким другим ресурсам. Я нашёл их тут, примерно понял идею, потом пришлось смотреть реализацию, у меня к ней остались вопросы, я воспринимал немного как чёрный ящик. Но сегодня в 3 часа ночи мне пришло озарение и я всё понял. Чтобы тем 5 людям, которые прочитают мой блог, не пришлось его ждать, я хочу тут разъяснить моё понимание этого алгоритма и как его удобно писать.

The div 1 today was cancelled, which made me really frustrated, I was really trying to prepare for the round in order to get satisfiable performance, but now I've got to wait a whole other month, and who knows what will happen then. Because of that I'd like to make some suggestions in order to reduce the frustration from lack of div 1 rounds and precedents like today's one.

Idea 1: Currently I see very few people, that aren't GMs, who can AK a div 2 round, so why can't the unrated barrier for div 2 be increased? I think that masters (and maybe IMs too) can participate in a div 2 and it usually doesn't just become speedforces to solve all problems for them.

Idea 2: I think that today's div 1 was cancelled only because the last problem coincided. Which is really a shame since most of the participants wouldn't even get to that problem. I'm not saying that we shouldn't care about LGMs, but maybe a new type of rounds, that has only one of the two problems for div 1 can be made. They would be more often, since usually preparing a 3500 task takes the biggest effort and the most time.

Personally, I like idea 2 more, as it's more of a compromise between idea 1 and current state of rounds. Some of the last problems from div 2 can really be on further positions that they are now, since modern div2F are usually made only for GMs.

All in all, I hope that something will be done, waiting 1 month for a div 1 just to find out that the last problem was on some contest is really frustating.

Вчера закончился длинный тур Открытой олимпиады 2024-25, мне оттуда очень понравилась задача F (инопланетные омофоны). Возможно, некоторые скажут, что там очевидное решение (про которое я тоже напишу), но я таких идей раньше не встречал и не думал в ту сторону. Зато я придумал другое решение, более техничное, но тоже интересное.

Само условие можно найти тут.

Общие идеи для решения:

Чтение очередного слога я буду называть прыжком по строке. Прыжок зависит от текущий позиции (его старт) и от правой границы, до которой мы прыгаем. Слово, которое мы получаем, по факту является массивом из типов звуков. Сравнение двух слов — это сравнение этих двух массивов на равенство. Делать это не хешами звучит очень сложно, поэтому для сравнения подотрезков нам нужно будет посчитать их хеши. Также, для определения, какой именно звук мы произнесём при прочтении слога, мы по факту должны выделить компоненты связности, слоги из одной компоненты звучат одинаково, а из разных — по-разному. Ну и наконец, для определения прыжка очень полезен будет алгоритм Ахо-Корасик, без него никуда не деться. Так как при прыжке у нас фиксирован старт, а конец не фиксирован, строки из набора следует развернуть, а затем проходиться по строке справа-налево (обычный Ахо-Корасик умеет находить слова, которые заканчиваются в какой-то позиции, а если мы разверём слова и направление прохода, то получим слова, которые начинаются в какой-то позиции).

Теперь же перейдём к решениям задачи. Нормальное решение, которое сдало большинство, звучит так:

Мы умеем для позиции искать самое длинное слово, которое начинается в ней. Почему мы не можем всегда делать просто максимальные прыжки? В какой-то момент максимальный прыжок будет пересекать правую границу отрезка. Но до этого момента мы прыгать спокойно можем. А в момент пересечения возникает очень хитрое замечание: оставшийся отрезок строки, который надо пропрыгать — это префикс какой-то строки из набора. Так как суммарная длина строк в наборе $$$S \le 10^6 + 26$$$, мы можем просто решить задачу для каждого префикса каждой строки, тогда мы победим. Информация, которая нам будет нужна — это хеш и количество прыжков, которые мы сделаем (нужны оба параметра для того, чтобы хеши прыжков с двух частей можно было объединить).

А чтобы решить задачу для префикса каждой строки, сделаем так: будем считать ответ в порядке возрастания длин строк в наборе. Тогда применима такая же идея — сначала мы прыгаем, сколько можем, а последний прыжок может оказаться префиксом какой-то строки, но мы её уже были обязаны рассмотреть. Таким образом, за $$$O(S)$$$ мы решили задачу для всех префиксов.

Чтобы быстро понимать в строке $$$t$$$, до куда мы допрыгаем по максимальным прыжкам, можно насчитать бинарные подъёмы. Итого получается $$$O(n \ log \ n)$$$ на эту часть. Общая сложность решения $$$O(n \ log \ n + S)$$$ (алфавит считаем константной). С этой информацией хеш считается за $$$O(1)$$$, так что на запросы мы ответим просто за $$$O(q)$$$.

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

Второе решение:

Решать будем оффлайн, у нас будет $$$2q$$$ запросов вида "посчитать хеш на интервале $$$[l, r)$$$" (для удобства будем считать, что мы должны прийти не в позицию $$$r$$$, которая нам даётся, а в $$$r + 1$$$, потому что после последнего прыжка мы как бы оттуда должны читать следующий слог).

Задачи, в которых есть какие-то прыжки по массиву, иногда позволяет решать техника Разделяй-и-Властвуй по запросам. Попробуем её тут увидеть.

Пусть у нас есть функция $$$solve(l, r, q)$$$, которая решает все запросы с $$$l \le q.l$$$ и $$$q.r \lt r$$$. Введём середину $$$m = \lfloor \frac{l + r}{2} \rfloor$$$. Поделим запросы на $$$3$$$ типа:

1. $$$q.r \lt m$$$
2. $$$q.l \ge m$$$
3. Остальные

Первый тип запросов решается так: $$$solve(l, m, q1)$$$. Второй, аналогично, $$$solve(m, r, q2)$$$. Однако перед этим запуском хочется разобраться с запросами третьего типа. Я хочу свести третий тип ко второму, тогда запуск от правой половины решит как 2 так и 3 тип запросов.

Третий тип запросов имеет хорошее свойство — есть прыжок через разрез $$$(m - 1, m)$$$. То есть найдётся такой прыжок, что его старт в левой половине, а старт следующего уже в правой. Если мы научимся делать все прыжки до этого включительно, то мы умеем получать запрос типа 2. Заметим, что все прыжки из левой части в левую никак не зависят от того, какая у запроса правая граница, они и так не могут прыгнуть во вторую половину. Это чем-то напоминает дерево (вернее лес). Каждая позиция — это или корень, который ведёт вправо, или у неё есть предок. С таким деревом задача решается очень просто — храним в позиции хеш до корня и сам корень, из корня делаем прыжок вправо. Однако для прыжка через разрез правая граница запроса уже имеет значение, и, возможно, максимальная строка окажется слишком длинной.

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

Если мы будем отвечать на запросы в порядке убывания правой границы, то для каждой позиции слева минимальный прыжок сначала будет доступен, но в какой-то момент (а именно, когда правая граница будет левее, чем позиция, куда ведёт прыжок) перестанет быть возможным, и тогда позиция слева перестанет быть корнем, её надо будет подвесить к максимальному левому прыжку. Это звучит как СНМ. Оставим от него только сжатие путей. Теперь мы быстро умеем понимать, из какой позиции мы будем делать прыжок через разрез, надо просто вызвать сжатие путей от левой границы запроса. При сжатии путей нам нужно поддерживать хеш прыжков и их количество.

Осталось научиться делать максимальный прыжок вправо, длина которого ограничена правой границей запроса. Мы умеем искать максимальный прыжок с помощью Ахо-Корасика, а также у нас есть суффиксные ссылки в нём. Построим также сжатые суффиксные ссылки — это ссылки, ведущие в ближайшую терминальную вершину. Тогда, если построить бинарные подъёмы на этих ссылках, то мы можем с помощью них найти нужный прыжок. С помощью них же можно найти и минимальный прыжок вправо (это можно ещё и ускорить, сделав предварительно на сжатых ссылках ladder decomposition).

Кратко: идём в порядке убывания правой границы, подвешиваем все минимальные прыжки, которые теперь слишком длинные, все прыжки кроме последнего нам посчитает СНМ, а последний найдём бинарными подъёмами.

По итогу из запроса $$$(l, r)$$$ получаем запрос $$$(l', r)$$$, где $$$l' \ge m$$$, следовательно, его можно пустить во второй тип.

Итоговая сложность: $$$O(n \ log^2 \ n + q \ log \ n \ log \ S + S \ log \ S)$$$.

Выглядит долго, есть несколько оптимизаций, сильно ускоряющих решение. Во-первых, для поиска минимальных прыжков можно использовать ladder decomposition. Во-вторых, как известно, на пути до какой-то вершины может быть не более $$$\sqrt{2S}$$$ терминальных вершин, так что глубина бинарных подъёмов не $$$20$$$, а $$$11$$$.

И последняя. Иногда при разделяйке условие выхода ставится не $$$(l = r)$$$ (в случае полуинтервалов $$$r - l = 1$$$), а $$$r - l \le 10$$$ или $$$r - l \le 30$$$. При этом условии запросы чуть менее тривиально обрабатываются, не просто "Ответ 0" или что-то такое, а пишется наивное решение, которое работает быстрее на маленьких размерах. А как выбирать этот размер и почему вообще происходит ускорение? У классической разделяйки ровно $$$log \ n$$$ слоёв. Однако, если мы выберем некоторый размер $$$B$$$, на котором мы обрубаем рекурсию, то слоёв будет всего лишь $$$log \ (n / B)$$$, или же $$$log \ n - log \ B$$$. В данной задаче наивное решение будет работать за $$$(r - l)^2$$$, что можно оценить сверху как $$$(r - l)B$$$. Поэтому суммарно все наивные решения отработают за $$$nB$$$. Новое время работы получается уже несколько лучше:

$$$O(nB + (log \ n - log \ B) (n \ log \ n + q \ log \ S)$$$. При маленьких $$$B$$$ вторая часть работает явно дольше, чем первая. Поэтому $$$B$$$ можно увеличить. Правда не стоит увеличивать слишком сильно, всё-таки, $$$nB$$$ растёт очень быстро. Если взять $$$B \simeq log \ n$$$, то выходит время уже чуть получше:

$$$O(n \ log \ n + (log \ n - log \ log \ n) (n \ log \ n + q \ log \ S))$$$.

Улучшение несильное, но всё же не стоит такое недооценивать, особенно если умное решение имеет большую константу.

Реализация тут.

So recently I became red on CF and my happiness knows no boundaries. For achieving the red color, I would like to thank those who helped me the most.

dmikhalin, my first informatics teacher who inspired me to do competitive programming

gmusya, teacher in B parallel of the main programming club in Russia, who answered many of my questions and helped my a lot

And all the teachers of parallel A!

I'd like to tell a timeline of my progression. Three years ago when I ended 8th grade I got a giant boost of motivation after I learned segment tree and dsu from CF EDU (that's actually useful try it). In summer school I got to expert (that was so cool, I still remember how I solved problem F from div 3, back then it was difficult). Then I continued to grind CF. Before 9th class I learned that there is a strong programming club from Tinkoff, so I decided to try to get there. Easily the best decision, this club gave me a gigantic boost during these three years. I got to parallel B, which I think is the place where you learn most of important techniques.

In 9th class I also managed to get to ROI (Russian Olympiad in Informatics), craziest thing was that I was top 5 among 9-graders from Moscow on regional stage. However I couldn't get silver medal there, by 16 out of 800 points, which was sad. 2 weeks before ROI I also managed to get CM (could've happened a lot faster, but goodbye 2022 killed me).

Summer after 9th class, high motivation to get revenge and again grinding CF. I also really wanted to get Master before school and bit by bit I crawled in the 2100 zone, getting Master on 5th August 2023. After that I participated in two rounds, first one gave me positive delta, I felt worthy of Master, another one — not so good, E was bad :).

Then was a giant pause for rated rounds, I just couldn't find any time. And then I drop back to CM, solving only one problem on div 1... That felt so awful, I needed to comeback asap. Luckily there was div 2 really close, and I managed to solve all 6 problems! I guess a miracle happened or something, but I got again to Master and a really good one, the idea of getting to IM wasn't so distant anymore.

I could tell about experience from other olympiads (IZhO, Open Olympiad and most importantly ROI), but then the post would be too long (and it already kinda is). Shortly, gold in IZhO (very surprising), gold in Open Olympiad (there not so surprised) and ROI... First day had completely destroyed me, instead of getting in top-30 like it was predicted by training tours I got in top-300... I was depressed the whole day after that result, wanted to get the gold medal (and had enough skill), just got really unlucky). Second day was good, I performed like I should've in both days, so I managed to get at least a silver medal, yay...

Growing when you're 2100+ is really slow, div 1's are only twice a month. I thought I would be able to get IM on round 959, when I was in Germany with my parents, but no, and the worst part was that I got totally killed by problem C! Of div 2!!! I think I spent more time on it than on all other problems combined. I felt really sad that day, like something was taken from me. The worst part was that I had only one chance left before SIS (summer camp) and then school. Pinely Round 4 was really strange for me, I solved D in 3 minutes, and problem A-F felt like there was an extra one (probably D). Having 6 problems solved in like an hour, I thought that it's over and no IM, as G is super hard, but decided to give it a try. By some higher powers I managed to solve it 5 minutes before the contest ended (I still don't understand how that happened), but stunning +131 delta and I went to SIS all happy with a new title.

After that getting GM was more of a measure of time, but still an impressive achievement for me. I'm happy that it happened before my 18-th birthday (which is like in two weeks btw!)

So that's my story and my "yay gm" blog (sorry for cringe, I am on cloud nine today).

P. S.: AMA! I'll try to reply fast :)

Спасибо K1o0n за то, что он был mvp при подготовке раунда.

1992A - Одни плюсы

Идея: Vladosiya

Подготовка: K1o0n

for _ in range(int(input())):
    arr = sorted(list(map(int,input().split())))
    for i in range(5):
        arr[0]+=1
        arr.sort()
    print(arr[0] * arr[1] * arr[2])

1992B - Злой Monk

Идея: Noobish_Monk

Подготовка: K1o0n

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T;
    cin >> T;
    while (T--){
        int n, k;
        cin >> n >> k;
        vector<int> s(k);
        int m = -1;
        for (int i = 0; i < k; i++){
            cin >> s[i];
            m = max(m, s[i]);
        }
        cout << 2 * (n - m) - k + 1 << '\n';
    }
}

for _ in range(int(input())):
    n,k = map(int,input().split())
    mx = max(map(int, input().split()))
    print((n - mx) * 2 - (k - 1))

1992C - Горилла и перестановка

Идея: K1o0n

Подготовка: K1o0n

for _ in range(int(input()):
    n,m,k = map(int,input().split())
    print(*range(n,m,-1), *range(1,m+1))

1992D - Испытание любви

Идея: ArSarapkin

Подготовка: K1o0n

def run() -> None:
    n,m,k = map(int, input().split())
    A = input()
    logs = [i for i in range(n) if A[i] == "L"]
    logs.append(n+1)
    i = -1
    next_log = 0
    while i < n-1:
        if m >= logs[next_log] - i:
            i = logs[next_log]
        else:
            i+=m
            if i > n-1:
                print("YES")
                return
            while i < n and i < logs[next_log]:
                if A[i] != "C" and k > 0:
                    i+=1
                    k-=1
                else:
                    print("NO")
                    return
        next_log +=1
    print("YES")
 
for _ in range(int(input())):
    run()

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k; 
        cin >> n >> m >> k;
        string s;
        cin >> s;
        vector<int> dp(n + 2, -1);
        dp[0] = k;
        for (int i = 1; i <= n + 1; i++) {
            if (i != n + 1 && s[i - 1] == 'C') 
                continue;
            for (int t = 1; t <= m; t++)
                if (i - t >= 0 && (i - t == 0 || s[i - t - 1] == 'L'))
                    dp[i] = max(dp[i], dp[i - t]);
            if (i > 1 && s[i - 2] == 'W') 
                dp[i] = max(dp[i], dp[i - 1] - 1);
        }
        if (dp[n + 1] >= 0) 
            cout << "YES\n";
        else 
            cout << "NO\n";
    }
}

1992E - Ошибка новичка

Идея: Noobish_Monk, K1o0n

Подготовка: K1o0n

for _ in range(int(input())):
    n = int(input())
    sn = str(n)
    lenN = len(str(n))
    ans = []
    for a in range(1, 10001):
        minB = max(1, lenN * a - 5)
        maxB = lenN * a
        for b in range(minB, maxB):
            x = n * a - b
            y = 0
            for i in range(lenN * a - b):
                y = y * 10 + int(sn[i % lenN])
            if x == y:
                ans.append((a, b))
    print(len(ans))
    for p in ans:
        print(*p)

1992F - Ценные карточки

Идея: Noobish_Monk

Подготовка: Noobish_Monk

#include <iostream>
#include <vector>

using namespace std;

const int A = 1e6 + 1;
bool used[A];
bool divs[A];

void solve() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	vector<int> vecDivs;
	for (int d = 1; d * d <= x; d++) {
		if (x % d == 0) {
			divs[d] = true;
			vecDivs.push_back(d);
			if (d * d < x) {
			    vecDivs.push_back(x / d);
				divs[x / d] = true;
			}
		}
	}
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ans = 1;
	used[1] = true;
	vector<int> cur{ 1 };
	for (int i = 0; i < n; i++) {
		if (!divs[a[i]])
			continue;
		vector<int> ncur;
		bool ok = true;
		for (int d : cur)
			if (1ll * d * a[i] <= x && divs[d * a[i]] && !used[d * a[i]]) {
				ncur.push_back(d * a[i]);
				used[d * a[i]] = true;
				if (d * a[i] == x)
					ok = false;
			}
		for (int d : ncur)
			cur.push_back(d);
		if (!ok) {
			ans++;
			for (int d : cur)
				used[d] = false;
			used[1] = true;
			used[a[i]] = true;
			cur = vector<int>{ 1, a[i] };
		}
	}
	for (int d : vecDivs) {
	    divs[d] = false;
	    used[d] = false;
	}
	cout << ans << '\n';
}

signed main() {
    int T;
    cin >> T;
    while (T--)
	    solve();
	return 0;
}

1992G - Ультра-мяу

Идея: Noobish_Monk, K1o0n

Подготовка: K1o0n

#include <iostream>

using namespace std;

const int mod = 1e9 + 7;

int add(int a, int b) {
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

int sub(int a, int b) {
    if (a < b)
        return a + mod - b;
    return a - b;
}

int mul(int a, int b) {
    return (int)((1ll * a * b) % mod);
}

int binpow(int a, int pw) {
    int b = 1;
    while (pw) {
        if (pw & 1)
            b = mul(b, a);
        a = mul(a, a);
        pw >>= 1;
    }
    return b;
}

int inv(int a) {
    return binpow(a, mod - 2);
}

const int N = 15000;
int f[N], r[N];

void precalc() {
    f[0] = 1;
    for (int i = 1; i < N; i++)
        f[i] = mul(f[i - 1], i);
    r[N - 1] = inv(f[N - 1]);
    for (int i = N - 2; i > -1; i--)
        r[i] = mul(r[i + 1], i + 1);
}

int C(int n, int k) {
    if (n < 0 || k < 0 || n < k)
        return 0;
    return mul(f[n], mul(r[k], r[n - k]));
}

inline void solve() {
    int n;
    cin >> n;
    int ans = 1;
    for (int k = 1; k <= n; k++) {
        if (2 * k >= n) {
            ans = add(ans, mul(2 * k + 1, C(n, k)));
            continue;
        }
        for (int m = k + 1; m <= 2 * k + 1; m++) {
            int c = mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m));
            ans = add(ans, mul(mul(C(m - 1, m - 1 - k), C(n - m, 2 * k + 1 - m)), m));
        }
    }
    cout << ans << '\n';
}

signed main() {
    int T = 1;
    cin >> T;
    precalc();
    while(T--)
        solve();
    return 0;
}

I came up on a problem and got it to solving this one, but now I am stuck. Can someone help please?

How can we efficiently count the number of regular bracket sequences with length $$$2n$$$ that have first closing bracket on position $$$k + 1$$$ (any way faster than $$$O(nk)$$$ or $$$O(n^2))$$$?

If there will be 3 or 4 rounds before rating update on problems, we'll have full empty page. Is it like a challenge that codeforces is trying?

Hello. I've been trying to understand min cost max flow algorithm for several days and now I realised I don't understand why Jonhson's potentials work. We use them so that all edges have nonnegative weights. As I remember, Jonhson's algorithm works only if there aren't any cycles with negative weight. But isn't it the criteria for optimal MCMF, that there are no negative cycles in the residual network? So, until we actually find the optimal flow, we can't use potentials as there are negative cycles. Why can we use potentials then?

Hello. I've heard there is a way to store trees using like 3 integer arrays. How exactly is it done? And can it be extended on any graph?

After rounds problems appear in the problemset and somehow get their difficulties after some time. How is the difficulty selected for a problem and what's the time needed for rating to be determined?