DMOPC '14 Contest 4 P4 - Sketchley Park

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 0.9s
Memory limit: 128M
Author:
Xyene
Problem types

At Sketchley Park, you're part of the effort to break enemy communications encrypted with the Paradox machine. Breaking the encryption would shorten the war by 5 years and save millions of lives.

Thankfully, Intelligence has managed to obtain a functional Paradox machine for you to reverse engineer. You've discovered that the machine operates only with uppercase alphabetical characters, encrypting and decrypting based off a letter map cipher. Every letter is mapped to a different letter in the alphabet, i.e. not necessarily shifted by a constant value.

Through arduous manual labour, you've isolated N (1 \le N \le 500\,000) possible letter mappings, and you'd like to find which one correctly decrypts an enemy message. You also know that the enemy is very zealous, such that many decrypted messages contain the substring HAILHYDRA in them, not necessarily at the end.

To illustrate, with the letter map HALOVJEGBRMCZFSUYQKIDNTXWP,

  • HELLOWORLDANDHAILHYDRA → GVCCSTSQCOHFOGHBCGWOQH
  • NICEWEATHERHAILHYDRA → FBLVTVHIGVQGHBCGWOQH
  • HAILHYDRAHAIL → GHBCGWOQHGHBC

Given an encrypted message and a set of N possible keys, identify the correct letter map and print the decrypted message. You can assume a letter map is correct if the decrypted message contains HAILHYDRA. It is also possible, however, that the message itself contains no HAILHYDRA, in which case we're out of luck. If no letter map is found, print KeyNotFoundError.

Input Specification

The first line will contain the encrypted message (no longer than 100\,000 characters long). The second line will contain the single integer N, and the following N lines will each contain a possible decryption key (each 26 characters long).

It is guaranteed that the input is randomly generated. If there is a valid key, the string HAILHYDRA (after encryption) will be inserted into the random string at a random position.

Output Specification

The decrypted message, on one line. If multiple input keys are valid, use the first key in the order of input.

Sample Input 1

GVCCSTSQCOHFOGHBCGWOQH
5
ZTKJFCMLBGVPORSIEUQYHDANXW
QURVLGJKWAYHBONPSXFETMIDZC
IANUJTHMVXBLCDGQZKFYOWPSER
UWBPCEKGFZLMJDYSOAQHRIXVNT
HALOVJEGBRMCZFSUYQKIDNTXWP

Sample Output 1

HELLOWORLDANDHAILHYDRA

Explanation for Sample Output 1

GVCCSTSQCOHFOGHBCGWOQH decrypted with the 5th key in the input, HALOVJEGBRMCZFSUYQKIDNTXWP, results in HELLOWORLDANDHAILHYDRA. Since the substring HAILHYDRA is recognizable, we can assume we have found the correct key.

Sample Input 2

GVCCSTSQCOHFOGHBCGWOQH
5
ZTKJFCMLBGVPORSIEUQYHDANXW
IANUJTHMVXBLCDGQZKFYOWPSER
VMOAZUIFNELRCPJGKSBTDHWXYQ
UWBPCEKGFZLMJDYSOAQHRIXVNT
HNXKGSLBEZCYMTUDVPIOFWAJQR

Sample Output 2

KeyNotFoundError

Explanation for Sample Output 2

None of the 5 keys produce a decrypted string containing HAILHYDRA, so the correct key is not present.

Everything appearing in this problem is fictitious. Any resemblance to real locations, countries, organizations (?), or machines is not coincidental.

Comments


  • 3
    aeternalis1  commented on July 16, 2017, 3:52 p.m. ← edited

    Is it safe to assume that the substring 'HAILHYDRA' appears only once in the original?

    EDIT: Nvm apparently it can appear multiple times


    • -2
      pblpbl  commented on Aug. 18, 2020, 3:59 p.m.

      Looking at the statement, there is a small chance that HAILHYDRA can appear more than once when a random sequence of characters somehow formed the encrypted string of HAILHYDRA from a random key (most of the time, there are 0 or 1 sequences that actually decrypt to HAILHYDRA as given by the problem statement)


  • 0
    pyrexshorts  commented on Feb. 11, 2015, 1:59 a.m.

    Do I need to use other methods besides simple concatenation and a find function?


    • 0
      FatalEagle  commented on Feb. 11, 2015, 2:23 a.m.

      Yes. There are much better solutions.


      • 0
        pyrexshorts  commented on Feb. 11, 2015, 2:45 a.m.

        What kind of solutions exist? Can suffix trees be used? I have no idea where to even start.


        • 1
          FatalEagle  commented on Feb. 11, 2015, 3:02 a.m.

          Yes, you can use them. But given that this is a 12-point problem, it's way too much overkill.

          You can notice that the test data is randomly generated and go from there.