CF 1530G - What a Reversal
We are given two binary strings, a and b, of the same length n and an integer k. Our goal is to transform a into b by repeatedly reversing substrings of a that contain exactly k ones. Each reversal can involve any number of zeros.
Rating: 3300
Tags: constructive algorithms
Solve time: 49s
Verified: no
Solution
Problem Understanding
We are given two binary strings, a and b, of the same length n and an integer k. Our goal is to transform a into b by repeatedly reversing substrings of a that contain exactly k ones. Each reversal can involve any number of zeros. The output should either be a sequence of reversals or -1 if the transformation is impossible within the specified limit.
The problem is constructive, but it has a subtle constraint: we cannot arbitrarily move ones. We can only reverse blocks containing exactly k ones. This means we need to think in terms of the positions of ones