GEASS - Editorial

Contest

Author: Vallabh Deshpande
Tester: Sarthak Chafle
Editorialist: Vallabh Deshpande

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Strings

PROBLEM:

Print the index of the leftmost largest contiguous binary substring consisting of only 1s.

QUICK EXPLANATION:

Traverse the string from left to right and keep a variable for counting the number of contiguous 1s in the binary string. Reset the variable every time you encounter a 0. Keep a counter for assigning 1 based indexes to the contiguous 1s. Print the minimum such index.

EXPLANATION:

As per the problem, Lelouch buys the largest chocolate bar. If there are multiple such chocolate bars then he buys the leftmost such chocolate bar. The chocolate bars in this problem statement correspond to the largest substrings consisting of only 1s in them.

Since we need to print the index of chocolate bars, we need to assign them indexes starting with 1 to the leftmost chocolate bar. In order to do that we must keep a counter that can be incremented as soon as we reach the end of a chocolate bar. We also need to count the length contiguous 1s, for which we will keep a variable named curlen, which has the length of current chocolate bar that you are traversing.

Each time we encounter a larger chocolate bar than the previous one, we need to update another variable named totlen which stores the length of largest chocolate bar that has yet been encountered, and also we need to update ans which stores the index of largest-leftmost chocolate. We know that a chocolate bar ends when the next character in the string is a 0, the only exception is the last chocolate bar, for which we can append a 0 at the end of the string to make the implementation a bit simpler.

Finally just print the value of ans.

Time Complexity: O(n) per test case, where n is the length of string.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>

using namespace std;

void oJudge() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    oJudge();
    int t = 1;
    cin>>t;
    while(t--){
        string str;
        cin>>str;
        int n = str.length(), counter = 0, curlen = 0, totlen = 0, ans = 0;
        str.push_back('0');
        for(int i = 0; i < n; ++i){
            if(str[i] == '0'){
                curlen = 0;
            }
            else{
                ++curlen;
                if(str[i+1] == '0'){
                    ++counter;
                    if(curlen > totlen){
                        ans = counter;
                        totlen = curlen;
                    }
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
Tester's Solution
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class CodeChef {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            String s = br.readLine();
            StringBuilder sb = new StringBuilder(s);
            sb.append('0');
            int n = sb.length(), noOfBars = 0, currLen = 0, maxLen = 0, res = 0;

            for (int i = 0; i < n ; i++) {
                if (sb.charAt(i) == '0') {
                    currLen = 0;
                } else {
                    currLen++;
                    if (sb.charAt(i + 1) == '0') {
                        noOfBars++;
                    }
                    if (currLen > maxLen) {
                        maxLen = currLen;
                        res = noOfBars;
                    }
                }
            }
            System.out.println(res);
        }
    }
}
1 Like