ram2012k's blog

Find Kth smallest element from all or-subarrays
By ram2012k, 3 years ago, In English

You are given an array A of N integers.

Create another array B containing all or-subarrays of A . i.e B contains $$$A_{l}|A_{l+1}|...A_{r}$$$ for all $$$1 <= l <= r <= N$$$

You are provided Q queries . n each query you have to print K-th smallest element of B.

$$$1 <= A_{i} <= 10^{5}$$$ $$$1 <= Q , N <= 10^{5}$$$ $$$1 <= k <= N*(N+1)/2$$$

Example

N = 3 A = [1, 2, 3] Q = 3 Queries = [1, 2, 6]

B = {1, (1|2), (1|2|3), 2, (2|3), 3} = {1, 3, 3, 2, 3, 3}

The queries are answered below

• The 1st smallest element is 1

• The 2nd smallest element is 2

• The 6th smallest element is 3.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Source?

→ Reply
»
3 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Upd misunderstood the problem

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not from distinct , k-smallest from all subarrays

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry my bad!

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Aman_j1 Can you explain your solution of the particular problem you had mentioned in your original comment?

        UPD: Nvm, I solved it.

        → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe solving this problem first will help: Link

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I solved the problem which you linked, but I am still unable to solve this problem. Can you provide some hints? If this problem was to find the Kth distinct smaller OR, it would be easy. [ because the no of distinct OR's starting from some index would be (Max(A)) ]

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Calculate pairs (value, count). There are at most O(N log A_max) of them.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        does this seem right? 

        set of pairs S[n] element,count
for elements in array(n to 1) {
   if(index is n) S[index].insert(array[index],1)
   else {
       S[index].insert(array[index],1)
       for j in S[index+1] 
           if(j.first|array[index] exists in S[index]) {
          //find the pair, and increment count by 1 and insert back into the set
           }   
           else S[index].insert(j.first | array[index],j.second)
    }
 }
        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can use persistent segment tree for this problem.

For each array element ending at jth index compute suffixes of all bitwise or values ending at jth index. For example take array = [3,1,4,2,6]

If we take j = 5 (1 based indexing) arr[5]=6 compute all bitwise or [7,7,6,6,6]

So in the range (1,2) make range update with value 7.

In the range (3,5) make range update with value 6.

We can now answer queries like kth min|max in a range.

Since, there could only $$$O(\log_2{}100000)$$$ range updates for a single index.

Preprocessing can be done in $$$O(n\log{}n\log{}\max{(ai)})$$$.

Queries can be performed in $$$O(q\log{}n)$$$.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For each endpoint of a subarray $$$i$$$, there are only $$$\log{A_i}$$$ possible subarray OR-sum values, so we can just find all of those values and the number of times each one occurs, sort them, then build a prefix sum array on the counts and binary search for when we reach a count of $$$k$$$ in each query.

edit: nvm someone already described this idea

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you are correct. I had AC with this approach.
    The only observation is that there won't be much distinct elements in the resultant OR array B. So we can create frequency map and then use Binary search on that.

    → Reply