Tokitsukaze and Good 01-String (hard version)
Contest: Codeforces Round 789 (Div. 2)
Difficulty rating: 1800
Tags: dp, greedy, implementation

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
5
10
1110011000
8
11001111
2
00
2
11
6
100110

Example output:
3 2
0 3
0 1
0 1
3 1

Editorial:
B（Greedy）
Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $$$0$$$ or $$$1$$$. In other words, the string is divided into many adjacent binaries with length of $$$2$$$. If the binary is "01" or "10", it needs $$$1$$$ operation, otherwise the operation is not required.
If you want to minimize the number of "contiguous segments", a simple greedy way is to change each "binary requiring operation" (i.e. $$$01$$$ or $$$10$$$) into the form of the previous or next "binary requiring no operation" (i.e. $$$11$$$ or $$$00$$$). For example: "0010" change to "0000" and "1101" change to "1111". In this way, this "binary requiring operation" has no contribution to the final number of contiguous segments. We only need to count the number of contiguous "11 "and "00" binaries.
In particular, if all binaries are "01" or "10", the final contribution to the number of final contiguous segments is $$$1$$$ in total.
B(State compression DP)
Obviously, the operation is, for each pair of adjacent and unequal characters, change both of them to $$$0$$$ or $$$1$$$. In other words, the string is divided into many adjacent binaries with length of $$$2$$$.
Consider the recursion from the front to the back, it can be observed that the previously maintained prefix must end with "00" or "11". Therefore, it's necessary to convert each divided binary into "00" or "11" by enumerating the cost of changing the current binary into "00" and "11". Maintain the minimum number of operations in the process of DP, try to make the current string consistent with the end of the prefix subsegment.
$$$dp[n][2]$$$, set the first dimension as the maintained length of prefix and the second dimension as the suffix state of the prefix.
Then the DP transfer equation is:
$$$dp[i][0]=min(dp[i-2][0]+\left \{c_0,0\right \},dp[i-2][1]+\left \{c_1,1\right \})$$$
$$$dp[i][1]=min(dp[i-2][0]+\left \{c_0,1\right \},dp[i-2][1]+\left \{c_1,0\right \})$$$
where $$$c_k$$$ represents the cost of converting the current binary to "kk".