PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You have an array A.
On the X-th second, you can do the following operation:
- For each index i, leave A_i unchanged, or replace it with A_i\mid X.
Find the minimum number of seconds needed to obtain a sorted array.
EXPLANATION:
Suppose we fix the value of X.
Let’s try to check whether using the operations at seconds 1, 2, 3, \ldots, X is enough to make the array sorted.
For this, it’s important to understand exactly what we can modify with our operations.
Since we’re working with bitwise OR, we can only take an unset bit in some number and set it - but never the opposite.
With this in mind, let’s look at 1, 2, 3, \ldots, X.
Which bits can it affect?
Well, if 2^b \leq X is the largest power of 2 till X, then it’s easy to see that we can only affect bits 0, 1, 2, \ldots, b.
Bits higher than b cannot be affected by operations till X no matter what, since nothing till X has any of them set at all.
With this in mind, let’s look at the part which we can’t affect, namely the bits higher than b.
Specifically, let’s create a new array B, where B_i equals only the sum of bits higher than b that are set in A_i.
For example, if A_i = 45 = 2^5 + 2^3 + 2^2 + 2^0, and b = 2, we’d have B_i = 2^5 + 2^3 = 40.
There are now two possibilities: either B is sorted, or it’s not sorted.
- If B is sorted, then it’s always possible to obtain a sorted A.
For example, one way of doing this is to just set all bits \lt b in every element.
Since they’re all equal now, and bits \gt b are sorted, the entire array is sorted. - If B is not sorted, it’s impossible to obtain a sorted A.
This is because B being not sorted means there’s some issue with bits \gt b; which we cannot do anything about using smaller bits.
Looking closer at what happens above, we see that we only care about the smallest X for which the resulting array B becomes sorted.
It’s also easy to see that the array B depends only on the highest power of 2 that’s \leq X.
In particular, this means the only important “breakpoints” are the powers of two themselves, since all the values 2^k, 2^k+1, 2^k+2, \ldots, 2^{k+1}-1 will end up having the same array B.
This gives a fairly simple solution: for each power of 2, create the corresponding array B by stripping out all lower powers, and check if it’s sorted.
The answer is the smallest power of 2 that works.
Of course, if A is already sorted initially, the answer is 0.
TIME COMPLEXITY:
\mathcal{O}(N\log\max(A)) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if a == sorted(a): # Already sorted
print(0)
continue
for bit in range(30):
# Can pretend all bits <= this one are set, then check if sorted
for i in range(n): a[i] |= (2 << bit) - 1
if a == sorted(a):
print(1 << bit)
break