ROTIT-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: yaswanth phani kommineni
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

3081

PREREQUISITES:

Z-function, RMQ data structures

PROBLEM:

Given two arrays A and B of length N each.

You can do the following operation on the array B exactly once:

  • Chose two integers R (1 \le R \le N) and K(K \ge 0) and apply K right-rotations to the subarray [1,R].
    Applying a right-rotation to the array C = [C_1, C_2, C_3, \ldots, C_M] changes it to [C_M, C_1, C_2, \ldots, C_{(M-1)}]

Find whether you can transform the array B into the array A by applying the mentioned operation exactly once. If it is possible, find the minimum value of K for which it is possible.

EXPLANATION:

Z-function

Suppose we are given an array a of length n. The Z-function for this array is an array of length n where the i^{th} element is equal to the greatest number of elements starting from the position i that coincide with the first elements of a.

In other words, z[i] is the length of the longest array that is, at the same time, a prefix of a and a prefix of the suffix of a starting at i.

If arrays A and B are same then minimum value of K is 0. From now on we assume that A and B are not same. Iterate on the array A from i=2\: to\: N. If the minimum number of right-rotations, of any prefix of B, needed to make A and B same is (i-1) then there must be a subarray of B which is same as the prefix of A of length (i-1) with some restrictions on the starting point of such a subarray.
Let l and r be the left limit and right limit respectively for the starting point of such a subarray and let SameFromEnd be the smallest index such that for all indices i\geq SameFromEnd, A_i=B_i and len be the length of largest prefix of B which is same as the subarray of A of same length starting at index i.

Calculation of len for all indices of array A

The values of len for indices i are calculated in O(N) time by applying Z-function on the array (B+(-1)+A) where '+' represents concatenation of the arrays.
Let zba be the array obtained after applying the Z-function on the array (B+(-1)+A)
then value of len for index i is zba_{n+1+i} .

Then l = max(SameFromEnd - i+1, 2), r = len+1;

Left limit

The left limit is equal to max(SameFromEnd - i+1, 2) because if we select a subarray which starts with an index smaller than this limit, the prefix of length (i-1) will be same but the suffix starting from index i of array A and B will not be the same as A[SameFromEnd-1]!=B[SameFromEnd-1](from the definition of the variable SameFromEnd)

Right limit

The right limit is equal to len+1 because if we select a subarray which starts with an index greater than this limit, the prefix of length (i-1) will be same but the suffix starting from index i of array A and B will not be the same as A[i+len]!=B[len+1](from the definition of Z-function)

Now we just need to check effectively whether there is a subarray of B which is same as the prefix of A of length (i-1). Let zab be the array obtained after applying the Z-function on the array (A+{-1}+B) where '+' represents concatenation of the arrays. If the maximum value of the zab_i in the range [n + 1 + l,n+1+r] is greater than or equal to (i-1) then we have found a subarray and we can output i-1 as the minimum value of K.
For range query one can use any RMQ data-structure, modified to return maximum value in the range, like segment tree, sparse table etc.

For details of implementation please refer to the attached solutions.

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mpa make_pair
#define endl '\n'

vector <int> z(vector <int> s){
        ll n = s.size();
        vector <int> z(n,0);
        int l = 0,r = 0;
        for(int i=1;i<n;i++){
                if(i>r){
                        l = i;r = i-1;
                        while(r+1<n && s[r+1] == s[r-l+1]) r++;
                        z[i] = r-l+1;
                }
                else{
                        if(z[i-l]+i-1 >= r){
                                l = i;
                                while(r+1<n && s[r+1] == s[r-l+1]) r++;
                                z[i] = r-l+1;
                        }
                        else z[i] = z[i-l];
                }
        }
        return z;
}

class maxSegmentTree{
        // author : yaswanth phani kommineni
        public :
                vector <int> st;
                ll n;
                maxSegmentTree(vector <int> v){
                        n = ((int)1<<((int)ceil(log2(v.size()))));
                        st.assign(2*n,-1e9-1);
                        for(ll i=0;i<(int)v.size();i++){
                                st[n+i] = v[i];
                        }
                        build(1);
                }
                // not for use ( instantiated automatically)
                void build(int u){
                        if(u<n){
                                build(2*u);
                                build(2*u+1);
                                st[u] = max(st[2*u],st[2*u+1]);
                        }
                }
                // changes value at l(0 indexed) to val
                void update(int l, int val){
                        l+=n;
                        st[l] = val;
                        l>>=1;
                        while(l){
                                st[l] = max(st[2*l],st[2*l+1]);
                                l>>=1;
                        }
                }
                // 0 indexed
                ll query(int l,int r){
                        l+=n;
                        r+=n;
                        int res = -1e9-1;
                        while(l<=r){
                                if(l&1) res = max(res,st[l++]);
                                if(!(r&1)) res = max(res,st[r--]);
                                l>>=1;
                                r>>=1;
                        }
                        return res; 
                }
};

