krishan's blog

How can we solve this question? What is the approach behind this?

By krishan, 4 years ago, In English,

I only need the hint. That's all. I don't need the exact solution. Thank you.

  • Vote: I like it  
  • -6
  • Vote: I do not like it  

4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Let's start from a slow solution first.

In fact you are asked to place 1 in 2nd free cell of your answer, then to place 2 in 3rd free cell of your answer while starting counting from position where you had placed 1 (and starting from the beginning if you reached end of array), then to place 3 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.

  • »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the BIT approach in more detail?