UTS Open '15 #2 - Secret Code

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

Ms. Evans's database stores a number of words consisting of the first A (2 \le A \le 26) English letters. To prevent technicians from seeing sensitive information, the words are encrypted in a very simple way: each English letter is mapped to exactly one English letter, such that no two letters map to the same letter. A letter can map to itself. To encrypt a word, each letter of the word is replaced with the letter it maps to.

For example, if A=3, the following mappings are valid:

  • \{A \to C, B \to A, C \to B\}
  • \{A \to A, B \to B, C \to C\}
  • \{A \to C, B \to B, C \to A\}

The following mappings are not valid:

  • \{A \to B, B \to A, C \to A\}
  • \{A \to A, B \to D, C \to C\}

Picture of lock

One of the hard drives failed yesterday, and some information about the mapping has been lost. Specifically, for the i^\text{th} letter, it is known that it mapped to either a_i or b_i (a_i and b_i are among the first A English letters; a_i \ne b_i).

Ms. Evans has a list of N (1 \le N \le 100) questions. Question i asks: given what we know about the mapping, is it possible that X_i could map to Y_i? X_i and Y_i are strings of equal length composed of the first A lowercase English characters. No string will exceed 100 characters in length.

It is guaranteed that the input corresponds to at least one valid mapping.

Input Specification

The first line contains A. The i^\text{th} of the next A lines contains a_i and b_i. The next line contains N. The i^\text{th} of the next N lines contains X_i and Y_i.

Output Specification

For each question, output a single line containing the answer: either YES or NO.

Sample Input 1

a b
a b
aa bb
aa ab
ba aa
ab ba

Sample Output 1


Sample Input 2

b d
a c
a b
c b
a b
b b
abcd dabc

Sample Output 2



  • 3
    pyrexshorts  commented on Feb. 11, 2015, 10:50 p.m.

    Can someone explain the second test case? Why can't a be mapped to b if a can be mapped to b and d?

    • 0
      r3mark  commented on Dec. 28, 2015, 10:56 a.m.

      If 'a' were to be mapped to 'b', then 'c' must be mapped to 'a' and 'd' must be mapped to 'c' (by elimination). This means that 'b' must be mapped to 'd' (since every letter must be mapped by exactly one letter), but this isn't possible since 'b' can only be mapped to 'a' or 'c'. So 'a' cannot be mapped to 'b'.

    • 0
      d  commented on Dec. 28, 2015, 10:30 a.m.

      In all the valid mappings, a maps to d.

  • 2
    nullptr  commented on Feb. 11, 2015, 4:50 p.m.

    We have updated the statement with examples of valid and invalid mappings in an attempt to make the question clearer.

  • 3
    Butane  commented on Feb. 11, 2015, 4:48 p.m.

    Why cant 'a' be mapped to 'b'? In the input it says the 2 possibilities for 'a' are 'b' and 'd'.

  • 4
    awaykened  commented on Feb. 11, 2015, 4:43 p.m.

    I am thoroughly confused x.x

    • 1
      bobhob314  commented on Feb. 11, 2015, 4:50 p.m.

      To the problem writers: If this is your first contest, I feel you. It definitely is tough making the first one when schools like DM have been doing this for a year. Keep it up!


      • 3
        omaewamoushindeiru  commented on Feb. 11, 2015, 7:57 p.m.

        hob, you realize that nullptr went to the IOI...

        • -1
          bobhob314  commented on Feb. 11, 2015, 8:40 p.m.

          BuMP how do you know this shizbiz

        • 2
          kobortor  commented on Feb. 11, 2015, 8:16 p.m.

          Bruh going to IOI doesn't require you to write questions.

      • 8
        nullptr  commented on Feb. 11, 2015, 4:52 p.m.

        Thank you very much for your kind, understanding words.

        • 2
          awaykened  commented on Feb. 11, 2015, 8:53 p.m. edited


        • 0
          bobhob314  commented on Feb. 11, 2015, 8:39 p.m.

          Can't tell if that was sarcasm or just being a decent human being... x) (^o^ )/

          Either way, no problem!