Зсув сиру#13002

Зсув сиру (Розбір)

Поділимо ряд на голову — перші шматочків — і хвіст. Позначимо через кількість невпорядкованих пар усередині голови, через — усередині хвоста, а через — кількість пар «елемент голови більший за елемент хвоста». Тоді

a = i + j + c.

Після зсуву голова й хвіст міняються місцями, внутрішні пари не змінюються, а перехресні перевертаються всі одразу:

b = i + j + \left(k(n-k) - c\right).

Віднімаючи, отримуємо a - b = 2c - k(n-k), тобто

c = \frac{a - b + k(n-k)}{2}

— число, визначене однозначно. Якщо воно не ціле, від'ємне або більше за k(n-k), відповідь .

Далі все розпадається на добуток трьох незалежних величин:

Складність: O\!\left(n^2 + k \cdot k(n-k)\right), з великим запасом у межах обмежень.

Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.