Editorial for UTS Open '15 #2 - Secret Code
Submitting an official solution before solving the problem yourself is a bannable offence.
To decide whether the string ~A~ could map to ~B~, we first have to realize what this is telling us: for each valid ~i~, ~A_i~ maps to ~B_i~. We can immediately answer
NO if any of the following conditions is satisfied:
- Two letters map to the same letter.
- The same letter maps to two different letters.
- A letter maps to a letter other than one of the two possibilities specified in the input.
However, as the second sample case shows, this is not sufficient to determine if the mapping is valid. The following algorithm works:
- Find a letter which has not yet been assigned, but for which one of the two possibilities for that letter is taken. If there is no such letter, go to step 4.
- Assign to that letter the possibility which is not taken.
- Go to step 1.
- Check the conditions mentioned above and answer
YESif none of them are satisfied.
The proof of correctness is left as an exercise to the reader. (That is, I have no proof, but it gets the same answer as my bipartite matching solution for every test case I can create.)