Flip or Compress FLIPCOMP Solution Codechef

Flip or Compress FLIPCOMP Solution

You are given a binary string SS. You can perform the following operations on SS:

  • Flip: Pick an index ii (1≤i≤|S|)(1≤i≤|S|) and flip the ii-th character (i.e change 11 to 00 or 00 to 11). For e.g. 011–001→010–001011_001→010_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. 1001111–––––10→1001–101001111_10→1001_10

You want to make all the characters of the binary string equal (i.e. either all characters are 00 or all characters are 11). Find the minimum number of operations required to do so.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains a binary string SS.

Output Format

For each test case, output a single line containing one integer – the minimum number of operations required to make all the characters of SS equal.

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤|S|≤1061≤|S|≤106
  • SS is a binary string.
  • It is guaranteed that the sum of |S||S| over all test cases does not exceed 106106.

Subtasks

Subtask #1 (5 points):

  • 1≤T≤1031≤T≤103
  • 1≤|S|≤101≤|S|≤10

Subtask #2 (20 points):

  • 1≤T≤1031≤T≤103
  • 1≤|S|≤501≤|S|≤50

Subtask #3 (75 points):

  • Original constraints

Sample Input 1 

3
100011
1110011
000101110

Sample Output 1 

2
2
3

Explanation

In the first test case,

  • 1000––––11−→−−−−compress10–111000_11→compress10_11
  • 10–11−→−flip11–1110_11→flip11_11

In the second test case,

  • 1110–011−→−flip1111–0111110_011→flip1111_011
  • 11110–11−→−flip11111–1111110_11→flip11111_11

In the third test case,

  • 00010–1110−→−flip00011–111000010_1110→flip00011_1110
  • 00011111––––––0−→−−−−compress0001–000011111_0→compress0001_0
  • 0001–0−→−flip0000–0

Flip or Compress FLIPCOMP Solution is updated. Click Below

SOLUTION

Program Python: Flip or Compress FLIPCOMP Solution in Python

# cook your dish here
for _ in range(int(input())):
    s=input()
    v,ans,n=0,0,len(s)
    i=0
    flag=flag2=False
    while i<n:
        if s[i]=='0':
            if not flag:
                flag=True
            else:
                if not flag2:
                    flag2=True

        else:
            if flag:
                if flag2:
                    if i<n-1:
                        if s[i+1]=='0':
                            ans+=1
                        else:
                            ans+=2
                            flag=False
                            flag2=False
                    else:
                        ans+=2
                        flag=False
                        flag2=False
                else:
                    ans+=1
                    flag=False
        i+=1
    if flag:
        if flag2:
            ans+=2
        else:
            ans+=1
    v=ans
    ans=0
    i=0
    flag=flag2=False
    while i<n:
        if s[i]=='1':
            if not flag:
                flag=True
            else:
                if not flag2:
                    flag2=True

        else:
            if flag:
                if flag2:
                    if i<n-1:
                        if s[i+1]=='1':
                            ans+=1
                        else:
                            ans+=2
                            flag=False
                            flag2=False
                    else:
                        ans+=2
                        flag=False
                        flag2=False
                else:
                    ans+=1
                    flag=False
    
        i+=1
    if flag:
        if flag2:
            ans+=2
        else:
            ans+=1
    v=min(v,ans)
    print(v)

Program C++: Flip or Compress FLIPCOMP Solution in C++

#include <iostream>
using namespace std;

int main() {
    int t; cin >> t;
    
    while(t--){
        string s; cin >> s;
        
        int zer = 0;
        string sd = s;
        for(int i=1; i+1<s.length(); i++){
            if(sd[i]=='1' && sd[i-1]=='0' && sd[i+1]=='0' && ((i-2>=0 && sd[i-2]=='0') || (i+2<s.length() && sd[i+2]=='0'))){
                zer++;
                sd[i] = '0';
            }
        }
        
        for(int i=0; i<s.length(); i++){
            if(sd[i]=='0' && i>1 && sd[i-1]=='0' && sd[i-2]=='0')continue;
            else if(sd[i]=='0' && i>0 && sd[i-1]=='0')zer++;
            else if(sd[i]=='0')zer++;
        }
        
        int one = 0;
        sd = s;
        for(int i=1; i+1<s.length(); i++){
            if(sd[i]=='0' && sd[i-1]=='1' && sd[i+1]=='1' && ((i-2>=0 && sd[i-2]=='1') || (i+2<s.length() && sd[i+2]=='1'))){
                one++;
                sd[i] = '1';
            }
        }
        for(int i=0; i<s.length(); i++){
            if(sd[i]=='1' && i>1 && sd[i-1]=='1' && sd[i-2]=='1')continue;
            else if(sd[i]=='1' && i>0 && sd[i-1]=='1')one++;
            else if(sd[i]=='1')one++;
        }
        
        cout << min(zer, one) << "\n";
    }
 // your code goes here
 return 0;
}

November Long Challenge 2021 Solution

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

Leave a Comment