## Editorial for DMOPC '18 Contest 1 P6 - Sorting

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:

For Subtask 1, we employ an interval dynamic programming solution. Let be equal to the least number of character swaps necessary to sort the to numbers when only looking at the leftmost bits. This leads to the recurrence: where is the number of 's as the digit in the to numbers (computing this can be easily sped up with a prefix sum array).

**Time Complexity:**

For Subtask 2, observe that if is the least such that (often called the breaking point) then . Thus, we can apply Knuth's Optimization to the recurrence from Subtask 1. The proof of the observation follows the standard proof of Knuth's.

Certain implementations may require compressing the DP table to only store the previous row for the digit.

**Time Complexity:**

## Comments