PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
For an array A of length N, let
Given N and M, let S denote the maximum possible value of f(A) across all integer arrays of length N with elements in [0, M].
Count the number of these arrays for which f(A) = S.
EXPLANATION:
If N = 1 all arrays have f(A) = 0, and there are M+1 possible arrays so the answer is simply M+1.
From now on, we assume N \ge 2 so a non-trivial XOR is possible.
First, we try to find the value of S, i.e. the maximum possible sum of adjacent bitwise XORs.
Let \text{mx} denote the maximum bitwise XOR of two integers in [0,M].
Clearly, an upper bound on the value of S is (N-1)\cdot\text{mx}, since at best, each adjacent pair can be made to have a XOR of \text{mx}.
It’s also easy to see that this bound is achievable - for example, if (x, y) is the pair such that x\oplus y = \text{mx}, then the array [x, y, x, y, x, y, \ldots] will have f(A) = (N-1)\cdot \text{mx}.
This means we now only need to count arrays such that every adjacent pair has a bitwise XOR equal to \text{mx}.
Observe that all such arrays are in fact uniquely determined by their first element A_1, and further will contain exactly two distinct elements.
This is because:
- A_1 \oplus A_2 = \text{mx} fixes A_2 = \text{mx} \oplus A_1.
- A_2 \oplus A_3 = \text{mx} fixes A_3 = \text{mx} \oplus A_2 = \text{mx} \oplus (\text{mx} \oplus A_1) = A_1.
- A_3 \oplus A_4 = \text{mx} fixes A_4 = \text{mx} \oplus A_3 = \text{mx} \oplus A_1 = A_2.
\vdots - In general, elements at odd indices will equal A_1 and elements at even indices will equal \text{mx} \oplus A_1.
Further, we cannot have A_1 = \text{mx}\oplus A_1, since this would imply \text{mx} = 0 which as we will see below is never the case.
Thus, A will consist of exactly two distinct elements, that alternate.
So, all we really need to count is the number of valid first elements - this will also tell us the number of arrays.
Now, let us focus on \text{mx} itself, i.e. the maximum bitwise XOR of two values in [0, M].
Let k be the highest set bit in M, i.e. k is the largest integer satisfying 2^k \le M.
Then, two values \le M can only affect bits 0, 1, 2, \ldots, k.
So, the absolute maximum possible bitwise XOR is when all of these bits are set; corresponding to the value 2^0 + 2^1 + \ldots + 2^k = 2^{k+1}-1.
Observe that for any 0 \le x \le M, there must exist a unique integer y such that x\oplus y = 2^{k+1}-1.
In fact, y is exactly the number which has its set bits be the complement of the set bits of x.
That is, for each 0 \le i \le k,
- If bit i is set in x, it must be unset in y.
- If bit i is unset in x, it must be set in y.
In particular, this will give us not just x\oplus y = 2^{k+1} - 1, but also x+y = 2^{k+1}-1, since if two integers do not share any set bits, their sum equals their XOR.
We can now use this property to solve our problem.
Recall that we were looking for only the number of valid first elements.
If we want A_1 = x,
- 0 \le x \le M must be satisfied.
- The complement of x is 2^{k+1}-1-x.
Since this will be the only other element of the array, it must also lie in [0, M], so we obtain
0 \le 2^{k+1}-1-x \le M.
This translates to 2^{k+1}-1-M \le x \le 2^{k+1}-1.
As long as x satisfies both inequalities above, it is a valid first element.
It can be seen that this corresponds to all x in the segment [2^{k+1}-1-M, M].
The length of this segment is
which becomes our answer.
Recall that k here is the largest integer such that 2^k \le M, and can be found in \mathcal{O}(\log M) time by just iterating through k starting from 0.
TIME COMPLEXITY:
\mathcal{O}(\log M) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
if n == 1: print(m+1)
else:
pw = 1
while pw <= m: pw *= 2
lo = (pw - 1) - m
print(m - lo + 1)