Autocomplete

View as PDF

Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 N 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 N words?

Input

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

Output

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

Constraints

1 \le T \le 100
1 \le N \le 100\,000

The N words will have a total length of no more than 1\,000\,000 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 1 + 2 + 1 + 3 + 4 = 11 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

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


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

    Question displays 1 ≤ T ≤ 100 and 1 ≤ N ≤ 100,000.


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

    .


    • 1
      quantum  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.


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

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


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

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


    • 2
      fifiman  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