 CHEF1010 - Editorial

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

Cakewalk

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 = *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;
for(int i = 0; i< N; i++)c[S.charAt(i)-'0']++;
pn(Math.max(0, Math.min(c, c)-1));
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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

Feel free to share your approach. Suggestions are welcomed as always. 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;

}