Connection Status:
Competition Arena > HandlesSpelling

HandlesSpelling

TCO10 Qual 2 · 2010-04-11 · by Nickolas

TCO10 Qual 2 · 2010-04-11 · by Nickolas · Dynamic Programming
Class Name: HandlesSpelling
Return Type: int
Method Name: spellIt
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

You have recently gained access to the badge printing machine used by TopCoder to print name badges for their tournaments. Each badge produced by the machine contains the handle of a TopCoder member, and you can print any number of badges for each handle from a predefined list. You decide to play a game using the machine. Given an arbitrary sentence, you want to spell it using only name badges that you print with the machine in some optimal way.
The rules of the game are as follows. First, you remove all spaces and punctuation from the sentence. Then, you try to spell out the resulting string by printing out name badges and arranging them in a single row. Each badge you use must contain a handle which is a contiguous substring of the string. Badges can touch but not overlap. Letters in the string which are not represented by the badges are considered "uncovered".
For example, consider the case where only the following TopCoder members exist: {"E", "HE", "L"}. If you want to spell the sentence "HELLO", you might try to do it by printing out one "E" badge and two "L" badges. However, "H" and "O" would then be uncovered, and you wouldn't be able to add an "HE" badge because it would overlap with the "E". A better way would be to print out one "HE" badge and two "L" badges. Then, only the "O" would be uncovered.
You want to create the best possible arrangement of badges, so you've come up with the following scoring system. Define A as the length of the longest contiguous sequence of letters covered with the badges, and B as the number of letters that are uncovered. If all letters are uncovered, A is equal to 0. The score of the arrangement is A^2-B.
You are given a String[] parts. Concatenate the elements of parts to obtain the original sentence (with spaces and punctuation already removed). The handles on your name badges are given to you in the String[] badges. Return the maximal possible score you can obtain using the given badges.

Constraints

  • parts will contain between 1 and 20 elements, inclusive.
  • Each element of parts will contain between 1 and 50 characters, inclusive.
  • badges will contain between 1 and 50 elements, inclusive.
  • Each element of badges will contain between 1 and 50 characters, inclusive.
  • parts and badges will contain only uppercase letters ('A'-'Z').
  • All elements of badges will be distinct.
Examples
0)
{"HELLO"}
{"E","HE","L"}
Returns: 15

Example from the problem statement.

1)
{"ALGORITHM","QUALIFICATION","ROUND","TWO"}
{"AL", "CAT", "GOR", "IFI", "ION", "ROUND", "T"}
Returns: 282

The optimal spelling is "AL"-"GOR"-I-"T"-HMQU-"AL"-"IFI"-"CAT"-"ION"-"ROUND"-"T"-WO. In this spelling, A=17 and B=7.

2)
{"GOOD","LUCK"}
{"GOODLUCKBJ","G","L"}
Returns: -5

The handle used has to be a proper substring of the sentence spelled, and not vice versa. In this case at most one letter in a row can be covered with badges, and 6 letters are left uncovered, so the total score is negative.

3)
{"ANDDOHAVEFUN"}
{"HAV"}
Returns: 0
4)
{"QWERTYU"}
{"WE","TY","ERT"}
Returns: 5

test where "B is minimized" fails

5)
{"WERWERW","HJKRSDFSIFG","WERJKOIEFAE","KRUIDFUI"}
{"XCV","MBVN","ZXCM"}
Returns: -37

no coverings at all

