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