[Solution] Tokitsukaze and Good 01-String (hard version) solution codeforces

Tokitsukaze and Good 01-String (hard version) solution codeforces – Tokitsukaze has a binary string 𝑠s of length 𝑛n, consisting only of zeros and ones, 𝑛n is even.

[Solution] Tokitsukaze and Good 01-String (hard version) solution codeforces

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 222244 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 33222233. 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 𝑠𝑖si to ‘0‘ or ‘1‘ (1𝑖𝑛1≤i≤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.

[Solution] Tokitsukaze and Good 01-String (hard version) solution codeforces

The first contains a single positive integer 𝑡t (1𝑡100001≤t≤10000) — the number of test cases.

For each test case, the first line contains a single integer 𝑛n (2𝑛21052≤n≤2⋅105) — 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 21052⋅105.

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.

Example
input

Copy
5
10
1110011000
8
11001111
2
00
2
11
6
100110

[Solution] Tokitsukaze and Good 01-String (hard version) solution codeforces

output

Copy
3 2
0 3
0 1
0 1
3 1
Note

In the first test case, one of the ways to make 𝑠s good is the following.

Change 𝑠3s3𝑠6s6 and 𝑠7s7 to ‘0‘, after that 𝑠s becomes “1100000000“, it can be divided into “11” and “00000000“, which lengths are 22 and 88 respectively, the number of subsegments of it is 22. There are other ways to operate 33 times to make 𝑠s good, such as “1111110000“, “1100001100“, “1111001100“, the number of subsegments of them are 224444 respectively. It’s easy to find that the minimum number of subsegments among all solutions with the minimum number of operations is 22.

In the second, third and fourth test cases, 𝑠s is good initially, so no operation is required.

For Solution

Click here

Leave a Comment