CF 1678B2 - Tokitsukaze and Good 01-String (hard version)

Rating: 1800
Tags: dp, greedy, implementation
Solve time: 2m 49s
Verified: no

Solution

Problem Understanding

We are given a binary string of even length and asked to transform it into a "good" string. A good string is defined by two rules. First, if we break it into the minimum number of contiguous subsegments such that each subsegment contains only identical characters, every subsegment’s length must be even. Second, we want to perform the fewest number of bit flips to achieve this. Among all solutions with the minimal number of flips, we also need the configuration with the minimal number of subsegments.

In practical terms, the input gives us multiple test cases, each with a binary string. The output must give, for each string, the smallest number of changes needed and the corresponding minimal subsegment count. Because the sum of string lengths across all test cases can reach 200,000, any solution that scans the string more than