PREFONES - Editorial

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

None

PROBLEM:

You have a binary string S of length N. You can delete at most one substring of S.
If this move is performed optimally, find the longest prefix containing all 1's.

EXPLANATION:

Suppose we delete substring [L, R]. Let’s analyze what the longest prefix consisting of ones looks like.
For convenience, a prefix containing only ones will be called good.

There are two cases to consider:

• First, suppose substring [1, L-1] contains a zero. Then, the longest good prefix is simply the longest good prefix of [1, L-1]; which also equals the longest good prefix of S.
Notice that this is completely independent of R.
• Second, it might be the case that [1, L-1] contains only ones. Then, the length of the longest good prefix is L-1, plus the longest good prefix of [R+1, N].

The first case is quite easy: the longest good prefix of S can be computed in \mathcal{O}(N), so let’s deal with the second case.

We require that [1, L-1] contains only ones; meaning [1, L-1] is a good prefix.
Obviously, it’s thus best to choose [1, L-1] to be the longest good prefix possible; which we’ve already computed above.
This fixes L.

Now, what about the choice of R? Of course, it’d be nice if [R+1, N] had a large good prefix.
We can simply find the longest good prefix for every choice of R \geq L, as follows:

• Let’s look at R from N down to L. Let \text{good}(R) denote the longest good prefix of [R, N].
• If S_R = 0, then \text{good}(R) = 0.
• Otherwise, \text{good}(R) = 1 + \text{good}(R+1).

Compute \text{good}(R) this way for every R \geq L, and take the maximum value of them.

You may also notice that this is equivalent to finding the longest block of ones in S that isn’t a prefix.
Either way, the time complexity is \mathcal{O}(N).

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Setter's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
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 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){
}
long long readIntLn(long long l,long long r){
}
}
}
void solve()
{
for(auto ch:S)
assert(ch=='0' || ch=='1');
vector <int> cont;
for(int i=0;i<n;i++)
{
if(S[i]=='1')
{
int j;
int now=0;
for(j=i;j<n;j++)
{
if(S[j]=='1')
now++;
else
break;
}
cont.pb(now);
i=j-1;
}
}
if(S[0]=='0')
{
int ans=0;
for(auto it:cont)
ans=max(ans,it);
cout<<ans<<'\n';
return;
}
int ans=cont[0];
for(int i=1;i<cont.size();i++)
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's code (C++)
// Jai Shree Ram

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

const int MOD = hell;

struct mod_int {
int val;

mod_int(long long v = 0) {
if (v < 0)
v = v % MOD + MOD;

if (v >= MOD)
v %= MOD;

val = v;
}

static int mod_inv(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;

while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}

return x < 0 ? x + m : x;
}

explicit operator int() const {
return val;
}

mod_int& operator+=(const mod_int &other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}

mod_int& operator-=(const mod_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}

static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return x % m;
#endif
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}

mod_int& operator*=(const mod_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}

mod_int& operator/=(const mod_int &other) {
return *this *= other.inv();
}

friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }

mod_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}

mod_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}

mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }

mod_int operator-() const {
return val == 0 ? 0 : MOD - val;
}

bool operator==(const mod_int &other) const { return val == other.val; }
bool operator!=(const mod_int &other) const { return val != other.val; }

mod_int inv() const {
return mod_inv(val);
}

mod_int pow(long long p) const {
assert(p >= 0);
mod_int a = *this, result = 1;

while (p > 0) {
if (p & 1)
result *= a;

a *= a;
p >>= 1;
}

return result;
}

friend ostream& operator<<(ostream &stream, const mod_int &m) {
return stream << m.val;
}
friend istream& operator >> (istream &stream, mod_int &m) {
return stream>>m.val;
}
};
#define NCR
const int N=1e6;
mod_int fact[N],inv[N];
void init(int n=N){
fact[0]=inv[0]=inv[1]=1;
rep(i,1,N)fact[i]=i*fact[i-1];
rep(i,2,N)inv[i]=fact[i].inv();
}
mod_int C(int n,int r){
if(r>n || r<0)return 0;
return fact[n]*inv[n-r]*inv[r];
}

int solve(){

static int sum_n = 0;
sum_n += n;

assert(sum_n <= 2e5);

for(auto &i: a){
assert(i == '0' or i == '1');
}

vector<int> t;
int i = 0;
int ans = 0;
while(i < n){
if(a[i] == '0') {
i++;
continue;
}
int j = i;
while(j < n and a[j] == '1')j++;
maxs(ans, j - i);
t.push_back(j - i);
i = j;
}
if(t.size() == 0){
cout << 0 << endl;
return 0;
}
sort(1 + all(t));
reverse(1 + all(t));
if(t.size() > 1 and a[0] == '1'){
maxs(ans, t[0] + t[1]);
}
cout << ans << endl;

return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
while(t--){
solve();
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
L = 0
while L < n and s[L] == '1': L += 1
R = L+1
mx = cur = 0
while R < n:
if s[R] == '0':
mx = max(mx, cur)
cur = 0
else: cur += 1
R += 1
mx = max(mx, cur)
print(mx + L)

1 Like

Hey, can anyone tell me an edge case for my code? Its failing on last testcase.

Check with the string with no zeros, I too forgot it at first

My code is failing for 1 test case dont know which onw ??
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t–)
{
int n ; cin>>n;
string s;
cin >> s;

    int cont = 0;
vector<int> temp;
for (int i = 0; i < n; i++)
{
if (s[i] == '1')
cont++;
else
{
if (cont != 0)
temp.push_back(cont);
cont = 0;
}
}
if (cont != 0)     //0000
temp.push_back(cont);

if (temp.size() == 0) // 1111
{
cout << "0" << endl;
}
else if (temp.size() == 1)
{
cout << n << endl;
}

else if (s[0] == '0')
{
int ans = 0;
for (auto i : temp)
{
ans = max(ans, i);
}
cout << ans << endl;
}
else{
int ans =temp[0];
int mm=0;
for(int i=1;i<temp.size();i++){
mm=max(mm,temp[i]);
}
cout<<(mm+ans)<<endl;
}
}

return 0;


}

Please let me know the testcase its failing on.
7/8 passed. Failed on the last one.
CodeChef | Competitive Programming | Participate & Learn.

@vivann

1
2
10


You need to ignore the prefix in the second part.

1 Like

hi i am new to codechef
this the first comment i am reading