So, I was sleeping and this problem just came to me in a dream:
Given an array a and an array b, we need to split a into contiguous subsegments and for each subsegment assign 1/0 — whether we reverse it or not. The question: can we determine if it's possible to obtain b from a?
So far I only know how to solve it in O(n²), but there's clearly a better way, help pls
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
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/.