PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Dynamic Programming
PROBLEM:
An array B is said to be good if B_i \oplus B_j = |B_i - B_j| for every pair of indices (i, j).
Given an array A of length N, find the length of its longest good subsequence.
EXPLANATION:
First, let’s understand when two integers X and Y can satisfy X\oplus Y = |X-Y|.
Specifically, let’s look at any single bit b.
Without loss of generality, let X \ge Y, so that |X-Y| = X-Y.
There are four options:
- b is not set in the binary representations of both X and Y.
Then, b will not be set in X\oplus Y, and also 2^b will not contribute to X-Y in any way. - b is set in the binary representations of both X and Y.
Once again, b will not be set in X\oplus Y, and 2^b will not contribute to X-Y since X adds 2^b and Y subtracts 2^b. - b is set in X but not in Y.
Here, b will be set in X\oplus Y, and also 2^b will be added to X-Y since X adds 2^b while Y subtracts nothing.
Note that the contribution to both X\oplus Y and X-Y is still equal. - b is not set in X, but is set in Y.
Here, b will be set in X\oplus Y, but 2^b will be subtracted from X-Y; since X adds 0 while Y subtracts 2^b.
From the above cases, we make the following observations:
- For any bit b, its contribution to X\oplus Y is not smaller than its contribution to X-Y.
In particular, this means X\oplus Y \ge X-Y always. - Next, the only case when the contributions are unequal are in the last case, i.e. a bit set in Y but not in X.
Thus, X\oplus Y = X-Y is possible only when no bit ever triggers the fourth case - that is, there must not exist any bit that is set in Y but not in X.
Note that is equivalent to saying that every bit set in Y must be set in X, i.e. Y must be a submask of X.
With the above knowledge, it’s now quite easy to classify good arrays.
Since every pair of elements must have XOR equal to difference, this would mean that for every pair of elements, one must be a submask of the other.
An alternate way of stating this is that for every element, it must be a submask of every larger element.
Because “is a submask of” is a transitive property, this is equivalent to just every element being a submask of its next larger element.
That is, we have the following simple method to check if an array B is good:
- Sort B in non-decreasing order.
- Then, check if B_i is a submask of B_{i+1} for each 1 \le i \lt |B|.
Equivalently, the bitwise AND of B_i and B_{i+1} must equal B_i.
With this criterion, it’s now quite easy to compute the longest good subsequence for the given array A.
Let’s first sort the array A, since that clearly doesn’t change the answer (and our easy check relies on sortedness).
From now on, we assume A_i \le A_{i+1} for all 1 \le i\lt N.
Now, define dp_i to be the maximum possible length of a good subsequence that includes A_i.
Since only adjacent elements need to be checked, we only care about the previous chosen element being a submask of A_i.
Thus, we obtain dp_i = \max(1 + dp_j) across all j such that A_j is a submask of A_i.
The answer is then \max(dp_1, dp_2, \ldots, dp_N).
This gives a solution in \mathcal{O}(N^2) which is easily fast enough for N \le 100.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
dp = [0]*n
for i in range(n):
for j in range(i):
if a[i] & a[j] == a[j]: dp[i] = max(dp[i], dp[j])
dp[i] += 1
print(max(dp))