Initials

This problem gives us a list of people's names, and rules for forming hashes (take last initial, next k letters of last name, first initial, k-len(last_name)+1) and asks for the minimum k summed over all names such that the hashed names still sort correctly.

The first thing to see is that a greedy solution seems enticing: do the names in order, and add letters until it sorts correctly. This fails, however. Consider just two names (after flipping first and last names, as we have to do)

• Ma C
• Mb A

We greedily select MC

• MC

Then we greedily select MA

• MC
• MA

We find however that this sorts incorrectly, so we add a character

• MC
• MbA

We find this STILL sorts incorrectly, but are out of letters to add. The only solution is to have taken the 'a' from the first name. Since we need some amount of backtracking, we know the solution cannot be purely greedy.

The common solution to a problem that almost looks greedy but isn't is to apply some DP to it.

The state intuitively will include which name we're on, but as the example above shows, it also depends on how many characters we've added to the word we're on. This leads to the following recursive relation

dp[word][letters added to word] = min dp[word - 1][k]

The value in the dp[i][j] is minimum number of characters to place i by adding j letters to it.

The DP array has 1000*80 elements, and each relation takes 80 steps, giving us 1k * 80^2, or 6.5 million. Plenty fast.