PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy-Med
PREREQUISITES:
Suffix arrays or hashing
PROBLEM:
There’s a binary string S, which will change as follows:
- First, Alice will delete a substring from S. This substring can be empty.
- Then, Bob will flip some substring of S, changing all its ones to zeros and vice versa. Again, this substring can be empty.
Alice wants the resulting string to be lexicographically as large as possible, while Bob wants it to be as small as possible.
Find the final string.
EXPLANATION:
First, let’s look at what Bob does when he receives the string.
He wants the lexicographically smallest string, so ideally it starts with as many zeros as possible.
So,
- If S contains only zeros, Bob won’t do anything to it.
- Otherwise, Bob will flip the first block of ones in A, where a block refers to a maximal substring whose characters are all the same.
- For example, if A = \text{000110011110011}, Bob will flip the first block of ones to obtain \text{000\underline{00}0011110011}.
This is Bob’s unique best move: anything else is strictly worse for him.
Subtask 1
Now that we know what Bob will do, let’s try to see how Alice can play around that.
We can afford \mathcal{O}(N^2) time in the first subtask, and Bob’s move is easy to perform in linear time.
So, if we’re able to find \mathcal{O}(N) candidate moves for Alice, we can simply try them all and take the best one (after all, string comparison can also be done in linear time)
Let [x, y] be the leftmost block of ones in A, and [l, r] be the substring chosen by Alice.
We analyze three cases.
Case 1: l \leq x
Here, it’s always optimal to choose l = 1.
This is because, quite simply, deleting [l-1, r] is better for Alice than deleting [l, r]: the effect on the final string is essentially just removing a 0 from the prefix, which is (almost) always going to lead to a lexicographically larger string.
The only exception is if the final string consists of all zeros, in which case it’s optimal to maximize its length - in which case it’s better to not delete anything from S anyway.
Case 2: x \lt l \leq y+1
Here, it’s again always optimal to choose l = x+1, for exactly the same reasons: moving l to l-1 is equivalent to deleting a zero in the final string, which is ideal for Alice in almost every case — and the one time it isn’t, it’s best to not delete anything.
Case 3: l \gt y+1
Now that l is large enough, Bob’s move is fixed: he’ll always operate on [x, y] and turn it into zeros.
So, the final string after Bob’s move [l, r] will look like l-1 zeros followed by the suffix starting at r+1.
Clearly, for a fixed l, it’s optimal to just choose the largest possible ending after l: everything else is just worse.
Now, we have no idea which of these cases is optimal, however observe that we do indeed have only \mathcal{O}(N) candidates:
- Case 1 gives us every substring starting at index 1.
- Case 2 gives us every substring starting at index x+1.
- Case 3 gives us exactly one substring starting at each index \gt y+1, for at most N in total.
In addition to these, we also consider the case of Alice just not deleting any substring, which is optimal in some cases.
We now have \sim 3N candidate moves for Alice, so simply try them all and take the best among them.
Generating the candidates is not too hard: cases 1 and 2 are trivial, while for case 3 we only need to find the lexicographically largest suffix that starts after l, which can be precomputed.
Subtask 2
For full points, \mathcal{O}(N^2) is no longer acceptable.
We have \mathcal{O}(N) candidates for Alice’s move, but even generating all the strings corresponding to them all would be too slow.
However, observe that for each candidate, once Bob makes his move, the resulting string will look like some prefix that’s entirely zeros, followed by either a suffix of S (cases 1 and 2), or some substring of S followed by a suffix of S (case 3).
Note that both the suffix and the substring will start with 1 in an optimal solution.
For each candidate move [l, r], let’s encode the final string as the tuple (z, l, r, i), denoting that the final string has z zeros followed by the substring S[l, r] followed suffix starting at i.
These tuples are not too hard to find with a bit of bookkeeping and casework, and have the advantage of needing only constant space each.
Now, two pairs (z_1, l_1, r_1, i_1) and (z_2, l_2, r_2, i_2) can be compared as follows:
- If z_1 \neq z_2, whichever z_i is smaller represents the larger string.
- If z_1 = z_2, then S[l_1, r_1] + S[i_1, n] and S[l_2, r_2] + S[i_2, n] need to be compared quickly.
This can be done in a variety of ways, the simplest is probably to use a combination of hashing and binary search allowing for substring comparison in logarithmic time: use binary search to find the first position where the hashes differ, then directly compare the characters at that position.
It’s also possible to use string suffix structures to perform this comparison.
Since tuples can now be compared in \mathcal{O}(1) or \mathcal{O}(\log N) time, and there are \mathcal{O}(N) of them, the maximum among them can be found in \mathcal{O}(N\log N) at worst.
Once the optimal (z, l, r, i) tuple is known, reconstruction is trivial.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++, Suffix array)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;
#define ll long long
const int N = 3e5 + 9;
const int LG = 18;
void induced_sort(const vector<int> &vec, int val_range, vector<int> &SA, const vector<bool> &sl, const vector<int> &lms_idx) {
vector<int> l(val_range, 0), r(val_range, 0);
for (int c : vec) {
if (c + 1 < val_range) ++l[c + 1];
++r[c];
}
partial_sum(l.begin(), l.end(), l.begin());
partial_sum(r.begin(), r.end(), r.begin());
fill(SA.begin(), SA.end(), -1);
for (int i = lms_idx.size() - 1; i >= 0; --i)
SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
for (int i : SA)
if (i >= 1 && sl[i - 1]) {
SA[l[vec[i - 1]]++] = i - 1;
}
fill(r.begin(), r.end(), 0);
for (int c : vec)
++r[c];
partial_sum(r.begin(), r.end(), r.begin());
for (int k = SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
if (i >= 1 && !sl[i - 1]) {
SA[--r[vec[i - 1]]] = i - 1;
}
}
vector<int> SA_IS(const vector<int> &vec, int val_range) {
const int n = vec.size();
vector<int> SA(n), lms_idx;
vector<bool> sl(n);
sl[n - 1] = false;
for (int i = n - 2; i >= 0; --i) {
sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
}
reverse(lms_idx.begin(), lms_idx.end());
induced_sort(vec, val_range, SA, sl, lms_idx);
vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
for (int i = 0, k = 0; i < n; ++i)
if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
new_lms_idx[k++] = SA[i];
}
int cur = 0;
SA[n - 1] = cur;
for (size_t k = 1; k < new_lms_idx.size(); ++k) {
int i = new_lms_idx[k - 1], j = new_lms_idx[k];
if (vec[i] != vec[j]) {
SA[j] = ++cur;
continue;
}
bool flag = false;
for (int a = i + 1, b = j + 1;; ++a, ++b) {
if (vec[a] != vec[b]) {
flag = true;
break;
}
if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
break;
}
}
SA[j] = (flag ? ++cur : cur);
}
for (size_t i = 0; i < lms_idx.size(); ++i)
lms_vec[i] = SA[lms_idx[i]];
if (cur + 1 < (int)lms_idx.size()) {
auto lms_SA = SA_IS(lms_vec, cur + 1);
for (size_t i = 0; i < lms_idx.size(); ++i) {
new_lms_idx[i] = lms_idx[lms_SA[i]];
}
}
induced_sort(vec, val_range, SA, sl, new_lms_idx);
return SA;
}
vector<int> suffix_array(const string &s, const int LIM = 128) {
vector<int> vec(s.size() + 1);
copy(begin(s), end(s), begin(vec));
vec.back() = '$';
auto ret = SA_IS(vec, LIM);
ret.erase(ret.begin());
return ret;
}
struct SuffixArray {
int n;
string s;
vector<int> sa, rank, lcp;
vector<vector<int>> t;
vector<int> lg;
SuffixArray() {}
SuffixArray(string _s) {
n = _s.size();
s = _s;
sa = suffix_array(s);
rank.resize(n);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
costruct_lcp();
prec();
build();
}
void costruct_lcp() {
int k = 0;
lcp.resize(n - 1, 0);
for (int i = 0; i < n; i++) {
if (rank[i] == n - 1) {
k = 0;
continue;
}
int j = sa[rank[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
lcp[rank[i]] = k;
if (k) k--;
}
}
void prec() {
lg.resize(n, 0);
for (int i = 2; i < n; i++) lg[i] = lg[i / 2] + 1;
}
void build() {
int sz = n - 1;
t.resize(sz);
for (int i = 0; i < sz; i++) {
t[i].resize(LG);
t[i][0] = lcp[i];
}
for (int k = 1; k < LG; ++k) {
for (int i = 0; i + (1 << k) - 1 < sz; ++i) {
t[i][k] = min(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
}
}
}
int query(int l, int r) { // minimum of lcp[l], ..., lcp[r]
int k = lg[r - l + 1];
return min(t[l][k], t[r - (1 << k) + 1][k]);
}
int get_lcp(int i, int j) { // lcp of suffix starting from i and j
if (i == j) return n - i;
int l = rank[i], r = rank[j];
if (l > r) swap(l, r);
return query(l, r - 1);
}
int lower_bound(string &t) {
int l = 0, r = n - 1, k = t.size(), ans = n;
while (l <= r) {
int mid = l + r >> 1;
if (s.substr(sa[mid], min(n - sa[mid], k)) >= t) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
int upper_bound(string &t) {
int l = 0, r = n - 1, k = t.size(), ans = n;
while (l <= r) {
int mid = l + r >> 1;
if (s.substr(sa[mid], min(n - sa[mid], k)) > t) ans = mid, r = mid - 1;
else l = mid + 1;
}
return ans;
}
// occurrences of s[p, ..., p + len - 1]
pair<int, int> find_occurrence(int p, int len) {
p = rank[p];
pair<int, int> ans = {p, p};
int l = 0, r = p - 1;
while (l <= r) {
int mid = l + r >> 1;
if (query(mid, p - 1) >= len) ans.first = mid, r = mid - 1;
else l = mid + 1;
}
l = p + 1, r = n - 1;
while (l <= r) {
int mid = l + r >> 1;
if (query(p, mid - 1) >= len) ans.second = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n;
cin>>n;
string s;
cin>>s;
ll flag=0;
for(int i=1;i<n;i++){
if(s[i]!=s[i-1]){
flag++;
}
}
flag+=(s[0]=='1');
if(flag<3){
for(int i=0;i<n;i++){
cout<<"0";
}
cout<<"\n";
continue;
}
SuffixArray S(s);
flag=0;
ll pos1=-1,pos0=-1,pos3=-1;
ll maxi1=-1,maxi0=-1,maxi3=0;
for(int i=1;i<n;i++){
if(s[i]=='1' && flag>=2){
if(maxi3<S.rank[i]){
maxi3=S.rank[i];
pos3=i;
}
}
if(s[i]!=s[i-1]){
if(s[i]=='0'){
flag++;
if(maxi1<S.rank[i-1]){
maxi1=S.rank[i-1];
pos1=i-1;
}
}else{
if(pos1!=-1 && maxi0<S.rank[i-1]){
maxi0=S.rank[i-1];
pos0=i-1;
}
}
}
}
flag=0;
string ans1="";
string ans2="";
string ans3="0";
for(int i=0;i<n;i++){
if(s[i]=='1'){
break;
}
ans2+='0';
}
ans2+='0';
for(int i=pos1;i<n;i++){
ans1+=s[i];
}
ans1[0]='0';
for(int i=pos0;i<n;i++){
ans2+=s[i];
}
if(s[0]=='1' && s[1]=='0' && s[2]=='1' && pos3!=-1){
ans3="00";
for(int i=2;i<n;i++){
if(s[i]=='0'){
break;
}
ans3+=s[i];
}
for(int i=pos3;i<n;i++){
ans3+=s[i];
}
}
if(ans1<ans3){
ans1=ans3;
}
if(ans1>ans2){
cout<<ans1<<"\n";
}else{
cout<<ans2<<"\n";
}
}
return 0;
}
Tester's code (C++, Hashing)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
// #define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
}inp;
//0 based string hashing with closed intervals
class HashedString {
private:
// change M and B if you want
static const long long M = 2e9+39;
static const long long B = 9973;
// pow[i] contains B^i % M
static vector<long long> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<long long> p_hash;
public:
HashedString(const string& s) : p_hash(s.size() + 1) {
while (pow.size() < s.size()) {
pow.push_back((pow.back() * B) % M);
}
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
long long getPow(int p){
return pow[p];
}
long long getHash(int start, int end) {
long long raw_val = (
p_hash[end + 1] - (p_hash[start] * pow[end - start + 1])
);
return (raw_val % M + M) % M;
}
};
vector<long long> HashedString::pow = {1};
int smn = 0;
void solve()
{
int n;
// cin >> n;
n = inp.readInt(1,200'000);
smn += n;
inp.readEoln();
string s;
// cin >> s;
s = inp.readString(n,n,"01");
inp.readEoln();
int sm = 0;
for(auto &x : s)sm += x-'0';
if(sm == 0){
cout << s << "\n";
return;
}
repin{
if(s[i] == '1'){
bool b = 1;
rep(j,i,i+sm){
if(s[j] == '0')b = 0;
}
if(b == 1){
rep(j,0,n)cout << 0;
cout << "\n";
return;
}
break;
}
}
HashedString hs(s);
int id = -1;
repin{
if(s[i] == '1' && (i == n-1 || s[i+1] == '0')){
if(id == -1){
id = i;
}
else{
if(hs.getHash(i,n-1) == hs.getHash(id,id+n-1-i))continue;
int l = 1,r = n-i;
while(r > l+1){
int m = (l+r)/2;
if(hs.getHash(i,i+m-1) == hs.getHash(id,id+m-1))l = m;
else r = m;
}
if(s[i+l] < s[id+l])continue;
id = i;
}
}
}
string ans = s.substr(id,n-id);
ans[0] = '0';
int id1 = -1;
int f;
repin{
if(s[i] == '1'){
f = i;break;
}
}
rep(i,f+1,n){
if(i == n-1 || s[i+1] == '0'){
if(id1 == -1){
id1 = i+1;
}
else{
if(hs.getHash((i+1),n-1) == hs.getHash(id1,id1+n-1-(i+1)))continue;
int l = 1,r = n-(i+1);
while(r > l+1){
int m = (l+r)/2;
if(hs.getHash((i+1),(i+1)+m-1) == hs.getHash(id1,id1+m-1))l = m;
else r = m;
}
if(s[(i+1)+l] < s[id1+l])continue;
id1 = (i+1);
}
}
}
string ans1 = s.substr(0,f) + "0" + (id1<n?s.substr(id1,n-id1):"");
ans = max(ans,ans1);
if(n >= 3 && s.substr(0,3) == "101"){
int z = -1;
rep(i,3,n){
if(s[i] == '0'){
z = i;
break;
}
}
if(z != -1){
int id = -1;
rep(i,z,n-1){
if(s[i] == '0' && s[i+1] == '1'){
if(id == -1){id = i+1;continue;}
if(hs.getHash((i+1),n-1) == hs.getHash(id,id+n-1-(i+1)))continue;
int l = 1,r = n-(i+1);
while(r > l+1){
int m = (l+r)/2;
if(hs.getHash((i+1),(i+1)+m-1) == hs.getHash(id,id+m-1))l = m;
else r = m;
}
if(s[(i+1)+l] < s[id+l])continue;
id = (i+1);
}
}
string ans2 = s.substr(0,z) + (id<n && (id!=-1)?s.substr(id,n-id):"");
ans2[0] = '0';
ans = max(ans,ans2);
}
}
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
// cin >> t;
t = inp.readInt(1,100'000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
assert(smn <= 200'000);
return 0;
}
Editorialist's code (C++, Subtask 1)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
vector<string> candidates;
vector<string> sufmax(n+1);
for (int i = n-1; i >= 1; --i) {
sufmax[i] = max(sufmax[i+1], s.substr(i));
}
for (int i = 0; i < n; ++i) candidates.push_back(s.substr(i));
int pos = 0;
while (pos < n and s[pos] == '0') ++pos;
for (int i = pos+1; i < n; ++i)
candidates.push_back(s.substr(0, pos+1) + s.substr(i+1));
while (pos < n and s[pos] == '1') ++pos;
for (int i = pos; i < n; ++i)
candidates.push_back(s.substr(0, i) + sufmax[i]);
string ans = "0";
for (auto &cur : candidates) {
int flag = 0;
for (auto &c : cur) {
if (c == '1') {
flag = 1;
c = '0';
}
else {
if (flag) break;
}
}
ans = max(ans, cur);
}
cout << ans << '\n';
}
}