GCJ round 1B

A. Notice that you always take a prefix after sorting.

B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k

C. DP, although many topcoders use trie.

dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)

dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
  cut dict[w] from the end of S[0..i-1]
  for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away

One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector for dict is 10 times slower than using char[][], which means a difference of 15min vs 1.5 min