В розборі використовується нотація x \bmod y, що означає залишок від ділення числа на . Наприклад 7 \bmod 3 = 1.
Якщо пронумерувати букви в алфавіті від до (тобто '', '', , '') та зробити новий масив , де b_i відповідає номеру букви s_i, то додавання, описане в умові, це (b_i+a_i)\bmod 26. Тепер наша задача — зробити масив (b_i+a_i)\bmod 26 лексикографічно мінімальним для певної перестановки .
Можна замітити, що (b_i+a_i)\bmod 26=(b_i+(a_i\bmod 26)) \bmod 26. Це означає, що кожне a_i можна замінити на a_i \bmod 26.
Створимо масив підрахунку масиву , тобто такий масив що c_x — це кількість входжень числа в масив . Через те, що нам не грає ролі, в якій послідовності ставити елементи масиву, ми будемо працювати з їх кількістю.
Давайте для b_1 виберемо таке , що (b_1+x)\bmod 26 мінімальне. Після цього використаємо цей та заберемо його з масиву підрахунку. Так само зробимо для b_2,b_3,\dots,b_n.
Таким чином ми завжди намагаємось мінімізувати префікс масиву, що гарантує лексикографічно мінімальний масив.
Автор задачі: | Олександр Тимкович |
Задачу підготував: | Олександр Тимкович |
Розбір написав: | Олександр Тимкович |