Додай і мінімізуй

В розборі використовується нотація $$$x \bmod y$$$, що означає залишок від ділення числа $$$x$$$ на $$$y$$$. Наприклад $$$7 \bmod 3 = 1$$$.

Якщо пронумерувати букви в алфавіті від $$$0$$$ до $$$25$$$ (тобто '$$$a$$$'$$$=0$$$, '$$$b$$$'$$$=1$$$, $$$\dots$$$, '$$$z$$$'$$$=25$$$) та зробити новий масив $$$b$$$, де $$$b_i$$$ відповідає номеру букви $$$s_i$$$, то додавання, описане в умові, це $$$(b_i+a_i)\bmod 26$$$. Тепер наша задача — зробити масив $$$(b_i+a_i)\bmod 26$$$ лексикографічно мінімальним для певної перестановки $$$a$$$.

Можна замітити, що $$$(b_i+a_i)\bmod 26=(b_i+(a_i\bmod 26)) \bmod 26$$$. Це означає, що кожне $$$a_i$$$ можна замінити на $$$a_i \bmod 26$$$.

Створимо масив підрахунку масиву $$$a$$$, тобто такий масив $$$c$$$ що $$$c_x$$$ — це кількість входжень числа $$$x$$$ в масив $$$a$$$. Через те, що нам не грає ролі, в якій послідовності ставити елементи масиву, ми будемо працювати з їх кількістю.

Давайте для $$$b_1$$$ виберемо таке $$$x$$$, що $$$(b_1+x)\bmod 26$$$ мінімальне. Після цього використаємо цей $$$x$$$ та заберемо його з масиву підрахунку. Так само зробимо для $$$b_2,b_3,\dots,b_n$$$.

Таким чином ми завжди намагаємось мінімізувати префікс масиву, що гарантує лексикографічно мінімальний масив.

Автор задачі: | Олександр Тимкович
Задачу підготував: | Олександр Тимкович
Розбір написав: | Олександр Тимкович