Editorial for CCC '24 J4 - Troublesome Keys


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.

It can take some time to wrap your head around the behaviour of Alex's strange keyboard. To help us discuss it here, we will refer to the following five values.

pressed – the first line of input representing the keys pressed by Alex

displayed – the second line of input representing the letters displayed on the screen

silly – the letter corresponding to the silly key

wrong – the letter displayed when the silly key is pressed

quiet – the letter corresponding to the quiet key

For the first subtask, the quiet key is not pressed which means that the letter in pressed that is not in displayed must be silly. Also, wrong must be the letter that is in displayed but not in pressed. Finding a character that appears in one string but not the other can be done with a loop and search. The search can be accomplished with a built-in function or nested second loop. (In general, we can check whether or not the quiet key is pressed by comparing the lengths of pressed and displayed.)

For the other subtasks, we can still begin by determining wrong as above. Similarly, we can determine a pair of letters x and y that correspond to silly and quiet, but we need to work a bit harder to determine whether x corresponds to silly and y corresponds to quiet, or the other way around. For the second subtask, we can use the fact that the first troublesome key pressed is the silly key. Otherwise, one way to do this is to simulate Alex's keyboard by replacing all occurrences of x in pressed with wrong and removing y from pressed. It the result equals displayed then we know that x corresponds to silly and y corresponds to quiet. Otherwise, we know that it is the other way around. To solve the final subtask where a large number of keys are pressed, the number of times we pass over the input strings cannot depend on N, the bound on their lengths. This can be achieved by storing the letters in pressed and displayed in a data structure that allows for efficient searches (e.g. a dictionary in Python or HashMap in Java.)

This problem can also be solved without predetermining wrong and candidates for silly and quiet. We can scan pressed and displayed left to right looking for the first place where they differ. For the second subtask, we then immediately know that silly must be the mismatched character in pressed and wrong must be the mismatched character in displayed. To determine quiet (if it was pressed), we can continue scanning until we find a mismatch that does not involve silly. We omit the details here, but for the third and fourth subtasks, we can extend this approach by considering cases and simulating the behaviour of Alex's keyboard once we determine silly or quiet.


Comments

There are no comments at the moment.