Editorial for Cheerio Contest 3 P4 - Bit Flips
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
There are a number of clues which may provide intuition for the full solution, including:
- When comparing integers, higher bit positions are more significant than lower bit positions.
- If some element has a bit set at the highest bit position, then every element to its right must also have this highest bit set.
This motivates the following observation:
If the bit positions are labelled from to
, where
represents the lowest bit position and
represents the highest bit position, then an array
is sorted if and only if:
- There is a (potentially empty) prefix of the elements which do not have the bit at position
set, and the remaining (potentially empty) suffix has the bit at position
set, and
- Both the prefix and suffix are sorted themselves, when only considering the bit positions up to
.
We can now formulate a dynamic programming recurrence.
Define as the minimum number of moves to sort the subarray indexed from
to
(inclusive), when we only consider the bits up to position
. If
is the number of elements in the subarray
with the bit at position
set, and
is the number of elements in the subarray
with the bit at position
unset, then
Time complexity:
Comments