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.