CHEF1010 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Krupal Patel
Tester: Nishank Suresh
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Given a binary string of length N, you are allowed to rearrange the characters of the string in any order. Find the maximum number of occurrences of 1010 achievable after rearrangement.

QUICK EXPLANATION

  • The maximum number of occurrences of 1010 is max(0, min(c_0, c_1)-1), where c_0 denote occurrences of 0 and c_1 denote the occurrences of 1 in S.
  • The rearrangement to achieve this would be to form alternating string starting with 1 until occurrences of only one character are left and then appending all those occurrences at the end.

EXPLANATION

Since we are allowed to reorder characters of S, the original string doesn’t matter at all. Only the number of 0 and 1 in S matters. Let’s denote c_0 as the number of occurrences of 0 and c_1 as the number of occurrences of 1.

The aim here is to maximize the occurrences of 1010. The important thing to notice here is that overlapping occurrences are counted as well. So if we form string 101010, we get two occurrences of 1010, using only three occurrences of both 0 and 1. Without overlapping, we would need four occurrences of 1 and four occurrences of 0.

We can see that overlapping occurrences are beneficial. So if we can obtain say x occurrences, then there would be a single consecutive segment of alternating 1 and 0, followed by remaining characters.

For example, if c_0 = 3 and c_1 = 5, then we get string 10101011. The number of occurrences of 1010 is 2.

We can see that to get x occurrences of 1010, we need at least x+1 occurrences of both 0 and 1. Hence, we can see that the number of occurrences formed is min(c_0, c_1)-1. This failed when min(c_0, c_1) = 0, in which case, the number of occurrences is 0.

So we can write the number of occurrences as max(0, min(c_0, c_1)-1), which is the required count.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

int main() 
{

    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        string s;
        cin>>s;

        int c0=0,c1=0;

        for(int i=0;i<n;i++)
        {
            if(s[i]=='0') c0++;
            else c1++;
        }

        cout<<max((int)min(c0,c1)-1,0)<<endl;
    }
    
    return 0;
}
Tester's Solution
t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = ''
    mark = [0]*n
    for i in range(n):
        req = '1' if i%2 == 0 else '0'
        id = -1
        for j in range(n):
            if mark[j] == 1:
                continue
            if s[j] == req:
                id = j
        if id >= 0:
            ans += req
            mark[id] = 1
            continue
        for j in range(n):
            if mark[j] == 1:
                continue
            id = j
        ans += s[id]
        mark[id] = 1
    tot = 0
    for i in range(n-3):
        if ans[i:i+4] == '1010':
            tot += 1
    print(tot)
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHEF1010{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        String S = n();
        int[] c = new int[2];
        for(int i = 0; i< N; i++)c[S.charAt(i)-'0']++;
        pn(Math.max(0, Math.min(c[0], c[1])-1));
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new CHEF1010().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

can anyone tell me my mistake pls…the output is same but it is not being accepted

#include<bits/stdc++.h>

using namespace std;

int main(){

int T;

cin>>T;

while(T–){

int n; unordered_map<int,int>m;

cin>>n;

string s;

cin>>s;

for(int i=0;i<n;i++){

m[s[i]]++;

}

if(m[β€˜0’]>2 && m[β€˜1’]>2){

if(m[β€˜0’]==m[β€˜1’])

cout<<(m[β€˜0’]-1)<<endl;

if(m[β€˜0’]<m[β€˜1’])

cout<<(m[β€˜0’]-1)<<endl;

if(m[β€˜1’]<m[β€˜0’])

cout<<(m[β€˜1’]-1)<<endl;

}

else

cout<<β€œ0”<<endl;

}

return 0;

}