## 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.**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