Editorial for UTS Open '15 #2 - Secret Code

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.

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:

  1. 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.
  2. Assign to that letter the possibility which is not taken.
  3. Go to step 1.
  4. Check the conditions mentioned above and answer YES if 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.)

Complexity: \mathcal{O}(NA^2)


There are no comments at the moment.