Problem link
Contest: CodeChef: Practical coding for everyone
Practice: ABCHEAT Problem - CodeChef
Author: dedsec_29
Tester: sayan_244, dhrub_kumar
Editorialist: dedsec_29
Difficulty
Medium
Prerequisites
Z-function, Prefix sums, Range Minimum Queries
Quick Explanation
For each position that Alice can take, find the maximum length interval ending at i that matches with the suffix of the string. Suppose [i...j] and [n-(j-i+1)...n-1] are the matching intervals, then the answer is just the minimum sub-array sum (with their right boundaries fixed) in the two intervals.
Explanation
First, let’s see how to solve the following problem:
Given i, find the maximum length of a sub-string of S that ends at index i and matches with the suffix of S.
If we reverse our string S, the problem can be re-framed as:
Given i, find the maximum length of a sub-string of S that starts at index i and matches with the prefix of S.
This is a problem we can directly solve using Z-function, which can be computed in linear time. So we reverse our string, compute the z-function array (let us call it z), and finally reverse the z-function array to solve the original problem.
For a given position j where we can put Alice, we have i = j+1-z[i]
Alice will try to achieve a maximal score. This means if we put Alice in position j, she will choose a position k (k \leq j) such that Sum[k..j] is as maximum as possible. Let pre[i] denote the prefix sum array of A. Then,
\max_{i \leq k \leq j}(Sum[k..j]) = \max_{i \leq k \leq j}(pre[j] - pre[k-1])
= pre[j] - \max_{i \leq k \leq j}(-pre[k-1])
= pre[j] - \min_{i \leq k \leq j}(pre[k-1])
= pre[j] - RMQ( i-1, j-1)
Where RMQ(l,r) returns the minimum value of the array pre[] in the given range [l,r]. You can use Sparse Table to find the RMQ in any range in O(1) time per query with O(NogN) preprocessing.
For Bob, we can find his maximum score by finding the same as above in the interval [n-z[i]...n-1] and take the maximum of the two, giving us the maximum team score if we put Alice at j.
The answer is just the maximum of this value, taken for all j.
Alternate approaches
The maximum matching can be found using polynomial hashing and binary search as well. For RMQ, using a segment tree alternatively also fits in the constraints.
Solutions
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize "trapv"
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#pragma GCC optimize("unroll-loops")
#define int long long
class SparseTable {
public:
int n, ub;
vector<vector<int>> sparse;
SparseTable(vector<int>& arr) {
n = arr.size();
ub = __lg(n);
sparse = vector<vector<int>>(n, vector<int>(ub + 1));
for (int i=0;i<n;i++)
sparse[i][0] = arr[i];
for (int j=1;j<=ub;j++)
for (int i=0;i+(1<<j)-1<n;i++)
sparse[i][j] = min(sparse[i][j-1], sparse[i+(1<<(j-1))][j-1]);
}
int query(int l,int r) {
if (r < 0)
return 0;
bool edge = (l < 0);
l = max(0ll, l);
int interval = r-l+1;
int jump = __lg(interval);
int x = min(sparse[l][jump], sparse[r-(1<<jump)+1][jump]);
if (edge)
return min(0ll, x);
return x;
}
};
vector<int> z_function(string& s) {
int n = s.size();
vector<int> z(n);
// z0 not well defined
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i <= r)
z[i] = min(r-i+1, z[i-l]); // s[l..r] => s[0..r-l] so s[l..i] => s[0..i-l]
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) // launch
z[i]++;
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
vector<int> make_d(string s) {
reverse(s.begin(), s.end());
vector<int> z = z_function(s);
reverse(z.begin(), z.end());
return z;
}
void solve() {
int n; cin >> n;
string s; cin >> s;
vector<int> A(n);
for (int& i: A) cin >> i;
vector<int> d = make_d(s);
vector<int> pre(A);
for (int i = 1; i < n; i++)
pre[i] += pre[i-1];
SparseTable X(pre);
int ans = 0;
for (int j = 0; j < n-1; j++) {
if (d[j] == 0)
continue;
int i = j+1 - d[j];
ans = max(ans, pre[j] - X.query(i-1, j-1));
i = n - d[j];
ans = max(ans, pre[n-1] - X.query(i-1, n-2));
}
cout << ans << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin>>t;
while (t--)
solve();
return 0;
}
Tester's solution
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fastio() \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define pb push_back
#define show(x) cout << (#x) << " : " << x << endl;
//typedef __int128 bigll;
typedef long long ll;
#define ull unsigned long long
#define ld long double
#define pow power
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define sq(x) ((x) * (x))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define siz(a) int((a).size())
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define Forl(i,a,b) for(ll (i)=(a);(i) < (b); ++(i))
#define Forn(i,a,b) for(int (i)=(a);(i) >= (b); --(i))
#define Fornl(i,a,b) for(ll (i)=(a);(i) >= (b); --(i))
#define endl "\n"
#define pi 3.14159265
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
const ll mod = 1000 * 1000 * 1000 + 7;
const ll mod1 = 998244353;
const ll INF = 1ll*1000*1000*1000*1000*1000*1000 + 7;
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef tree<pair<ll, ll>,null_type,less<pair<ll, ll>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ll power(ll x, ll y)
{
ll res = 1;
while (y > 0)
{
if (y & 1)
res = (long long)(res*x); // adding powers wherever bit is set
y = y>>1;
x = (long long)(x*x); // increasing power by 2
//cout<<x<<'\n';
}
return res;
}
// Stolen Templates
template<typename F, typename S>
ostream& operator <<(ostream& ostream, pair<F, S>& p) {
cout << p.first << " " << p.second;
return ostream;
}
template<typename T>
ostream& operator <<(ostream& ostream, vector<T>& v) {
for(auto& element : v) {
cout << element << " ";
}
return ostream;
}
template<typename T>
ostream& operator <<(ostream& ostream, vector<vector<T>>& v) {
for(auto& row : v) {
for(auto& cell : row) {
cout << cell << " ";
}
cout << "\n";
}
return ostream;
}
template<typename F, typename S>
istream& operator >>(istream& istream, pair<F, S>& p) {
cin >> p.first >> p.second;
return istream;
}
template<typename T>
istream& operator >>(istream& istream, vector<T>& v) {
for(auto& element : v) {
cin >> element;
}
return istream;
}
void print() {
cout << endl;
}
template <typename T> void print(const T& t) {
cout << t << endl;
}
template <typename First, typename... Rest> void print(const First& first, const Rest&... rest) {
cout << first << " ";
print(rest...); // recursive call using pack expansion syntax
}
void dbg() {
cerr << endl;
}
template <typename T> void dbg(const T& t) {
cerr << t << endl;
}
template <typename First, typename... Rest> void dbg(const First& first, const Rest&... rest) {
cerr << first << " ";
dbg(rest...); // recursive call using pack expansion syntax
}
// Stolen Templates end here
// ostream& operator << (ostream&, bigll val) {
// string temp;
// while (val > 0) { temp.pb(val % 10 + '0'); val /= 10; }
// for(int i = siz(temp) - 1; i >= 0; i--)cout<<temp[i];
// return cout;
// } // inside class
// istream& operator >> (istream&, bigll & val) {
// string temp; cin>>temp; val = 0;
// for(int i = 0; i < siz(temp); i++)val = val * 10 + temp[i] - '0';
// return cin;
// } // for cin we use & because we want the original object we are sending not a copy of it
struct segtree {
ll size;
vector <ll> mins;
void init (ll n) {
size = 1;
while (size < n)
size *= 2;
mins.assign(2 * size, INF);
}
void set (ll i, ll v, ll x, ll lx, ll rx) {
if (rx - lx == 1) {
mins[x] = v;
return;
}
ll m = (lx + rx)/2;
if (i < m) {
set(i, v, 2 * x + 1, lx, m);
} else {
set(i, v, 2 * x + 2, m, rx);
}
mins[x] = min(mins[2 * x + 1], mins[2 * x + 2]);
}
void set (ll i, ll v) {
set(i, v, 0, 0, size);
}
ll minx (ll l, ll r, ll x, ll lx, ll rx) {
if (lx >= r || l >= rx) return INF;
if (lx >=l and rx <= r) return mins[x];
ll m = (lx + rx)/2;
ll s1 = minx(l, r, 2 * x + 1, lx, m);
ll s2 = minx(l, r, 2 * x + 2, m, rx);
return min(s1,s2);
}
ll minx (ll l, ll r) {
return minx(l, r, 0, 0, size);
}
};
vector<int> z_function(string s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for(int i = 1; i < n; i++) {
if(i < r) {
z[i] = min(r - i, z[i - l]);
}
while(s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if(i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
// If you plan on using set / map do check if it will TLE or not
fastio();
ll T;
cin>>T;
while(T--)
{
ll n;
cin>>n;
string s;
cin>>s;
vector <ll> val(n);
cin>>val;
reverse(all(s)); reverse(all(val));
vector <int> zf = z_function(s);
vector <ll> pre(n + 2);
segtree st; st.init(n + 5);
Fornl(i,n - 1, 0){ pre[n - i] = val[i] + pre[n - i - 1];
st.set(n - i, pre[n - i]);
}
st.set(0,0);
//cout<<pre<<endl;
//cout<<zf<<endl;
ll ans = 0;
For(i,1,n) {
ll upto = zf[i];
ll temp = pre[n] - st.minx(n - upto, n + 1);
//cout<<i<<' '<<upto<<' '<<temp<<endl;
temp = max(temp, pre[n - i] - st.minx(n - i - upto, n - i + 1));
ans = max(ans, temp);
}
cout<<ans<<endl;
}
return 0;
}