Editorial : Coyote and SuperVyas

Problem Link : https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/coyote-and-supervyas

Explanation :

Let’s start from a slow solution first.

Coming to think about it, you are asked to place X1 in 2nd free cell of your answer, then to place X2 in 3rd free cell of your answer while starting counting from position where you had placed X1 (and starting from the beginning if you reached end of array), then to place X3 in 4th free cell, and so on. It is quite easy to understand why it works – rotating deck around your pointer and rotating pointer around deck in opposite direction is basically same thing.

Now add one more optimization. At every moment you know how many free cells are in your array now. Assume you are at position X now, need to move 20 free cells forward, and you know that at given moment there are 2 free cells before X and 4 free cells after X. It means that you need to find 22nd free cell starting from beginning of array, which is same as going full circle 3 times and then taking 4th free cell. As you can see, we moved to a problem “find i-th zero in array”.

Naive solution is still O(N^2), but it is fast enough to pass and still have a very easy implementation!

However, you can speed it up.

Problem “find k-th 0 in array” is well-known. N*log(N) solution with segment tree: for every vertex store number of 0’s in given range. Start from root and move down to a leaf; at every vertex you know where you should go by looking at number of 0’s in left and right subtree. Suppose you need 5th 0 in range, and there are 8 of them in left subtree and 7 of them in right subtree. It is obvious that you need to move into left subtree and look for 5th 0 there. And what if you need 12th 0? In such case you have to move into the right subtree – but don’t forget that you’ll be interested in 4th 0 there, not in 12th (because of 8 more 0’s in left subtree).

N*log^2(N) solution with small hidden constant using Fenwick tree: use binary search to find minimum X such that there are at least Y 0’s among first X elements, it will give you position of Y’th 0 in given array.

You can also use BIT to store the number of free spaces on the left and right of every index.

Setter’s Code : http://ideone.com/9GKD4F

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s