Блог пользователя CleanerSpace

Tower Research Capital, OA 2022
Автор CleanerSpace, 2 года назад, По-английски

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
  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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)$$$.

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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

      → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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$$$

      → Ответить
      • »
        »
        »
        »
        2 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

        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?

        → Ответить
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 ?

          → Ответить
          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            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.

            → Ответить