PREFONES - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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];
vector <int> adj[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 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 solve()
{
    int n=readInt(2,200000,'\n');
    string S=readString(n,n,'\n');
    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];
    int add=0;
    for(int i=1;i<cont.size();i++)
        add=max(add,cont[i]);
    ans+=add;
    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);
    int T=readInt(1,1000,'\n');
    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 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); }
 
vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    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(){
 		
               int n = readIntLn(1, 2e5);
               static int sum_n = 0;
               sum_n += n;

               assert(sum_n <= 2e5);

               string a = readStringLn(n, n);
               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
    int t = readIntLn(1, 1000);
    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.
Link: https://www.codechef.com/viewsolution/87028399

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: Practical coding for everyone.
Thx in advance

@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