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\% 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} 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 to a number in a numerical system where the base is K. For easier implementation, we pad the number with leading zeros so that the total number of digits is M. Let the digits of the new number be a_1, a_2, \dots, a_M, respectively. Then the i^\text{th} unknown letter must be replaced by the a_i^\text{th} letter from the sorted order of letters that could potentially replace the 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).


There are no comments at the moment.