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();
}