PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Ashish Gupta
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Medium
PREREQUISITES:
PROBLEM:
Chef has an array A of N integers. He asks you Q queries. For each query, you are given the following:
- An integer X (0 \leq X \lt 2^{20}).
- An array B of size M such that 1 \leq B_j\leq N.
You need to erase minimum number of elements from A such that the bitwise-OR of the remaining elements is at most X and no element having index B_j is erased.
For each query, find the maximum number of remaining elements such that the bitwise OR of the remaining elements is at most X and no element with index B_j is erased. If it is impossible to get an OR of at most X, print -1.
Note: The bitwise OR of an empty array is considered 0.
QUICK EXPLANATION:
- Let us calculate dp[mask] which denotes the number of elements A_i such that A_i \& mask = A_i using SOS Dynamic Programming
- Subtask-1: We can iterate over all mask such that 0 \leq mask \leq X, and take the maximum over all dp[mask].
- Subtask-2: We can iterate from the most significant bit towards lowest significant bit and try calculating answer at each step.
EXPLANATION:
Subtask-1
To make explanation more lucid, let us first define subset of X as following: An element Y is called a subset of X if the set-bits in the binary representation of Y is a subset of set-bits in the binary representation of X. So, If X = 1010_2, then Y = 1010_2, 1000_2, 0010_2, 0000_2 represents subset of X.
Let us first try to answer a simpler version of Subtask-1. Suppose we are given an integer X, and we are asked to find out the maximum number of elements whose bitwise-OR is a subset of X.
So, if A_i is one of the elements which forms the answer, then we can say that A_i \& X = A_i. In other words, we want to find out the the number of elements A_i such that A_i \& X = A_i. Using SOS Dynamic Programming we can calculate the answer for each possible X and store it in dp[X].
Now, once we have this dp calculated, we can try solving our original Subtask-1. We are given X, and we want to find out the maximum number of elements such that their bitwise-OR is at most X. Note that all the subsets of X are less than or equal to X, hence if we take the max over all dp[i] such that 0 \leq i \leq X, we will get our required answer!
Subtask-2
Now we are also given some elements which cannot be removed from the array. Let us denote their bitwise-OR by Y. If Y > X, then we can say that the answer is -1, otherwise we can start by taking our current answer as dp[Y].
Now let’s start with the most significant bit, and iterate towards the lower significant bit. At each point, we will consider the cases if this bit is set in the final OR or not, and will update our answer accordingly. Let the current bit be the i^{th} bit. We have the following two cases:
The i-th bit is set in X
Let val denotes the current value such that the final OR is a subset of val and | denotes the bitwise-OR.
If val | 2^i > X, then this means that we cannot set this bit in our final OR, as it will make it greater than X.
Otherwise, we have the freedom to either set this bit in our final answer, or let it remain unset.
If we don’t want to set this bit, then we can set any of the bits at positions 0 to i-1 (as the resultant OR will always be less than X), and therefore we can update our answer using the dp that we calculated ( max(ans , dp[val'], where val' has all the bits set at positions 0 to i-1, unset at position i, and same as val for positions greater than i )
If we want to set this bit, we can update our val \rightarrow val | 2^i, and update our answer as max(ans , dp[val])
The i-th bit is not set in X
In this case, this bit cannot be set in the final OR, as that will make the final OR greater than X. Hence, we ignore this bit, and continue
TIME COMPLEXITY:
To calculate the dp, we will require O(N \cdot 2^N) time, where N = 20 in our problem.
For each query, we will require O(N + M) time.
SOLUTION:
Editorialist’s Solution
Tester-1’s Solution
Tester-2’s Solution