Значит я спал себе спокойно и вдруг эта задача мне приснилась:
Дан массив a и массив b, надо разбить a на подотрезки и для каждого подотрезка поставить 1/0 — разворачиваем мы его или нет. Вопрос: надо определить можем ли мы из a получить b?
Я пока умею решать только за O(n^2), но явно же можно лучше, помогите плиз
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Автокомментарий: текст был переведен пользователем GomerDoGo (оригинальная версия, переведенная версия, сравнить).
Автокомментарий: текст был обновлен пользователем GomerDoGo (предыдущая версия, новая версия, сравнить).
Что насчёт O(n log n)?
Что насчёт O(n log n)? Строим последовательность s длины 2n: s = a0,b0,a1,b1,... и ведём булево dp по границам между элементами a (граница i — это позиция 2i в s), где dp(i)=true означает, что префикс a длины i уже можно преобразовать в префикс b длины i. Любой блок разбиения a на отрезке [l, r) даёт переход dp(l) -> dp(r): если блок не переворачиваем, то требуется a[k]=b[k] для всех k из [l, r), и такие переходы делаются за O(n) протягиванием по подряд идущим равенствам a[k]==b[k] (держим самую дальнюю достижимую границу). Если блок переворачиваем, то условие b[l..r)=reverse(a[l..r)) эквивалентно тому, что подотрезок s на позиции [2l, 2*r) является палиндромом; поэтому переворотные переходы сводятся к палиндромам в s и добавляются через палиндромное дерево, а чтобы не перебирать все палиндромные суффиксы, используем стандартную оптимизацию diff/series_link и учитываем только палиндромы, начинающиеся и заканчивающиеся на чётных позициях (то есть попадающие в границы). Асимптотика: прочитать вход быстрее, чем за O(n), нельзя; часть без переворотов — O(n), палиндромное дерево строится за O(n), но DP через series_link в худшем случае даёт O(n log n) (так как на каждой позиции O(log n) серий), поэтому итог O(n log n) по времени и O(n) по памяти.
Мог бы ты объяснить почему нам хватает перебрать только log паллиндромов для позиции i? (если это очев и буквально объясняется series link, то можно сслыку плиз)
Да, мне тут, или в личных сообщениях?
В eertree у каждого палиндрома v есть link(v) — следующий меньший суффикс‑палиндром. Вводят diff(v)=len(v)-len(link(v)). Если идти по link, то часто получаются длинные участки, где diff одинаковый; тогда длины палиндромов на этом участке отличаются на константу (это одна серия). series_link(v) (slink) сжимает такие участки: он переводит v в максимальный суффикс‑палиндром u, для которого diff(u) != diff(v), то есть к началу следующей серии. Поэтому в DP на фиксированной позиции достаточно обновиться по одному разу на серию, а не по каждому палиндрому.
Ключевая лемма значится: длина цепочки v, slink(v), slink(slink(v)), .. (serial path) ограничена O(log n), поэтому серий на каждой позиции O(log n), и итоговая сложность DP получается O(n log n). См. введение diff/slink и утверждение про ограничение serial path (Approval 1) в разборе: https://mirror.codeforces.com/blog/entry/19193
Блин, очень крутая штука, мне понравилась. Конечно сомневаюсь, что на ROI прегодится), но все равно спасибо
Согласен, пожалуйста. Удачи на ROI!
За количество делителей, умноженное на размер массива? Это меньше, чем квадрат
Делителей не больше, чем корень
Длины блоков необязательно одинаковые, а твой код предполагает обратное.
hi , so i dreamt about the solution today in a nap ...
there was a fat horse who kept saying use 2 pointers+dp
that horse's name? your mother
О, я не увидел, что отрезки не должны быть равными. А какое есть решение за квадрат?
dp[i] = 0/1 можно ли выполнить эту задачу для префикса длины i.
dp[i] |= dp[j-1] & (a[j..i] == b[j..i] | rev(a[j...i]) == b[j...i]) по всем j < i.
Если на русском — говорим, что правая граница нашего отрезка сейчас в i, а левая в j, проверяем может ли так быть, перебирая все j<i. Вот и для проверки равенства строк будем использовать хеши, так что ассимптотика -> O(n^2)
This is a very interesting problem!
I believe a solution can be found with DP[i] = whether solution exists up to position i, while only transitioning the shortest possible reversed interval and the shortest possible non-reversed interval from each position
If the next interval in any existing solution is not reversed and has length m, it can be partitioned into m intervals of length 1 each, so we will find it by repeatedly taking the shortest possible non-reversed interval
If the next interval in any existing solution is reversed, it gets more complicated. Suppose the shortest reversed interval we can take is [i, r1] and an existing solution has the next interval as [i, r2]. We can show that:
The shortest possible reversed interval from each position can be found in n*log(n) time by finding the largest possible interval from each possible center point with hashing + binary search, then applying sweepline
This is beautiful! Thank you a lot
And if you are interested, in the Russian version of this post a guy proposed another solution:
We construct a sequence s of length 2n: s = a0, b0, a1, b1, … and maintain a boolean DP on the boundaries between the a‑elements (boundary i is position 2i in s), where dp(i) = true means that the prefix of a of length i can already be transformed into the prefix of b of length i. Any block of a partition over the interval [l, r) gives a transition dp(l) → dp(r): if the block is not reversed, we require a[k] = b[k] for all k in [l, r); such transitions are performed in O(n) by scanning consecutive equalities a[k] == b[k] (keeping the farthest reachable boundary). If the block is reversed, the condition b[l..r) = reverse(a[l..r)) is equivalent to the substring of s from position 2l to 2r‑1 being a palindrome; therefore, reversed transitions reduce to palindromes in s and are added via a palindrome tree. To avoid enumerating all palindromic suffixes, we use the standard diff/series_link optimization and consider only palindromes that start and end at even positions (i.e., those that hit the boundaries). Complexity: reading the input cannot be faster than O(n); the non‑reversed part is O(n), the palindrome tree is built in O(n), but the DP using series_link yields O(n log n) in the worst case (because each position contributes O(log n) series), so the overall time is O(n log n) and memory O(n).
Probably related to this leetcode problem: https://leetcode.com/problems/scramble-string/description/.