nikhil_cf's blog

By nikhil_cf, history, 4 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it