Editorial for COCI '16 Contest 2 #2 Tavan

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.

For $60\%$ ~60\%~ of points, the ink is spilled over only one letter, so it is sufficient to alphabetically sort the letters that could replace it and use the $X^\text{th}$ ~X^\text{th}~ one. This is a good example of a task where a simple approach can get you a large number of points.

There are multiple solutions where it is possible to obtain all points. One of them is to convert the number $X-1$ ~X-1~ to a number in a numerical system where the base is $K$ ~K~. For easier implementation, we pad the number with leading zeros so that the total number of digits is $M$ ~M~. Let the digits of the new number be $a_1, a_2, \dots, a_M$ ~a_1, a_2, \dots, a_M~, respectively. Then the $i^\text{th}$ ~i^\text{th}~ unknown letter must be replaced by the $a_i^\text{th}$ ~a_i^\text{th}~ letter from the sorted order of letters that could potentially replace the $i^\text{th}$ ~i^\text{th}~ letter (the letters in the sorted order are 0-indexed).

The time complexity of this solution is $\mathcal O(MK \log K)$ ~\mathcal O(MK \log K)~.

Comments

There are no comments at the moment.