## Autocomplete

View as PDF

Points: 10
Time limit: 25.0s
Memory limit: 1G

Author:
Problem type
##### Facebook Hacker Cup 2015 Round 1

Since you crave state-of-the-art technology, you've just purchased a phone with a great new feature: autocomplete!

Your phone's version of autocomplete has some pros and cons. On the one hand, it's very cautious. It only autocompletes a word when it knows exactly what you're trying to write. On the other hand, you have to teach it every word you want to use.

You have distinct words that you'd like to send in a text message in order. Before sending each word, you add it to your phone's dictionary. Then, you write the smallest non-empty prefix of the word necessary for your phone to autocomplete the word. This prefix must either be the whole word, or a prefix which is not a prefix of any other word yet in the dictionary.

What's the minimum number of letters you must type to send all words?

#### Input

Input begins with an integer , the number of test cases. For each test case, there is first a line containing the integer . Then, lines follow, each containing a word to send in the order you wish to send them.

#### Output

For the test case, print a line containing Case #i:  followed by the minimum number of characters you need to type in your text message.

#### Constraints

The words will have a total length of no more than characters.
The words are made up of only lower-case alphabetic characters.
The words are pairwise distinct.

NOTE: The input file is about 10-20MB.

#### Explanation of Sample

In the first test case, you will write h, he, l, hil, hill, for a total of characters.

#### Sample Input

5
5
hi
hello
lol
hills
hill
5
a
aa
aaa
aaaa
aaaaa
5
aaaaa
aaaa
aaa
aa
a
6
to
be
or
not
two
bee
3
having
fun
yet

#### Sample Output

Case #1: 11
Case #2: 15
Case #3: 11
Case #4: 9
Case #5: 3

• commented on Dec. 24, 2015, 9:47 p.m.

Question displays 1 &leq; T &leq; 100 and 1 &leq; N &leq; 100,000.

• commented on Dec. 24, 2015, 10:00 p.m.

Fixed

• commented on Dec. 24, 2015, 1:29 a.m.

.

• commented on Dec. 24, 2015, 9:53 a.m.

Judges Durandal and Excalibur are unavailable at the moment. There is little I can do to alleviate the fact.

• commented on Dec. 24, 2015, 2:55 p.m.

Judges won't connect even after pulling and changing conf file.

• commented on March 21, 2015, 12:41 p.m.

Shouldn't this problem be categorised as graph theory as well?

• commented on March 21, 2015, 2:11 p.m. edited

The problem can be solved using a string algorithm that is a graph too. I think string algorithm is better since it is more specific