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: r3mark

For Subtask 1, we employ an interval dynamic programming solution. Let dp[i][j][d] be equal to the least number of character swaps necessary to sort the i^{\text{th}} to j^{\text{th}} numbers when only looking at the d leftmost bits. This leads to the recurrence: \displaystyle dp[i][j][d]=\min_{i-1\le k\le j} {(dp[i][k][d-1]+dp[k+1][j][d]+n[i][k][d][1]+n[k+1][j][d][0])} where n[i][j][d][x] is the number of x's as the d^{\text{th}} digit in the i^{\text{th}} to j^{\text{th}} numbers (computing this can be easily sped up with a prefix sum array).

Time Complexity: \mathcal{O}(BN^3)

For Subtask 2, observe that if A[i][j][d] is the least k' such that \displaystyle dp[i][k'][d-1]+dp[k'+1][j][d]+n[i][k'][d][1]+n[k'+1][j][d][0]=\min_{i-1\le k\le j} {(dp[i][k][d-1]+dp[k+1][j][d]+n[i][k][d][1]+n[k+1][j][d][0])} (often called the breaking point) then A[i][j][d]\le A[i][j+1][d]\le A[i+1][j+1][d]. 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: \mathcal{O}(BN^2)


Comments

There are no comments at the moment.