FLIPCOMP - Editorial

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. :slight_smile:

I solved it with DP + Lazy Segment tree , ( Since I saw the pattern but still wasn’t sure about the conditions , My solution does look like an overkill ) .

I created 4 segment trees and an ans array , where ans[i][0] stores minimum no. of moves to convert first i elements to zero and ans[i][1] stores for 1.

( I will explain only how to convert all characters to zero )

At first I compressed the string , i.e. if a string has >=2 consecutive x , I changed it to 2 consecutive x.
So , now , suppose I am at ith element , and so I know answer of all i-1 elements , now if the current element is ‘0’ then the answer will be same as the last one , but if it’s ‘1’ I am considering converting all 0’s to 1 and then compressing and converting all , or another is to convert all 1’s to 0.

So ans[i][0]=min(ans[j][0]+x1+2,ans[j][0]+x2) for all j 0 to i-1 ,

where x1 is no. of ‘0’ from j->i and x2 is no. of ‘1’ from j to i

Link to my solution link

Can anyone help me with my approach?
My approach is:

  1. Separate the occurrences of 0 and 1 in two different vectors. For eg. 00100011 will be having VECTOR_1 as 2,3 and VECTOR_2 as 1,2
  2. Now I will count the number of times there are elements greater than 1 in each vector
  3. The vector in which there are less elements greater than 1 will be chosen to fully convert.

My solution : Solution

A simple approach is to divide the string into separate intervals of 0s and 1s, and then process these intervals such that we convert all intervals of 0s to 1 and vice versa. The interval which gives least number of operations will be the answer. Here’s the complete solution: Solution: 53728623 | CodeChef

1 Like

Bro , I also do the same thing , but it give me wrong answer . Can you please tell me the error ?
#include<bits/stdc++.h>

using namespace std;

#include

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(0);

int t;

cin>>t;

while(t--){

    string s;

    cin>>s;

    int count=0;

    vector<int> zeros,ones;

    int i=0;

    while(i<s.length()){

        if(s[i]=='1'){

            while(i<s.length() && s[i]=='1'){

                count++;

                i+=1;

            }

            i-=1;

            zeros.push_back(count);

            count=0;

        }

        else{

            while(i<s.length() && s[i]=='0'){

                count++;

                i++;

            }

            i-=1;

            ones.push_back(count);

            count=0;

        }

        ++i;

    }

    int con_zeros=0,con_ones=0;

    for(int a=0;a<ones.size();a++){

        if(ones[a]==1){

            con_ones++;

        }

        else if(ones[a]>1){

            con_ones+=2;

        }

    }

    for(int k=0;k<zeros.size();k++){

        if(zeros[k]==1){

            con_zeros++;

        }

        else if(zeros[k]>1){

            con_zeros+=2;

        }

    }

    cout<<min(con_zeros,con_ones)<<endl;

}

return 0;

}

You didn’t handle the case as mentioned in editorial Attempt3 section.

i guess my approach is passing attempt3 but not attempt 4

1 Like

phala maina sara 1 or 0 ko flip kia jiska asa pattern tha like for 101 → 111 and
for 010 → 000
phalabar array ko travers karka jitna bar asa flip kia uskA count kia count variable me.

iska bad jo array bacha usme no of blocks ko count kia
like 0111000111000 isme no of blocks ‘b’=5 and agar isme koi single eliment block rahata ha to ‘singel’ variable ko 1 se initilize kia otherwise 0 se
isme first block singel eliment ks ha islea ‘singel’=1

next step

if(b%2==0 && si==0)
cout<<count+b<<"\n";

else if(b%2==0 && si==1)

{
b=b-1;
cout<<count+(b/2)*2+si<<"\n";
}

else if(b%2 !=0 && si==0)
cout<<count+(b/2)*2<<"\n"; 

else {
b=b-1;
cout<<count+(b/2)*2<<"\n";
 }

example: 11101110001000
first step 11111110000000 count=2
2nd step b=2 , s=0
3rd step ans=2+2=4

example: 11101110001000110001101011001
first step 11111110000000110001111111001 count=4
2nd step b=7 , s=1
3rd step ans=4+(7/2)*2=10

this approch gives me correct ans for my every custom code but when i’m try to submit this shows wrong ans (^_ ^)

please help me to finding the mistack soluation:53831484

  • List item

please tell me what is wrong in this dp part … please sir

void solve(){
cin>>s;
N=(int)s.size();
vectorarr;
vectorss;
for(int i=0;i<N;){
int cnt=0;
char c=s[i];
while(i<N and s[i]==c){
cnt++;
i++;
}
ss.push_back(c-‘0’);
arr.push_back(cnt);
}

N=(int)arr.size();

vector<vector<int>>dp(N,vector<int>(2));
dp[0][ss[0]]=0;
dp[0][!ss[0]]=min(arr[0],(int)2);

for(int i=1;i<N;i++){
    dp[i][ss[i]]=dp[i-1][ss[i]];
    dp[i][!ss[i]]=dp[i-1][!ss[i]]+min((int)2,arr[i]);
    dp[i][!ss[i]]=min(dp[i][!ss[i]],dp[i-1][ss[i]]+2);
}
cout<<min(dp[N-1][0],dp[N-1][1])<<endl;

}

basically I first combined the group and then applied the dp equation on new array

Your code fails on 001101100 you r not considering the Attempt 2 part of Editorial in your DP. I made segment tree just to cover that .

2 Likes

can someone please tell what is wrong with my approach?
i maintained two separate counters for 1 and 0 and then calculated the total flips required for 0 to convert to 1 or vice versa and print whichever is less

time complexity O(|s|)

https://www.codechef.com/viewsolution/53805325

I find it useful for such problems to go subtask by subtask.

  1. First brute-force the smallest subtask, then generate a bunch of test cases and run the brute-force solution on them. Work through the results to observe and figure out the technique to arrive at the answer for each test case.
  2. Code the simplest implementation of this technique and solve the second subtask.
  3. Optimize the code and solve the final subtask.

thanks

Setter’s Solution is so self explanatory, Just traced the code by taking some testcases and understood the logic.
And even Editorial is so well prepared.
It’s like i’m thinking and making progress towards the AC solution.

Why this solution is giving wrong answer? Which test case I’m missing?

https://www.codechef.com/viewsolution/54043417

Consider the test input:

1
1100101001
1 Like

what does it means

It’s a for loop where the value of x at the start of the first iteration is the char 0 and its value at the start of the second (and final) iteration is 1.

Equivalent to:

for (char x = '0'; x <= '1'; x++)