Facebook Hacker Cup 2016 Qualification Round 1.4

LiveCode is the premier environment for creating multi-platform solutions for all major operating systems - Windows, Mac OS X, Linux, the Web, Server environments and Mobile platforms. Brand new to LiveCode? Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller, robinmiller

Post Reply
MaxV
Posts: 1577
Joined: Tue May 28, 2013 2:20 pm
Location: Italy
Contact:

Facebook Hacker Cup 2016 Qualification Round 1.4

Post by MaxV » Mon Jan 11, 2016 6:17 pm

You have a list of N distinct words, consisting of only lowercase letters. You'd like to print any K words from this list, one per page, in any order.

You will accomplish this using a very basic text editor. It supports 3 types of operations: typing a letter, deleting the previous letter, and printing the current document. Note that it does not allow the cursor to be moved! This means that the first operation may only add a letter to the end of the document, and the second may only delete the last letter (if any). Due to issues with memory leakage, you also need to remember to leave the document completely empty after you've printed your K words!

What's the minimum number of operations required to get the job done?

As an example, let's say that you want to print 3 of the following 5 words:

Code: Select all

a
hair
box
awesome
hail
One optimal sequence of 15 operations is as follows:
  • type 'h', 'a', 'i', and 'r' (document = 'hair')
  • print
  • backspace (document = 'hai')
  • type 'l' (document = 'hail')
  • print
  • backspace 4 times (document = empty)
  • type 'a' (document = 'a')
  • print
  • backspace (document = empty)
Input
Input begins with an integer T, the number of sets of words you want to print. For each set, there is first a line containing the space-separated integers N and K. The next N lines contain the set of words, one per line.

Output

For the ith set of words, print a line containing "Case #i: " followed by the minimum number of operations required to print K of the words and then leave the document empty.

Constraints

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

Input

Code: Select all

5
3 3
x
y
z
2 1
loooong
tiny
4 3
fff
fffff
ff
ffff
5 3
a
hair
box
awesome
hail
8 6
fox
of
xfox
foo
foxxx
off
foff
foox
Output

Code: Select all

Case #1: 9
Case #2: 9
Case #3: 11
Case #4: 15
Case #5: 26
Livecode Wiki: http://livecode.wikia.com
My blog: https://livecode-blogger.blogspot.com
To post code use this: http://tinyurl.com/ogp6d5w

Post Reply

Return to “Getting Started with LiveCode - Experienced Developers”