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 22, 22, 44 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 33, 22, 22, 33. 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≤𝑛≤2⋅1052≤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 2⋅1052⋅105.
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.
5 10 1110011000 8 11001111 2 00 2 11 6 100110
[Solution] Tokitsukaze and Good 01-String (hard version) solution codeforces
3 2 0 3 0 1 0 1 3 1
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 22, 44, 44 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.