Editorial for SAC '22 Code Challenge 3 Junior P5 - Normal Encoding


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.

Author: maxcruickshanks

Subtask 1

It suffices to output the binary character pairing |M| times.

Time Complexity: \mathcal{O}(|M|)

Subtask 2

First, reverse the message and each binary string to allow for in-time backtracking.

Then, realize a DP state: DP[i][j]: the minimum number of binary strings to get to the i-th character of the message with the j-th binary string as the last message.

Now, verify that you can use each binary string for each index (i.e., the binary string and message match) and maintain the DP state.

Finally, start backtracking for the minimum length and lexicographically least message and output it.

Time Complexity: \mathcal{O}(|M| \sum_{i=1}^N |N_i|)

\sum_{i=1}^N |N_i| denotes the sum of the length of all the binary strings.

Note that there are faster solutions.


Comments

There are no comments at the moment.