## 12025 - Wrong Keys

Moderator: Board moderators

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

### 12025 - Wrong Keys

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

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!