Tokitsukaze and Good 01-String (hard version) (Codeforces 1678B2)
Tags: Greedy, dp

This is the hard version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.Tokitsukaze has a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones, $$$n$$$ is even.Now Tokitsukaze divides $$$s$$$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $$$s$$$ is considered good if the lengths of all subsegments are even.For example, if $$$s$$$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $$$2$$$, $$$2$$$, $$$4$$$ respectively, which are all even numbers, so "11001111" is good. Another example, if $$$s$$$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $$$3$$$, $$$2$$$, $$$2$$$, $$$3$$$. Obviously, "1110011000" is not good.Tokitsukaze wants to make $$$s$$$ good by changing the values of some positions in $$$s$$$. Specifically, she can perform the operation any number of times: change the value of $$$s_i$$$ to '0' or '1' ($$$1 \leq i \leq n$$$). Can you tell her the minimum number of operations to make $$$s$$$ good? Meanwhile, she also wants to know the minimum number of subsegments that $$$s$$$ can be divided into among all solutions with the minimum number of operations.

Input: The first contains a single positive integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of $$$s$$$, it is guaranteed that $$$n$$$ is even.The second line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print a single line with two integers — the minimum number of operations to make $$$s$$$ good, and the minimum number of subsegments that $$$s$$$ can be divided into among all solutions with the minimum number of operations.

Note: In the first test case, one of the ways to make $$$s$$$ good is the following.Change $$$s_3$$$, $$$s_6$$$ and $$$s_7$$$ to '0', after that $$$s$$$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $$$2$$$ and $$$8$$$ respectively, the number of subsegments of it is $$$2$$$. There are other ways to operate $$$3$$$ times to make $$$s$$$ good, such as "1111110000", "1100001100", "1111001100", the number of subsegments of them are $$$2$$$, $$$4$$$, $$$4$$$ respectively. It's easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is $$$2$$$.In the second, third and fourth test cases, $$$s$$$ is good initially, so no operation is required.

Sample Inputs:
5
10
1110011000
8
11001111
2
00
2
11
6
100110

Sample Outputs:
3 2
0 3
0 1
0 1
3 1

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    s = input()
    ans1 = 0
    ans2 = 0
    ans = ''
    last = '!'
    for i in range(0, n, 2):
        if s[i] != s[i + 1]:
            ans1 += 1
        elif s[i] != last:
            ans2 += 1
            last = s[i]
    if ans2 == 0:
        ans2 += 1
    print(ans1, ans2)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    s = input()
    ans1 = 0
    ans2 = 0
    ans = ''
    last = '!'
    for i in range(0, n, 2):
        if s[i] != s[i + 1]:
            ans1 += 1
        elif s[i] != last:
            ans2 += 1
            last = s[i]
    if ans2 == 0:
        ans2 += 1
    print(ans1, ans2)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
from array import array

def solve():
    n = int(input())
    s = list(input().rstrip())
    count = 0
    minSegs = 0
    LAST = -1
    for i in range(0, len(s), 2):
        if s[i] != s[i + 1]:
            count += 1
        else:
            minSegs += s[i] != LAST
            LAST = s[i]
    return (count, max(minSegs, 1))
for _ in range(int(input())):
    print(*solve())