Text Editor — Facebook Hacker Cup Qualification Round 2016

Revision en2, by zscoder, 2016-01-10 13:32:56

Abridged Problem Statement : You have a list of N distinct words, and you want to print K of them. You have a very basic text editor : It supports 3 types of operations: typing a letter, deleting the previous letter, and printing the current document. You need to leave the document empty after printing K words. What's the minimum number of operations required to get the job done?

Constraints : 1 ≤ K ≤ N ≤ 300 The total length of all N words in each set will be at most 100, 000 characters.

Solution :

Name the words s1, s2, ..., sN. Let s0 = "". We initially have s0 on the document. After some operations, we want to print k of s1, s2, ..., sN and change the document to s0. For some pair of string si, sj, how many operations do we need to print sj if we have a document with si? Let p be the length of the Longest Common Prefix of si and sj. We can compute this naively in O(min(|si|, |sj|)). Then, we need to delete |si| - p characters, type |sj| - p characters, and print it (1 operation), for a total of |si| + |sj| - 2p + 1 operations.

Tags editorial, fhc, facebook hacker cup, dp, string

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English zscoder 2016-01-12 04:06:49 0 (published)
en8 English zscoder 2016-01-10 16:53:19 2 Tiny change: '$L(i, j) \le L(i, k)$' -> '$L(i, j) \ge L(i, k)$'
en7 English zscoder 2016-01-10 16:52:55 471
en6 English zscoder 2016-01-10 14:20:10 9
en5 English zscoder 2016-01-10 14:15:03 841
en4 English zscoder 2016-01-10 14:02:48 641
en3 English zscoder 2016-01-10 13:56:30 1227
en2 English zscoder 2016-01-10 13:32:56 553 Tiny change: 'cters.\n\nName t' -> 'cters.\n\nSolution :\n\nName t'
en1 English zscoder 2016-01-10 13:25:03 645 Initial revision (saved to drafts)