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

Додай і мінімізуй (Розбір)

В розборі використовується нотація 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.

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

Автор задачі:

Олександр Тимкович

Задачу підготував:

Олександр Тимкович

Розбір написав:

Олександр Тимкович