Editorial for CCC '24 J4 - Troublesome Keys
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 , 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