[Solution] Tokitsukaze and Good 01-String (hard version) | Codeforces Problem Solution 2022

[Solution] Tokitsukaze and Good 01-String (hard version) | Codeforces Problem Solution 2022 

B2. Tokitsukaze and Good 01-String (hard version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Solution Click Below:-  CLICK HERE

For example, if 𝑠$s$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are 2$2$, 2$2$, 4$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$3$, 2$2$, 2$2$, 3$3$. Obviously, "1110011000" is not good.

Tokitsukaze and All Zero Sequence Codeforces Solution

[Solution] Tokitsukaze and Good 01-String

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

Tokitsukaze and Strange Inequality Codeforces Solution

Tokitsukaze and Meeting Codeforces Solution

Tokitsukaze and Two Colorful Tapes Codeforces Solution

Tokitsukaze and Permutations Codeforces Solution

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≤𝑖≤𝑛$1\le i\le 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≤𝑡≤10000$1\le t\le 10000$) — the number of test cases.

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

Join Now for Solution:-