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)~