Editorial for DMOPC '14 Contest 4 P4 - Sketchley Park
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
By Eduard Ionescu
The key part to this problem is in finding an efficient method of validating keys. The first step is to get all nine-letter substrings of the encrypted line that could be HAILHYDRA. You can determine this by seeing whether the first letter is the same as the fifth letter, that the second letter is the same as the last letter, and that all the other letters only appear once.
For each of the given key-mappings, check if one of the nine-letter strings decrypts to HAILHYDRA. If so, then decrypt the input. If none of the mappings yield a HAILHYDRA, output KeyNotFoundError. If your submissions continue to exceed the time limit, consider looking at the Tips page.
The expected time on random data is .
Comments