The analysis uses the notation x \bmod y, which means the remainder of dividing the number by . For example, 7 \bmod 3 = 1.
If we number the letters in the alphabet from to (i.e., '', '', , '') and create a new array , where b_i corresponds to the number of the letter s_i, then the addition described in the condition is (b_i+a_i)\bmod 26. Now our task is to make the array (b_i+a_i)\bmod 26 lexicographically minimal for a certain permutation .
It can be noticed that (b_i+a_i)\bmod 26=(b_i+(a_i\bmod 26)) \bmod 26. This means that each a_i can be replaced by a_i \bmod 26.
Let's create a count array of the array , i.e., an array such that c_x is the number of occurrences of the number in the array . Since the sequence in which the elements of the array are placed does not matter, we will work with their quantity.
Let's choose such for b_1 that (b_1+x)\bmod 26 is minimal. After that, we will use this and remove it from the count array. We will do the same for b_2,b_3,\dots,b_n.
Thus, we always try to minimize the prefix of the array, which guarantees a lexicographically minimal array.
Problem Author: | Oleksandr Tymkovich |
Problem Prepared by: | Oleksandr Tymkovich |
Editorial by: | Oleksandr Tymkovich |