CleanerSpace's blog

Tower Research Capital, OA 2022
By CleanerSpace, 2 years ago, In English

How to solve this problem?

Problem:

You are given an array of N integers. Now, you can choose any strictly increasing subsequence of the array and calculate the bitwise OR of all the elements of the subsequence. A subsequence can be obtained by deleting several elements (possibly none or all) from the array without changing the order of the remaining elements. A sequence a1, a2, a3…am is called strictly increasing if a1 < a2 < a3 <…< am

Task:

Determine all possible different values of p (p>=0) such that there exist a strictly increasing subsequence such that the bitwise OR of all the elements of the subsequence is equal to p.

Constraints:

1 <= N <= 10^4
1 ≤ arr[i] < 1024

Sample Input:

1
4
3 5 1 5

Sample Output:

0 1 3 5 7
  • Vote: I like it
  • +14
  • Vote: I do not like it

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

A small hint, the value of p can't exceed 1024, so there are 10 bits involved. The length of subsequence can't be greater than 10, because each successive term of subsequence should make at least one bit from 0 to 1 in the value of p made in the subsequence so far.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Are you sure about the last claim? Take the array to be a[i] = i, and N = 1024. The whole array is an increasing subsequence, and the bitwise OR of everything is 1023.

    To answer the original question, a simple dp suffices. dp[i][mask] is the smallest possible value of the last element of an increasing subsequence of the array till index i which has bitwise OR equal to mask. Time complexity is $$$O(N \cdot \max_i a_i)$$$.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think his point is that any p value generated can be done so by a subsequence of length at most 10..?

      Though I'm not sure why this helps

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes that was my point and it helps a lot :) Think about a simple dp :)

        → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      See, I'm saying that if you can get a value of $$$p$$$ using any subsequence of length greater than $$$10$$$, then the same value of $$$p$$$ can be obtained with a subsequence of length less than $$$10$$$ too. Basically its useless to take subsequences of length $$$> 10$$$

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

        I don't immediately see how you could use this fact non-trivially (except for adding another dimension to the dp I mentioned earlier and making it slower). It does have the advantage that you can find the shortest such sequence explicitly by maintaining pointers to the state which was used for the update. Is there a way faster than that?

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

          I got the way you defined the dp state. But, won't each transition for dp[i][mask] would require O(max ai) time complexity ? Like, dp[i][mask]will be minimum of dp[i-1][mask] or ai if there exists some mask' such that dp[i-1][mask'] < ai and also mask' | ai == mask ?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            You can do something like this to process all masks at the same time:

            for each i:
  copy over dp[i - 1] to dp[i]
  dp[i][a[i]] = min(dp[i][a[i]], a[i])
  for each mask:
    if dp[i - 1][mask] is not unassigned and < a[i]:
      dp[i][mask | a[i]] = min(dp[i][mask | a[i]], a[i])

            Here if unassigned stuff is passed to min, it returns the other argument.

            → Reply