Editorial for DMOPC '22 Contest 5 P3 - Sorted XOR

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: yzhao123

Performing an operation can change the prefix bitwise XOR to any value. Each time we must perform an operation, we consider which bits should be set in the prefix bitwise XOR. We can always a flip a really large bit to make the XOR value greater than the previous one. Thus, we just need to consider the bits up to the highest bit that A contains.

Subtask 1

Run a naive dp[i][x] which represents the minimum number of operations you need to perform to make B nondecreasing for the first i elements and with a current prefix bitwise XOR of x.

Time Complexity: \mathcal{O}(N\max(A)^2)

Subtask 2

Maintain the prefix bitwise XOR as an array S of size 30 whose values can be -1, 0, or 1, where -1 represents bits which are arbitrary. Initially, all bits are 0. Whenever you perform an operation, all bits become arbitrary. The only time the prefix bitwise XOR would decrease is when the highest bit of A_i is set in the running bitwise XOR, so an operation must be performed. Loop through the array and perform an operation if necessary. Otherwise, set the highest bit, then loop through the bits and XOR each bit of A_i with each known corresponding bit in S. The arbitrary bits remain unknown, since they could still be either 0 or 1.

Time Complexity: \mathcal{O}(N \log{A_i})


There are no comments at the moment.