12025 - Wrong Keys

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12025 - Wrong Keys

Post by brianfry713 » Wed Apr 10, 2013 3:23 am

For the first book in the sample input:
Bo te or nob bo te.
Swap b and t and then it becomes:
to be or not to be
Now all words are in the dictionary.

For the second book:
Now pay parbicular abbenbion bo bhis firsb clause, tecause ib's mosb imporbanb.
Bhere's bhe parby of bhe firsb parb shall te known in bhis conbracb as bhe
parby of bhe firsb parb. How do you like bhab, bhab's prebby neab eh?
If you again swap b and t you get bo->to and te->be from the dictionary.

For the third book:
Simple case :-)
You can't get any words from the dictionary so print a b. a b is the first possible swap in lexicographic order. If there are several minimum solutions, only the first one in lexicographic order should be shown.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12025 - Wrong Keys

Post by brianfry713 » Sat Apr 13, 2013 4:32 am

My C++ code got AC in 4.260 sec. I store the dictionary into a hash, one for each word length. I then store the words of a book into another hash. I brute force over all possible swaps to determine the best one with the minimum possible number of different words that cannot be found in the dictionary.

For one test case to build the dictionary I take O(nw). Then for each book if it has n words in it I take O(n) to build that hashtable. Then I compare all 26 choose 2 = 325 = n_swaps, and each comparison takes O(n) to see if each word in the book is in the dictionary after the letters are swapped, for a total of O(nw + nb * n_swaps * n) per test case.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 120 (12000-12099)”