6)
{"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
{"X","XX","XXX","XXXX","XXXXX","XXXXXX","XXXXXXX","XXXXXXXX","XXXXXXXXX","XXXXXXXXXX","XXXXXXXXXXX","XXXXXXXXXXXX","XXXXXXXXXXXXX","XXXXXXXXXXXXXX","XXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX","XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
Returns: 1000000

max test

8)
{"VOQYFESLLJNJYXCFDUHNWZWOPLHBZGWEKDLZSCWOOV","XSHKCNTIYLVUUKDCJBZOARHDTJYOUCD","YGWJDGWBVNKFOMAONKCHTJIUVSTB","KMKIVC","KDAGRGNNWPLISUSRNGNKRQHLELHBLMEPXFMTWSDAAHFBXAM","NVINVIHMYXVSLFJRRIFVWCQAILTRSNIUXFAGTGITADZLYNA","YHWGPDHHAMJQLUWQEWWCNTXNRUKCSHLUKFHJNZXTQJEZJFPZ","ZPBYQRIBGLYHBMFVQDGMCHJLXPMXKX","NJOBXNIOZXFKBMXSFJIBXCQCLQFHBCZBZEGAYGFWZMVQXJ","FIGCZWIVVFMFRWOAQUZMZOOC","EA","OJCQKIWAMSCXMMAQKWEZBXGWULPFYWPCUODFIAQVOWUDBYD","DTHVDWYPZTRZSXIHUVPOHUO","MWDIPJUAYHIHLPEJFMCLFOYRJKZTNHDWDCMOSAVEZCP","AHOY","AVEXCGTEXSQBZPTST","AYWQULYXDXURJZZMP","PQEXPHYSLFINKKHAFDHKRXGJXTDRBMCDOYXSXEAUSWWOFM","TY","UGSTYRLTEQDADHFIKUDX"}
{"YFZNTPQTPHUETLXUSGYCTPPWCWIFQZKVSCVUARCYA","MEWWVHVMONKBKIJCYHYZLKGFZOGADMRPDGJJMSC","QRJYDSMNRXRZ","PAOCDBPEVAMSNGVOBOF","D","ENANIGRRITTFZWFXRNGVIRYLHABTPPGDVYUGAEZEDACNGHQAO","MCEZDWZAGYRWEDZUNRLGW","SRKKQQNEOOZGAF","JPEGKCEJCBAREVEICGJKMEHR","LIHNZUTEUOKQEXNXUKYS","DOIKDWFNFTSKABGABGUHLVTPAXI","HNVKNUDISGMRZYFFTBSHFBXIA","PUZDGGQKNTBIM","GVGSQX","MTTTVJUBKSRXKD","ZGLOGYHPRDGILJNZJSNKHKNOEUMKTWSOHXY","YRGNAYPOYHDXYMJULDEAKYEXDNN","MFVZSWHXE","GJPZFQRGIXILKXZN","CLDQUGWQTHTQHWDOJOCTUCSUAUCOVIIBIPCPPOTARF","QJEVOKPKOVKJWCEHEFNJBLXFUJYYOXLPPKTOBOMJBMTXJX","TQPPVFXXXQWZBSKJUKSV","FUPKVDPKFFOSEHBBKTVGZAYFBOZHDTMOFCRQBAAAHAWHT","TFFJVTITNZVVXBBHUFZIQNUSUW","GKQRCDRPPUNGWIN","KTNJZTJOQVORZFJEKUAYHZKOQK","RUZUCQBQKMLPYHNNMWJJMHWWCFJJVG","DTPSHKZKKNIUBWDGZQTUQYH","UKNSFM","BZSVCYCFGPOZUTNWYZZUWUD","NHHEPGKOMSUC","ZRASGMUIWLVKVLEUWYBJICSMENDKWULYBVIRCXNQBDP","IHBCMAQEJAXWTIXDIPABBTPTOLQNFXKTJWTPSIJGSFVTVOS","ZNTZIQVKIHKORESFDNVOXR","BRNBHYXCRANXABBOGGEFTZQUVETOQUN","KZWCKUUGAZHJQBGRSVDAVSCPKACYBHMYHFDWHZEDN","BCHHJGMRJYWZKVCMDGMQW","OIVGZTUMLVFADWEXKGOZLGYVLFRXCTWWV"}
Returns: -540

#8-17 are pure random, no coverings or small accidental ones

18)
{"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX",
"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
{"A","B","C","D"}
Returns: -1000

min test

19)
{"DTUXVYLIMKTRIRTJTCPVOKJGSXMAVUROFIBGAPGANQJDIIOGDK","ZEFVHVAHEBWRZGBMIOFURRNLLNPYOIHXMUASTJUXIRGDEYUIUF","YGUPTWSPQIRPXGLCUIBYCJEOEVKKJKNHGSAWMMKVNTUWCGROUZ","MEJWAMMHDHGVNCARRKYNBZCCBRFSDOEYFMRVPRUVQHMIJIRIRG","MNUVMUEEAORXYQUXMXVWHEGUDKRFKYUWRFAZOEVDGHLVXENPZH","EFRKNGIOLMHVYXVYJOKJFARIPBLTBPWATJAYXQEMMNYQSDHGTS","ZFPNUGTFQESNULZVCBBEBRSHWETFICINAFRJQYWYQUGBCJCLSO","TAEPSPOMGBIWOLVZFMJBESWXUDAFSRHMLJYHAXODLIYKSCXWTN","EYLDVWSRTHZZZVKPFPAZVIYEEKDYVGGVUSBHPBYGESPTHYAWUY","TYMSEMVVJVTEMWLKZDAJJIUPXCQHRUMRDJNZJUUDWVSDXYXIUP","AICCLDEFOBGVVAJKCUBXXTRLVRBMTPTWQMPRTXQYGMTXAIZYYX","ZXVHMPMZSHNOLPCTUDPOBCMDNANPZRWFXOIENLVJHNRMBEGGJG","GTDRPRCTZSABPGAWNFZVPGPXDEMXJZSIGYVNQEIINLSKQXSPDF","YNRQHVUAXSWKATGULW"}
{"UROF","GSXMAVUROFIBGAPGANQJDIIOGDKZEFVHVAHE","VUROFIBGAPGANQJDIIOGDKZEFVHVA","UXVYLIMKTR","OFIBGAPGANQJDIIOGDKZEFVHVAHEBWRZGBMI","KJG","UXVYLIMKTRIRT","ESN","IRTJTCPVOK","VNTUWCGROUZMEJWAMMHDHGVNCARRKYN","M","ROFIBGAPGANQJDIIOGDKZEFVHVAHEBWR","DTUXVYLIMKTRIRTJTCPVOKJGSXMAVUROFIBGAPGA","TCPVOKJGSXMAV","GAPGANQJD","PBLTBPWATJAYXQEMMNYQSDHGTSZFPNUG","GSXMAVUROFIBGAPGANQJDIIOGDKZEFVHVAHEBWRZGBMIOFURRN","XVYLIM","SXMAVUR","JTCPVOKJGSXMAVUROFIBGAPGANQ","MAVUROFIBGAPGANQ","OKJGSXMAVUROFIBGAPGAN","XMAVURO","RTJTCPVOKJGSXMAVURO","BZCCBRFSDOEYFMRVPRUVQHMIJIRIRGMNUVMUEE","TRIRTJTCPVOKJGSXMA","DMCVVAONHKJSPRTVTQGOZNLZQRNOWO","VYLIMKTRIRTJTCPVOKJGSXMAVUR","AORXYQUXMXVWHEGUDKRFKYUWRFAZOEVDGHLVXENPZHEFRK","PLZUYXQETBNUGABERFWOLREMCLZSQNBNUCGHHKLCWBLSSK","OKJGSXMAVUROFIBGAPGANQJDIIOG","AVUROFIBGAPGANQJDIIOGDKZEFV","TRIRTJTCPVOKJGSXMAVUROFIBGAPGANQJDIIOGDKZEFV","VYLIMKTR","JCZWHFLXHFFDXCYUZVDXOCTTQAZIFVGJIQGQSJ","IMKTRIRTJTCPVOKJGSXMAVUROFIBGAPGANQJDIIOGDKZ","FIBGAPGANQJDIIOGDK","TFQ","PVOKJGSXMAVUROFIBGAPGANQJDIIOGDKZ","KXYRHLHXQJXEWDMMVMXUMISWEAJVJPUYJHHWFEEXZETN","CPVOKJGSXMAVUROFIBGA","LIMKTRIRTJTCPVOKJGSXMAVUROFIBG","RQBWICBPDZEBTJOAZUJUSYOKKEPRECZUXCDXWTCSWQJXAA","XVYLIMKTRIRTJTCPVOKJGSXMAV","IRTJTCPVOKJGSXMAVUR","CPVOKJGSXMAVUROFIBGAPGA","DTUXVYLIMKTRIRTJTCPVOKJGSXM","NGIOLMHVYXVYJOKJFARI","DTUXVYLI"}
Returns: 29522

#19-68 are covering+random substrings+random handles

Submissions are judged against all 130 archived test cases, of which 10 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HandlesSpelling with a public method int spellIt(vector<string> parts, vector<string> badges) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous