I remember a problem called "lighthouses". It was something like the following:

There are $$$n$$$ lighthouses on a circle. Given distances between each pair of lighthouses, you need to find a continuous path through them of minimal cost. No two segments of your path can intersect.

It had a $$$O(n^3)$$$ dp solution and I don't remember where I heard it. Perhaps from an ICPC contest? Do you know what problem am I talking about?

Осталось всего несколько дней до заключительного тура "Высшей пробы"! Он пройдёт 9го февраля 2024 года.

Я не нашел в Тренировках заключительные этапы прошлых лет, поэтому сам решил их добавить. Успейте принять виртуальное участие, чтобы попрактиковаться! Вот ссылки на тренировки:

Заключительный этап 2022-2023

Заключительный этап 2021-2022

Заключительный этап 2020-2021

Большое спасибо Slamur, за то, что перепроверил задачи и помог мне преодолеть skill issue. Сам бы я не смог их разместить в тренировках :D

У меня есть решение задачи G с Codeforces Round #900 (Div.3), которое работает за $$$O(n \cdot (log(A) + log(n)) + q \cdot log(A))$$$ по времени.

Я заметил, что никто не упоминал это решение, поэтому я попробую его объяснить.

Из-за того, что чтобы посчитать побитовое ИЛИ на пути нужно $$$O(log(n))$$$ операций, суммарно нам потребуется $$$O(n \cdot log(A) + q \cdot log(A) \cdot log(n))$$$ операций. Наша задача состоит в том, чтобы как-то избавиться от множителя $$$O(log(n))$$$ и научиться вычислять побитовое ИЛИ на пути за $$$O(1)$$$. Чтобы это сделать необходимо:

• Во-первых, давайте предподсчитаем для каждой вершины какие предки её поменяют. Сделаем это при помощи динамики. Какая вершина может поменять наше значение ИЛИ? Или наш непосредственный родитель, или тот, кто поменял родителя. Почему? Потому что если поднимемся один раз, то окажемся в родителе и добавим его биты себе и только те, кто поменяли родителя возможно смогут поменять и нас. Существует не более $$$O(log(A))$$$ вершин, которые могут поменять значение вершины на пути к корню.

• Во-вторых, давайте запомним запросы в вершинах. То есть для каждой вершины мы запомним список запросов, где эта вершина участвует. В этом списке будем хранить другую вершину из запроса и индекс запроса. Да, будем отвечать в оффлайне.

• В-третьих, как теперь вычисляется ИЛИ? Пусть $$$(x, y)$$$ — пара вершин из запроса, $$$l$$$ = $$$LCA(x, y)$$$, и $$$z$$$ — промежуточная вершина на пути от $$$x$$$ к $$$l$$$. Давайте предположим, что мы поднимаемся из $$$x$$$. Мы уже предпосчитали все вершины $$$z$$$ для данного $$$x$$$, которые могут её поменять. Так что можно легко посчитать ИЛИ на пути $$$path(x, z)$$$. $$$path(z, y)$$$ разбивается на $$$path(z, l)$$$ и $$$path(l, y)$$$. Мы можем вычислить $$$path(l, y)$$$ с помощью бинарных подъёмов. Мы так можем сделать потому что мы это делаем один раз для всех возможных вершин $$$z$$$. Но что с $$$path(z, l)$$$? Тут уже нельзя использовать бинарные подъёмы, чтобы посчитать ИЛИ.

• Давайте воспользуемся $$$\bf{идемпотентностью}$$$ функции ИЛИ. Это значит $$$ИЛИ(ИЛИ(a, b), ИЛИ(b, c)) = ИЛИ(a, b, c)$$$. Эта идея очень схожа с идеей Разреженной таблицы. Мы уже до этого считали что-то вроде $$$sum$$$_$$$or[i][j]$$$ $$$=$$$ побитовое ИЛИ на пути к корню из $$$i$$$ длиной length $$$2^j$$$. Так, ИЛИ на пути $$$path(z, l)$$$ разбивается на $$$sum$$$_$$$or[z][p]$$$ | $$$sum$$$_$$$or[w][p]$$$ для какой-то вершины $$$w$$$ и показателя степень двойки $$$p$$$ таких, что $$$2^p \le dist(w, l) < 2^{(p+1)}$$$.

• Но как же узнать вершину $$$w$$$? Для этого мы и запоминали все запросы. Теперь нам нужно поддерживать путь от корня до $$$x$$$ чтобы быстро находить вершину $$$w$$$. Теперь мы можем вычислить побитовое ИЛИ на пути dfs'а за $$$O(1)$$$ кодом вроде этого:

    auto or_last = [&](int cur, int len) {
      if (len == 0) {
        return arr[cur];
      }
      int p = __lg(len);
      int diff = len - (1 << p);
      return sor[p][cur] | sor[p][tour[inds[cur] - diff]];
    };

Смотрите это решение и авторское.

В результате нашей работы, это решение имеет сложность по времени $$$O((n + q) \cdot (log(A) + log(n)))$$$