Walter White Easy
Problem Statement
Walter white is considered very intelligent person. He has a problem to solve. As he is suffering from cancer, can you help him solve it?
Given two integer arrays C and S of length c and s respectively. Index i of array S can be considered good if a subarray of length c can be formed starting from index i which is complimentary to array C.
Two arrays A, B of same length are considered complimentary if any cyclic permutation of A satisfies the property (A[i]- A[i-1]=B[i]-B[i-1]) for all i from 2 to length of A (1 indexing).
Calculate number of good positions in S .
Cyclic Permutation
1 2 3 4 has 4 cyclic permutations 2 3 4 1, 3 4 1 2, 4 1 2 3,1 2 3 4
Given two integer arrays C and S of length c and s respectively. Index i of array S can be considered good if a subarray of length c can be formed starting from index i which is complimentary to array C.
Two arrays A, B of same length are considered complimentary if any cyclic permutation of A satisfies the property (A[i]- A[i-1]=B[i]-B[i-1]) for all i from 2 to length of A (1 indexing).
Calculate number of good positions in S .
Cyclic Permutation
1 2 3 4 has 4 cyclic permutations 2 3 4 1, 3 4 1 2, 4 1 2 3,1 2 3 4
#include<bits/stdc++.h>
using namespace std;
#define pu push_back
#define fi first
#define se second
#define mp make_pair
// #define int long long
#define pii pair<int,int>
#define mm (s+e)/2
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(int i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define sz 2000015
#define qw1 freopen("input1.txt", "r", stdin); freopen("output1.txt", "w", stdout);
#define qw2 freopen("input2.txt", "r", stdin); freopen("output2.txt", "w", stdout);
#define qw3 freopen("input3.txt", "r", stdin); freopen("output3.txt", "w", stdout);
#define qw4 freopen("input4.txt", "r", stdin); freopen("output4.txt", "w", stdout);
#define qw5 freopen("input5.txt", "r", stdin); freopen("output5.txt", "w", stdout);
#define qw6 freopen("input6.txt", "r", stdin); freopen("output6.txt", "w", stdout);
#define qw freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define sajid main
int A[sz],B[sz],C[sz],D[sz],E[sz],F[sz],G[sz];
int n,m;
signed sajid()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>A[i];
F[i]=A[i];
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>B[i];
G[i]=B[i];
C[m-i-1]=B[i];
}
C[m]=-500000000;
for(int i=0;i<n;i++)
{
C[i+m+1]=A[n-i-1];
}
int l=0,r=0;
for(int i=1;i<=n+m;i++)
{
if(i<=r)
{
E[i]=min(r-i+1,E[i-l]);
}
while(i+E[i]<=n+m && C[E[i]]-C[0]==C[i+E[i]]-C[i])
E[i]++;
if(i+E[i]-1>r) {
l=i;r=i+E[i]-1;
}
}
for(int i=0;i<m;i++)
{
C[i]=B[i];
}
for(int i=0;i<n;i++)
{
C[i+m+1]=A[i];
}
for(int i=0;i<n;i++)
{
A[i]=E[n+m-i];
}
l=0;
r=0;
for(int i=1;i<=n+m;i++)
{
if(i<=r)
{
D[i]=min(r-i+1,D[i-l]);
}
while(i+D[i]<=n+m && C[D[i]]-C[0]==C[i+D[i]]-C[i])
D[i]++;
if(i+D[i]-1>r) {
l=i;r=i+D[i]-1;
}
}
// cout<<0<<" ";
for(int i=0;i<n;i++)
{
B[i]=D[i+m+1];
}
int cnt=0;
vector<pii> xx,yy;
for(int i=0;i<=n;i++){
int a=0;
int b=0;
if(i>0) a=A[i-1];
if(i<n) b=B[i];
// cout<<i<<" "<<a<<" "<<b<<endl;
if(a+b>=m && (a==0 || b==0 ||(F[i]-F[i-1]==G[0]-G[m-1])))
{xx.pu(mp(i-a,i+b-m)); }
if(a==m) xx.pu(mp(i-a,i-a));
if(b==m ) xx.pu(mp(i,i));
}
sort(xx.begin(),xx.end());
for(int i=0;i<xx.size();i++)
{
if(yy.size()==0) yy.pu(mp(xx[i].fi,xx[i].se));
else{
int p=yy.size()-1;
if(yy[p].se>=xx[i].se) continue;
if(yy[p].se>=xx[i].fi) yy[p].se=xx[i].se;
else yy.pu(mp(xx[i].fi,xx[i].se));
}
}
for(int i=0;i<yy.size();i++)
{
cnt+=yy[i].se-yy[i].fi+1;
}
cout<<cnt<<endl;
}
