Cyclic Shifts (Editorial)

Solution

Suppose that we shift permutation $a$ by $x$ positions and permutation $b$ by $y$ positions.

There is no reason to shift any permutation at least $n$ times, because after $n$ cyclic shifts it returns to its initial state. Therefore, it is enough to consider 0 \le x,y<n.

Let us fix the relative shift

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

For this fixed $r$, consider the cyclic sequence

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

If we shift $a$ by $s$ positions, then $b$ must be shifted by (s+r)\bmod n positions.

Therefore, the sequence of differences between the corresponding elements of the shifted permutations is exactly a cyclic shift of $d$ starting from position $s$.

The required condition says that for every prefix, the sum of elements of $a$ must be at least the sum of elements of $b$.

Thus, we need every prefix sum of the corresponding cyclic shift of $d$ to be non-negative.

Since $a$ and $b$ are permutations of the same numbers,

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

Let

P_0=0,

and for 1\le k\le n define

P_k=d_1+d_2+\ldots+d_k.

We will show that starting the cyclic sequence from position s+1 is valid if and only if P_s is a minimum among

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

Suppose that P_s is minimal.

Before reaching the end of the sequence, every prefix sum of the cyclic shift has the form

P_j-P_s

for some j>s.

Since P_s is minimal, P_j\ge P_s, so this value is non-negative.

After we pass the end of the sequence and continue from its beginning, a prefix sum has the form

(P_n-P_s)+P_j.

But P_n=0, because the total sum of $d$ is zero. Therefore, this value equals

P_j-P_s,

which is also non-negative.

Hence, every position corresponding to a minimum prefix sum gives a valid cyclic shift.

Now suppose that P_s is not minimal.

Then there exists some $j$ such that P_j<P_s. While moving cyclically from position s+1, at some moment we reach this prefix and obtain a negative sum.

Therefore, such a starting position cannot be valid.

So, for every fixed relative shift $r$, we only need to calculate all prefix sums and find their minimum.

For every position $s$ where this minimum is reached, the number of shifts of $a$ is

x=s,

while the number of shifts of $b$ is

y=(s+r)\bmod n.

Thus, the total number of operations is

s+(s+r)\bmod n.

We try all $n$ possible values of $r$. For each of them, we calculate the prefix sums in $O(n)$ and check all positions where the minimum is reached.

The time complexity of the solution is O(n^2).

The memory complexity is $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;
}