Циклічні зсуви#13060

Циклічні зсуви (Розбір)

Автор задачі:	Andrii Kholod (Connect)
Підготував:	Andrii Kholod (Connect)
Розбір:	Andrii Kholod (Connect)

Розв'язання

Припустимо, що ми зсунули перестановку $a$ на $x$ позицій, а перестановку $b$ на $y$ позицій.

Немає сенсу зсувати будь-яку перестановку хоча б $n$ разів, оскільки після $n$ циклічних зсувів вона повернеться у початковий стан. Тому достатньо розглядати $0 \leq x, y < n$ 0 \le x,y<n.

Зафіксуємо відносний зсув

$r = (y - x + n) mod n .$ r=(y-x+n)\bmod n.

Для фіксованого $r$ розглянемо циклічну послідовність

$d_{i} = a_{i} - b_{(i + r) mod n} .$ d_i=a_i-b_{(i+r)\bmod n}.

Якщо зсунути $a$ на $s$ позицій, тоді $b$ потрібно зсунути на $(s + r) mod n$ (s+r)\bmod n позицій.

Отже, послідовність різниць між відповідними елементами зсунутих перестановок є циклічним зсувом послідовності $d$ , який починається з позиції $s$ .

Умова задачі вимагає, щоб для кожного префікса сума елементів $a$ була не меншою за суму елементів $b$ .

Тобто нам потрібно, щоб усі префіксні суми відповідного циклічного зсуву $d$ були невід'ємними.

Оскільки $a$ та $b$ є перестановками однакових чисел,

$\sum_{i = 1}^{n} d_{i} = 0.$ \sum_{i=1}^{n} d_i=0.

Нехай

$P_{0} = 0,$ P_0=0,

а для $1 \leq k \leq n$ 1\le k\le n визначимо

$P_{k} = d_{1} + d_{2} + \dots + d_{k} .$ P_k=d_1+d_2+\ldots+d_k.

Доведемо, що циклічна послідовність, яка починається з позиції $s + 1$ s+1, є коректною тоді й лише тоді, коли $P_{s}$ P_s є мінімальним серед

$P_{0}, P_{1}, \dots, P_{n - 1} .$ P_0,P_1,\ldots,P_{n-1}.

Припустимо, що $P_{s}$ P_s є мінімальним.

До моменту переходу через кінець послідовності кожна префіксна сума циклічного зсуву має вигляд

$P_{j} - P_{s}$ P_j-P_s

для деякого $j > s$ j>s.

Оскільки $P_{s}$ P_s є мінімальним, маємо $P_{j} \geq P_{s}$ P_j\ge P_s, тому це значення невід'ємне.

Після того як ми пройдемо кінець послідовності та продовжимо з її початку, префіксна сума матиме вигляд

$(P_{n} - P_{s}) + P_{j} .$ (P_n-P_s)+P_j.

Але $P_{n} = 0$ P_n=0, оскільки загальна сума $d$ дорівнює нулю. Тому це значення дорівнює

$P_{j} - P_{s},$ P_j-P_s,

що також є невід'ємним.

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

Тепер припустимо, що $P_{s}$ P_s не є мінімальним.

Тоді існує деяке $j$ , для якого $P_{j} < P_{s}$ P_j<P_s. Під час циклічного проходу, починаючи з позиції $s + 1$ s+1, у певний момент ми дійдемо до цього префікса та отримаємо від'ємну суму.

Отже, така початкова позиція не може бути коректною.

Тому для кожного зафіксованого відносного зсуву $r$ нам достатньо обчислити всі префіксні суми та знайти їх мінімум.

Для кожної позиції $s$ , у якій досягається цей мінімум, кількість зсувів перестановки $a$ дорівнює

$x = s,$ x=s,

а кількість зсувів перестановки $b$ дорівнює

$y = (s + r) mod n .$ y=(s+r)\bmod n.

Отже, загальна кількість операцій дорівнює

$s + (s + r) mod n .$ s+(s+r)\bmod n.

Переберемо всі $n$ можливих значень $r$ . Для кожного з них обчислимо префіксні суми за $O (n)$ та перевіримо всі позиції, у яких досягається мінімум.

Часова складність розв'язання — $O (n^{2})$ O(n^2).

Просторова складність — $O (n)$ .

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'

const ll clasik = 5005;

ll a[clasik] , b[clasik] , pref[clasik];

signed main() {
    speed;

    ll n;

    cin>>n;

    for (int i = 1 ; i<=n ; i++) cin>>a[i];

    for (int i = 1 ; i<=n ; i++) cin>>b[i];

    ll ans = 2*n;

    for (int r = 0 ; r<n ; r++) {

        pref[0] = 0;

        for (int i = 1 ; i<n ; i++) {
            ll pos = (i+r-1)%n+1;

            pref[i] = pref[i-1] + a[i] - b[pos];
        }

        ll mn = pref[0];

        for (int i = 1 ; i<n ; i++) {
            mn = min(mn , pref[i]);
        }

        for (int s = 0 ; s<n ; s++) {
            if (pref[s] != mn) continue;

            ll x = s;
            ll y = (s+r)%n;

            ans = min(ans , x+y);
        }
    }

    cout<<ans<<endl;

    return 0;
}

C++