Flip or Compress FLIPCOMP Solution Codechef

Flip or Compress FLIPCOMP Solution

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

• Flip: Pick an index i (1≤i≤|S|) and flip the i-th character (i.e change 1 to 0 or 0 to 1). For e.g. 011–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–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.

Input Format

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

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 S equal.

Constraints

• 1≤T≤10⁵
• 1≤|S|≤10⁶
• S is a binary string.
• It is guaranteed that the sum of |S| over all test cases does not exceed 10⁶.

Subtasks

Subtask #1 (5 points):

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

Subtask #2 (20 points):

• 1≤T≤103
• 1≤|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−→−−−−compress 10–11
• 10–11−→−flip 11–11

In the second test case,

• 1110–011−→−flip 1111–011
• 11110–11−→−flip 11111–11

In the third test case,

• 00010–1110−→−flip 00011–1110
• 00011111––––––0−→−−−−compress 0001–0
• 0001–0−→−flip 0000–0

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

• Which Fuel is Cheaper CHEAPFUEL Solution
• Convex Hulk CONHULK Solution
• Functional Array FUNARR Solution
• Flip or Compress FLIPCOMP Solution
• Maximise the bridges MAXBRIDGE Solution
• Wildcard Replacement WLDRPL Solution
• Xor Equation XOREQN Solution
• Hill Sequence HILLSEQ Solution
• Weird Palindrome Making MAKEPAL Solution
• Equal Coins EQUALCOIN Solution Codechef