how to efficiently shift sub arrays

I have got stuck on one question from the contest “koder kombat”

I have tried to solve this question using array and linked list but both are taking too long and I am getting TLE error.
I have referred to this solution:-

https://www.codechef.com/viewsolution/8623244

they are accomplishing this using some tree data structure, I banged my head a lot but couldn’t figure out what’s under the hood.

Please help me out with this.

Thank you

Arrays/vectors and swap should be fast on modern GHz range processors with large caches, so if you are doing it right(single array, no reallocations and just using swap and do so sequentialy to benefit from the cache), you could fit the time for most cases with your (I assume) O(N*Q) approach, but probably not for the worst case of N=Q=10^5.

Optimizing your stdin/cin input could perhaps help you beat that limit too if you feel you are close (I tested on INTEST and naive/natural cin input is as much as 50x slower than optimized version). Feel free to use my IIStream<> if on C++14 (with proper attribution as local rules demand).

Maybe stating the obvious: With naive implementation you run into the problem,that array have O(N) insertion/range swap in middle and linked lists O(N) indexed element access. You must find some way around, if the above doesn’t work.

If I read it correctly, it is basicaly taking some subarray and placing it at end or beginning. It feels, there should be some trivial solution.
I have not done it yet, but I would probably try to build a tree on top of the A[N] array. (That is root would represent whole array. left child = some left subarray and, right child = some right range of the subarray of parent and so on for the grandchilds). And then at the end the leaves should be the array in correct (shifted) order. Building the tree based on the shifts should be mostly O(Q*log(N)) - I won’t spoil for now how precisely to do that. Printing the levaves to output O(N+Q).

Maybe show us what you got yourself. That would help us to point you to inefficiencies in your code. Also there are plenty of problems - take one you can solve and return to this one with fresh mind.

I have tried to decode the nicely obfuscated C++ sample you linked. I gave up, but I am confident it is some sort of implementation of a Treap. There seem to be some submitted/accepted solutions of that that are somewhat more readable.

1 Like

The solution uses a data structure called Treap. Treap is probabilistic binary search tree. It provides two general functions split and merge using that we can break and join the tree

For the arrays, we use Implicit Treap which uses index of elements as key for search purpose

This structure do the splitting and merging operation in O(log(n)) where n is the number of elements in the tree

For more info on Treap, Read this awesome article by Tanuj Khattar Part 1 Part 2

1 Like

@kr0oze
I have done this using an extra array, and for next query using the extra array as main array.
Did you try to figure out, what approach the guy with this solution https://www.codechef.com/viewsolution/8623244

is using.

updated answer with that information

@pulkitsinghal
How merge operation is working in the code I mentioned.