PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Jeevan Jyot Singh
Tester: Manan Grover and Samarth Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Observations
PROBLEM
You are given a binary string S. You can perform the following operations on S:
- Flip: Pick an index i (1 \le i \le |S|) and flip the i-th character (i.e change 1 to 0 or 0 to 1). For e.g. 01\underline{1}001 \rightarrow 01\underline{0}001
- Compress: Pick any non-empty substring consisting of the same character and replace it with a single occurrence of that character. For e.g. 100\underline{1111}10 \rightarrow 100\underline{1}10
You want to make all the characters of the binary string equal (i.e. either all characters are 0 or all characters are 1). Find the minimum number of operations required to do so.
QUICK EXPLANATION
- Compute the cost of converting the string into all zeros and all ones and print the minimum cost
- In order to compute the cost to convert S into all zeros, it’d be optimal to compress all blocks of 1 with size \gt 1 and then flip that single character.
- There is a possible situation where flipping from 0 to 1 is helpful here, as it reduces the number of components where we need to apply compress and flip operations.
EXPLANATION
First of all, one thing remains the same. Let’s try computing the cost of converting S into all zeros, and all ones, and print a minimum of the two. Hence, the rest of the editorial shall focus on converting S into all zeros.
Attempt 1
For each occurrence of 1, we flip that position. This solution wouldn’t take more than N operations, and it works, hence we can guarantee that the final answer does not exceed N.
But this attempt doesn’t utilize the compress operation at all.
Attempt 2
This time, let’s iterate over all positions in S one by one and find continuous blocks of 1 in S. For each block with size \geq 2, it is optimal to first compress them into a single character, and then flip that character, taking 2 operations.
This way, if the number of blocks is B, then 2*B is the number of operations required.
While this attempt is certainly an improvement over the previous attempt, it still has some issues. For example, consider example S = 001101100. By the above approach, we have two blocks of $1$s, and the number of operations would be 4. However, we can just flip the 0 in the middle to reduce the number of blocks by 1, leading to 3 operations.
Attempt 3
We shall build on attempt 2, but add a pass on the string to avoid such situations as happened in the previous example. it happened because though flipping a block takes 2 operations, we were able to merge to blocks in 1 operation, thus saving one operation.
Claim: This situation can happen only when the current character is 0, and both neighbouring characters are 1.
**Proof: ** Assuming at least one immediate neighbour having value 0, we see that in order to merge two blocks of 1 by flipping 0 to 1, that require at least 2 operations. But with 2 operations, we can just flip the whole box anyway.
So the replacement shall occur at some position like 101.
Another issue arises. Consider example S = 0000101000. Here, though we can merge two blocks of 1 by flipping 0 in between, a better approach here is to just flip those two positions. This happened because here no compress operation was required in flipping positions.
Attempt 4
We proved that flip from 0 to 1 should happen when they join blocks of 1. But if at least one of the neighbourhood blocks require a compress operation, only then it would be optimal to flip a 0 to 1.
This means that if we find any 1101 or 1011, we can flip the inner 0 to 1 to merge blocks of 1. One of the best examples is this S = 00110101100, which can be converted to all zeros in 4 operations.
This solution passes all tests and can be referred to in Editorialist’s solution section.
Implementation Note
There are several conditions to check for in case you stay overnight for odds, but appending two 0 at the start and two at the end automatically takes care of boundary conditions.
TIME COMPLEXITY
The time complexity is O(|S|) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while(T--)
{
string S; cin >> S;
int ans = 1e9;
for(auto x: {'0', '1'})
{
string s = x + S + x;
int n = s.size(), add = 0;
for(int i = 1; i+1 < n; i++)
{
if(s[i] != s[i-1] and s[i] != s[i+1])
s[i] = '0' + '1' - s[i], add++;
}
int res = 0, cnt = 0;
for(int i = 0; i < n;)
{
int j = i;
while(j < n and s[j] == s[i])
j++;
i = j;
cnt++;
}
res += (cnt/2) * 2;
ans = min(ans, res+add);
}
cout << ans << "\n";
}
return 0;
}
Tester 1 Solution
#include <bits/stdc++.h>
using namespace std;
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;
}
assert(l<=x&&x<=r);
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);
}
int solve(string str){
int n = str.size();
int ans = 0;
for(int i = 1 ; i < n - 1 ; i++){
if(str[i] != str[i-1] && str[i] != str[i+1])
str[i] = '0' + ('1' - str[i]), ans++;
}
int bl = 0;
for(int i = 0; i < n ; i++){
int j = i;
while(j < n && str[j] == str[i])
j++;
bl++;
i = j - 1;
}
ans += 2*(bl/2);
return ans;
}
int main() {
// your code goes here
int t;
t = readIntLn(1, 1e5);
int sum = 0;
while(t--){
string str;
str = readStringLn(1, 1e6);
int n = str.size();
sum += n;
assert(sum <= 1e6);
cout << min(solve("1" + str + "1"), solve("0" + str + "0")) << '\n';
}
readEOF();
return 0;
}
Tester 2 Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
I cal(S s,C c){
I ans=0;
if(s[0]==c && s[1]!=c){
ans++;
s[0]=s[1];
}
if(s[sz(s)-2]!=c && s[sz(s)-1]==c){
ans++;
s[sz(s)-1]=s[sz(s)-2];
}
asc(i,1,sz(s)-1){
if(s[i+1]!=s[i] && s[i-1]!=s[i]){
ans++;
s[i]=s[i+1];
}
}
I x=0;
while(x<sz(s)){
if(s[x]!=c){
x++;
continue;
}
I y=x+1;
while(y<sz(s) && s[y]==s[x]){
y++;
}
ans+=2;
x=y;
}
return ans;
}
int main(){
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<I> randGen;
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
I t;
cin>>t;
while(t--){
S s;
cin>>s;
if(sz(s)==1){
cout<<0<<"\n";
}else{
cout<<min(cal(s,'0'),cal(s,'1'))<<"\n";
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class FLIPCOMP{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
String S = n();
int ans = S.length();
for(char ch = '0'; ch <= '1'; ch++)ans = Math.min(ans, cost(""+ch+ch+S+ch+ch, ch));
pn(ans);
}
int cost(String S, char ch){
char[] C = S.toCharArray();
int ans = 0, N = S.length();
for(int i = 2; i+2 < N; i++){
boolean f = C[i] == ch && C[i-1] != ch && C[i+1] != ch && (C[i-2] != ch || C[i+2] != ch);
if(f){
ans++;
C[i] = (char)('0'+'1'-ch);
}
}
for(int i = 0, ii = 0; i< N; i = ii){
while(ii< N && C[i] == C[ii])ii++;
if(ii-i > 1 && C[i] != ch)ans++;
if(C[i] != ch)ans++;
}
return ans;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, intparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//intolution Credits: Taranpreet intingh
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 FLIPCOMP().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. 