Hey all,
Recently I came across a problem. It goes as follows:
You are given an integer array v of size n. Q queries are to be executed on v. Each query is of form a, b, c, 1 < a < b < c < N-1. For each query, you are supposed to swap the sub-arrays v[0:a-1] and v[a:b] with each other and the sub-arrays v[b+1:c] and v[c+1:n-1] with each other. Now, print the resulting array after executing the given queries in the given order.
Constraints:
3 < n < 1e5 + 1 and 0 < q < 1e5 + 1 and 0 < v[i] < 1e9 + 1.
One simple solution I was able to come up with is to maintain a linked-list based structure of the array and execute each query in O(n) time. But this doesn't fit in the required time complexity limits.
I think you're linked list approach could execute each query in o(1).After executing all queries you just need to find the starting node, that will be the node which has no other node pointing to it. So o(N) at the end to find the starting node and print everything in order.
Not sure if this will work, but you can try->https://codeforces.net/blog/entry/10355. Can you give some link where a solution to this problem can be submitted? That will be helpful. I have never used this technique before, it seems to be applicable only in certain very specific problems.
No I don't have any such link, found this question in a hiring challenge.
Cutting pieces of arrays and re-ordering them is a really popular application of Implicit Treaps. This question uses this idea, you can have a look it's video editorial by SecondThread once you know treaps