I Might Be Wrong (Codeforces 1693F)
Tags: Greedy, two pointers

You are given a binary string $$$S$$$ of length $$$n$$$ indexed from $$$1$$$ to $$$n$$$. You can perform the following operation any number of times (possibly zero):Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Let $$$cnt_0$$$ be the number of times 0 occurs in $$$S[l \ldots r]$$$ and $$$cnt_1$$$ be the number of times 1 occurs in $$$S[l \ldots r]$$$. You can pay $$$|cnt_0 - cnt_1| + 1$$$ coins and sort the $$$S[l \ldots r]$$$. (by $$$S[l \ldots r]$$$ we mean the substring of $$$S$$$ starting at position $$$l$$$ and ending at position $$$r$$$)For example if $$$S = $$$ 11001, we can perform the operation on $$$S[2 \ldots 4]$$$, paying $$$|2 - 1| + 1 = 2$$$ coins, and obtain $$$S = $$$ 10011 as a new string.Find the minimum total number of coins required to sort $$$S$$$ in increasing order.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of $$$S$$$.The second line of each test case contains a binary string $$$S$$$ of $$$n$$$ characters $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 or $$$S_i = $$$ 1 for each $$$1 \le i \le n$$$)It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the minimum total number of coins required to sort $$$S$$$ in increasing order.

Note: In the first test case, $$$S$$$ is already sorted.In the second test case, it's enough to apply the operation with $$$l = 1, r = 2$$$.In the third test case, it's enough to apply the operation with $$$l = 1, r = 2$$$.

Sample Inputs:
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000

Sample Outputs:
0
1
1
3
2
2
5

Solution (Python):
def findPrevGreater(arr):
    if not arr:
        return []
    s = list()
    ans = []
    for i in range(len(arr)):
        while s:
            if arr[s[-1]] >= arr[i]:
                ans.append(s[-1])
                break
            else:
                s.pop()
        if not s:
            ans.append(-1)
        s.append(i)
    return ans

def solve():
    n = int(input())
    s = [bool(int(x)) for x in input()]
    b = 0
    for i in range(n):
        if s[i]:
            b += 1
        else:
            b -= 1
    if b < 0:
        s = [not x for x in s]
        s.reverse()
        b = -b
    cs = [1 if x else -1 for x in s]
    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] + cs[i - 1]
    prev = findPrevGreater(pref)
    i = n
    while i > 1 and pref[i] > pref[i - 1]:
        i -= 1
    j = i
    for k in range(i, -1, -1):
        if pref[k] == pref[i] and prev[k] == -1:
            j = k
            break
    ans = 0
    while i != 1:
        ans += 1
        if pref[i] <= 0:
            break
        for k in range(j + 1, (i + j) // 2 + 1):
            s[k - 1] = False
            pref[k] = pref[j] - (k - j)
        for k in range((i + j) // 2 + 1, i + 1):
            s[k - 1] = True
            pref[k] = pref[j] + (k - (i + j) // 2)
        i -= 1
        while i > 1 and pref[i] > pref[i - 1]:
            i -= 1
        for k in range(j - 1, -1, -1):
            if pref[k] == pref[i] and prev[k] == -1:
                j = k
                break
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
inf = float('inf')
buffer = open(1, 'w', 10 ** 6)

def print(*args, sep=' ', end='\n'):
    buffer.write(sep.join((str(arg) for arg in args)) + end)

def flush():
    buffer.flush()

def read_ints(index=None):
    return [int(x) for x in input().split()]

def read_ints_indexed(index):
    return [(int(x), i + index) for (i, x) in enumerate(input().split())]

def findPrevGreaterOrEqual(arr):
    if not arr:
        return []
    s = list()
    ans = []
    for i in range(len(arr)):
        while s:
            if arr[s[-1]] >= arr[i]:
                ans.append(s[-1])
                break
            else:
                s.pop()
        if not s:
            ans.append(-1)
        s.append(i)
    return ans

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

def solve():
    n = int(input())
    s = [bool(int(x)) for x in input()]
    b = 0
    for i in range(n):
        if s[i]:
            b += 1
        else:
            b -= 1
    if b < 0:
        s = [not x for x in s]
        s.reverse()
    cs = [1 if x else -1 for x in s]
    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] + cs[i - 1]
    prev = findPrevGreaterOrEqual(pref)
    i = n
    while i > 0 and pref[i] > pref[i - 1]:
        i -= 1
    j = i - 1
    for k in range(i, -1, -1):
        if pref[k] == pref[i] and prev[k] == -1:
            j = k
            break
    ans = 0
    while pref[i] > 0:
        ans += 1
        for k in range(j + 1, (i + j) // 2 + 1):
            s[k - 1] = False
            pref[k] = pref[j] - (k - j)
        for k in range((i + j) // 2 + 1, i + 1):
            s[k - 1] = True
            pref[k] = pref[j] + (k - (i + j) // 2)
        i -= 1
        while i > 0 and pref[i] > pref[i - 1]:
            i -= 1
        for k in range(j - 1, -1, -1):
            if pref[k] == pref[i] and prev[k] == -1:
                j = k
                break
    if is_sorted(s):
        print(ans)
    else:
        print(ans + 1)
if __name__ == '__main__':
    test_cases = int(input())
    for _ in range(test_cases):
        solve()

Solution (Python):
import sys
inf = float('inf')
buffer = open(1, 'w', 10 ** 6)

def print(*args, sep=' ', end='\n'):
    buffer.write(sep.join((str(arg) for arg in args)) + end)

def flush():
    buffer.flush()

def read_ints(index=None):
    return [int(x) for x in input().split()]

def read_ints_indexed(index):
    return [(int(x), i + index) for (i, x) in enumerate(input().split())]

def findPrevGreaterOrEqual(arr):
    if not arr:
        return []
    s = list()
    ans = []
    for i in range(len(arr)):
        while s:
            if arr[s[-1]] >= arr[i]:
                ans.append(s[-1])
                break
            else:
                s.pop()
        if not s:
            ans.append(-1)
        s.append(i)
    return ans

def is_sorted(arr):
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True

def solve():
    n = int(input())
    s = [bool(int(x)) for x in input()]
    b = 0
    for i in range(n):
        if s[i]:
            b += 1
        else:
            b -= 1
    if b < 0:
        s = [not x for x in s]
        s.reverse()
    cs = [1 if x else -1 for x in s]
    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] + cs[i - 1]
    prev = findPrevGreaterOrEqual(pref)
    i = n
    while i > 0 and pref[i] > pref[i - 1]:
        i -= 1
    j = i - 1
    for k in range(i, -1, -1):
        if pref[k] == pref[i] and prev[k] == -1:
            j = k
            break
    ans = 0
    while pref[i] > 0:
        ans += 1
        for k in range(j + 1, (i + j) // 2 + 1):
            s[k - 1] = False
            pref[k] = pref[j] - (k - j)
        for k in range((i + j) // 2 + 1, i + 1):
            s[k - 1] = True
            pref[k] = pref[j] + (k - (i + j) // 2)
        i -= 1
        while i > 0 and pref[i] > pref[i - 1]:
            i -= 1
        for k in range(j - 1, -1, -1):
            if pref[k] == pref[i] and prev[k] == -1:
                j = k
                break
    if is_sorted(s):
        print(ans)
    else:
        print(ans + 1)
if __name__ == '__main__':
    test_cases = int(input())
    for _ in range(test_cases):
        solve()