void solve(){
        int n;
        cin >> n;
        vector <int> a(n), b(n);
        for(int i=0;i<n;i++){
                cin >> b[i];
        }
        for(int i=0;i<n;i++){
                cin >> a[i];
        }
        vector <int> tempa, tempb;
        for(int i=0;i<n;i++){
                tempa.push_back(a[i]);
        }
        tempa.push_back(-1);
        for(int i=0;i<n;i++){
                tempa.push_back(b[i]);
        }
        for(int i=0;i<n;i++){
                tempb.push_back(b[i]);
        }
        tempb.push_back(-1);
        for(int i=0;i<n;i++){
                tempb.push_back(a[i]);
        }
        tempa = z(tempa);
        tempb = z(tempb);
        vector <int> za, zb;
        for(int i=n+1;i<=2*n;i++){
                zb.push_back(tempa[i]);
        }
        for(int i=n+1;i<=2*n;i++){
                za.push_back(tempb[i]);
        }
        int k = n;
        for(int i=n-1;i>=0;i--){
                if(a[i] == b[i]){
                        k = i;
                        continue;
                }
                break;
        }
        k++;
        maxSegmentTree st(za);
        for(int i=1;i<=n;i++){
                int l = max(2, k-(i-1));
                int r = zb[i-1]+1;
                if(l<=r){
                        if(st.query(l-1,r-1) >= i-1){
                                cout << i-1 << endl;
                                return;
                        }
                }
        }
        cout << -1 << endl;
}
 
int main(){
#ifndef ONLINE_JUDGE
        //freopen("input6.in","r",stdin);
        //freopen("input6.out","w",stdout);
#endif
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int tc;
        tc = 1;
        cin >> tc;      
        for(int i=1;i<=tc;i++){
                //cout << "Case #" << i << ": ";
                solve();
        }
        return 0;
}
Tester-1's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
void zfn(I s[],I z[],I n) {
  asc(i,0,n){
    z[i]=0;
  }
  I l=0;
  I r=0;
  z[0]=n;
  asc(i,1,n){
    if(i<=r){
      z[i]=min(r-i+1,z[i-l]);
    }
    while(i+z[i]<n && s[z[i]]==s[i+z[i]]){
      z[i]++;
    }
    if(i+z[i]-1>r){
      l=i;
      r=i+z[i]-1;
    }
  }
}
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  I t;
  t=readInt(1,200000,'\n');
  I ns=0;
  while(t--){
    I ans=INT_MAX;
    I n,k;
    n=readInt(1,200000,'\n');
    ns+=n;
    assert(ns<=200000);
    I a[n],b[n];
    asc(i,0,n){
      if(i!=n-1){
        a[i]=readInt(1,1000000000,' ');
      }else{
        a[i]=readInt(1,1000000000,'\n');
      }
    }
    asc(i,0,n){
      if(i!=n-1){
        b[i]=readInt(1,1000000000,' ');
      }else{
        b[i]=readInt(1,1000000000,'\n');
      }
    }
    I x=0;
    dsc(i,0,n){
      if(a[i]!=b[i]){
        x=i+1;
        break;
      }
    }
    I temp[2*n+1];
    I c[2*n+1];
    asc(i,0,n){
      c[i]=a[i];
      c[i+n+1]=b[i];
    }
    c[n]=0;
    zfn(c,temp,2*n+1);
    I za[n];
    asc(i,0,n){
      za[i]=temp[i+n+1];
    }
    asc(i,0,n){
      c[i]=b[i];
      c[i+n+1]=a[i];
    }
    c[n]=0;
    zfn(c,temp,2*n+1);
    I zb[n];
    asc(i,0,n){
      zb[i]=temp[i+n+1];
    }
    V(P(I,I)) qr;
    asc(i,0,n){
      qr.pb({max(0ll,x-i),i});
    }
    sort(all(qr));
    I pt=0;
    OS(P(I,I)) s;
    I dp[n];
    memset(dp,-1,sizeof(dp));
    asc(i,0,n){
      if(pt==n){
        break;
      }
      while(pt!=n && qr[pt].fi==i){
        s.insert({qr[pt].se,qr[pt].fi});
        pt++;
      }
      while(1){
        A it=s.begin();
        if(it==s.end() || (*it).fi>zb[i]){
          break;
        }
        dp[(*it).fi]=i;
        s.erase(it);
      }
    }
    if(x==0){
      ans=0;
    }
    asc(i,0,n){
      if(dp[i]!=-1 && dp[i]<=za[i]){
        ans=min(ans,dp[i]);
      }
    }
    if(ans==INT_MAX){
      ans=-1;
    }
    cout<<ans<<"\n";
  }
  return 0;
}
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
 
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;

