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
