Contest Div1 : Here
Contest Div2 : Here
Contest Div3 : Here
Setter : Yaswanth Phani Kommineni
Tester : Aryan Choudhary
DIFFICULTY
Easy-Medium
Pre Requisites
String Algorithms, Math
Explanation :
For any i and j, if there does not exist any rotation which results in A_i black and A_j white, it implies that, after any number of rotations, whenever A_i is black, A_j is also black. Let S be the set of black indices. This would imply that \forall \ x \in S,\ (x + j-i) \text{ mod }N \in S. In this case, we say that S is a (j-i)-cycle.
Therefore, we want to find the maximum value of A_i - A_j such that S is not a (j-i)-cycle.
Consider the minimum k such that S is a k-cycle. Note that all S are N-cycles, so such a k always exists. Note that for all x, if k divides x, S is an x-cycle.
Claim: If S is an x-cycle, k divides x
Proof: If S is an x-cycle and a k-cycle, then S must be a gcd(x, k)-cycle as well - this follows directly from the Extended Euclidean Algorithm. Now, since k is minimum, we know k < x. If k does not divide x, this implies that gcd(x, k) < k. However, since S is a gcd(x, k)-cycle and gcd(x, k) < k, this contradicts the minimality of k. Therefore, k must divide x.
Therefore, we want to find the maximum value of A_i - A_j such that (j-i) mod k \neq 0. Assuming we have k, this is simple to do in O(N). We simply create two arrays b and a where b_i = max \{A_x | x \text{ mod } k = i\} and a_i = min \{A_x | x \text{ mod } k = i\}. Finally, we find \max\{b_i - a_j | i \neq j\}. The details are left as an exercise.
Now, we go back to the problem of how to find k. This is equivalent to finding the “periodicity” of the string C. There are many ways of doing this - an O(N) solution exists using KMP. You can read this comment thread for more details: November Lunchtime 2021 - Codeforces.
Time Complexity
O(N)
SOLUTIONS:
Setter
/*
yaswanth phani kommineni
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;
#define mpa make_pair
#define endl '\n'
// Z-Algo
vector <int> Z(string s){
int n = (int)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;
}
void solve(){
int n;
cin >> n;
vector <pair<int,int>> a(n);
string col;
for(int i=0;i<n;i++){
cin >> a[i].first;
a[i].second = i; // as we need initial indices after sorting the array
}
cin >> col;
auto z = Z(col+"$"+col);
int lbv = n; // lowest bad value
for(int i=2;i<n;i++){
if(n%i == 0){
if(z[2*n+1 - i] == i && z[2*n+1- (n-i)] == (n-i)){ // checking whether the value i is bad or not
lbv = i;
break;
}
}
}
sort(a.begin(),a.end());
int ans = 0;
int j = n-1;
while((a[j].second-a[0].second+n)%lbv == 0){
j--;
}
ans = a[j].first - a[0].first;
j = 0;
while((a.back().second-a[j].second)%lbv == 0){
j++;
}
ans = max(ans,a.back().first - a[j].first);
cout << ans << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
//freopen("output.txt","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
/* in the name of Anton */
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
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;
}
assert(l<=x&&x<=r);
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,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFL;
lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e5);
int sumN = 1.5e6;
while(T--)
{
const int n=readIntLn(2,sumN);
sumN-=n;
a=readVectorInt(n,1,1e9);
const auto s=readStringLn(n,n);
lli colors=0;
for(auto x:s){
assert(x=='B'||x=='W');
if(x=='B')
colors|=1;
else
colors|=2;
}
assert(colors==3);
lli ans=0;
// minimum period
const lli p = [&](){
auto pi=prefix_function(s+s);
dbg(pi);
for(int i=n;i<2*n;++i){
if(pi[i]<n)
continue;
const int p=i-n+1;
dbg(i,pi[i]);
assert(s==(s+s).substr(p,n));
return p;
}
assert(false);
}();
vii values(n,mp(-INF,INF));
for(int i=0;i<n;++i){
values[i%p].X=max(values[i%p].X,a[i]);
values[i%p].Y=min(values[i%p].Y,a[i]);
}
lli mn=INF;
for(auto x:values){
ans=max(ans,x.X-mn);
mn=min(mn,x.Y);
}
reverse(all(values));
mn=INF;
for(auto x:values){
ans=max(ans,x.X-mn);
mn=min(mn,x.Y);
}
cout<<ans<<endl;
} aryanc403();
readEOF();
return 0;
}