using ii = pair<ll,ll>;

vector<int> zfun(vector<int> &a){
    int n = a.size();
    vector<int> z(n,0);
    z[0] = 0;
    for(int i=1, l=0, r=0; i<n; i++){
        if(i<=r) z[i] = min(r-i+1, z[i-l]);
        while(i+z[i]<n && a[z[i]]==a[i+z[i]]) ++z[i];
        if(i+z[i]-1>r){
            l = i;
            r = i+z[i]-1;
        }
    }
    return z;
}

void solve(){
    int n = readIntLn(1,2e5);
    sum_n+=n;
    vector<int> a(n), b(n);

    rep(i,n){
        if(i<n-1) a[i] = readIntSp(1,1e9);
        else a[i] = readIntLn(1,1e9);
    }
    rep(i,n){
        if(i<n-1) b[i] = readIntSp(1,1e9);
        else b[i] = readIntLn(1,1e9);
    }

    if(a==b){
        cout<<0<<'\n';
        return;
    }

    int c = 0;
    rev(i,n-1){
        if(a[i]!=b[i]) break;
        c++;
    }
    
    vector<int> tmp = a;
    tmp.pb(0);

    rep(i,n) tmp.pb(b[i]);

    vector<int> zab = zfun(tmp);

    tmp.clear();
    tmp = b;
    tmp.pb(0);
    rep(i,n) tmp.pb(a[i]);

    vector<int> zba = zfun(tmp);

    vector<vector<pair<int,int> > > qr(2*n+1);

    rep_a(i,n+1, 2*n+1){
        if(i+zab[i]-1+c>=2*n && zab[i]>0){
            qr[max(n+1, 3*n+2-c-i)].pb(mp(i-n-1, n+2+zab[i]));
            //cout<<i<<" "<<max(n+1, 3*n+2-c-i)<<" "<<i-n-1<<" "<<n+2+zab[i]<<" "<<zab[i]<<endl;
        }
    }



    int ans = n+1;
    priority_queue<pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > p;

    rep_a(i,n+1,2*n+1){
        while(!p.empty() && p.top().ss<=i) p.pop();
        for(auto h:qr[i]) p.push(h);

        if(p.empty()) continue;

        if(zba[i]>=p.top().ff){
            ans = i-n-1;
            break;
        }
    }

    if(ans>n) ans = -1;
    cout<<ans<<'\n';

}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,2e5);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_n<=2e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
    // cerr<<"Maximum length : " << max_n <<'\n';
    // // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';

    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e6 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int t[N];
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = a[tl];
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(a, v * 2, tl, tm);
        build(a, v * 2 + 1, tm + 1, tr);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}
int mx(int v, int tl, int tr, int l, int r)
{
    if (l > r)
        return 0;
    if (l == tl && r == tr)
    {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return max(mx(v * 2, tl, tm, l, min(r, tm)), mx(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
vector<int> z_function(vector<int> s)
{
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
void sol(void)
{
    int n, samefromend;
    cin >> n;
    int a[n], b[n],arr[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    samefromend = n;
    for (int i = n - 1; i >= 0; i--)
    {
        if (a[i] == b[i])
            samefromend = i;
        else
            break;
    }
    vector<int> ab(2 * n + 1), ba(2 * n + 1);
    for (int i = 0; i < n; i++)
        ab[i] = a[i], ba[i] = b[i];
    ab[n] = ba[n] = -1;
    for (int i = n + 1; i <= 2 * n; i++)
        ab[i] = b[i - n - 1], ba[i] = a[i - n - 1];
    vector<int> zab = z_function(ab), zba = z_function(ba);
    if (zba[n + 1] == n)
    {
        cout << 0 << '\n';
        return;
    }
    for (int i = 0; i < n; i++)
        arr[i] = zab[n + 1 + i];
    build(arr, 1, 0, n - 1);
    for (int i = 1; i < n; i++)
    {
        int l = max(samefromend - i, 1),r = zba[n + 1 + i];
        if (mx(1, 0, n - 1, l, r) >= i)
        {
            cout << i << '\n';
            return;
        }
    }
    cout << -1 << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}