## UTS Open '15 #2 - Secret Code

View as PDF

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

Authors:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Ms. Evans's database stores a number of words consisting of the first () 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 , the following mappings are valid:

The following mappings are not valid:

One of the hard drives failed yesterday, and some information about the mapping has been lost. Specifically, for the letter, it is known that it mapped to either or ( and are among the first English letters; ).

Ms. Evans has a list of () questions. Question asks: given what we know about the mapping, is it possible that could map to ? and are strings of equal length composed of the first lower-case English characters. No string will exceed characters in length.

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

#### Input Format

The first line contains . The of the next lines contains and . The next line contains . The of the next lines contains and .

#### Output Format

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

#### Sample Input 1

2
a b
a b
4
aa bb
aa ab
ba aa
ab ba

#### Sample Output 1

YES
NO
NO
YES

#### Sample Input 2

4
b d
a c
a b
c b
3
a b
b b
abcd dabc

#### Sample Output 2

NO
NO
YES

• 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?

• 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'.

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

In all the valid mappings, a maps to d.

• 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.

• 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'.

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

Amen

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

I am thoroughly confused x.x

• 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!

hob

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

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

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

BuMP how do you know this shizbiz

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

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

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

Thank you very much for your kind, understanding words.

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

o

• 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!

hob