Bit Flipping solution codeforces – You are given a binary string of length 𝑛n. You have exactly 𝑘k moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped (00 becomes 11, 11 becomes 00). You need to output the lexicographically largest string that you can get after using all 𝑘k moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them.
[Solution] Bit Flipping solution codeforces
A binary string 𝑎a is lexicographically larger than a binary string 𝑏b of the same length, if and only if the following holds:
- in the first position where 𝑎a and 𝑏b differ, the string 𝑎a contains a 11, and the string 𝑏b contains a 00.
The first line contains a single integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of test cases.
Each test case has two lines. The first line has two integers 𝑛n and 𝑘k (1≤𝑛≤2⋅1051≤n≤2⋅105; 0≤𝑘≤1090≤k≤109).
The second line has a binary string of length 𝑛n, each character is either 00 or 11.
The sum of 𝑛n over all test cases does not exceed 2⋅1052⋅105.
[Solution] Bit Flipping solution codeforces
For each test case, output two lines.
The first line should contain the lexicographically largest string you can obtain.
The second line should contain 𝑛n integers 𝑓1,𝑓2,…,𝑓𝑛f1,f2,…,fn, where 𝑓𝑖fi is the number of times the 𝑖i-th bit is selected. The sum of all the integers must be equal to 𝑘k.
6 6 3 100001 6 4 100011 6 0 000000 6 1 111001 6 11 101100 6 12 001110
[Solution] Bit Flipping solution codeforces
111110 1 0 0 2 0 0 111110 0 1 1 1 0 1 000000 0 0 0 0 0 0 100110 1 0 0 0 0 0 111111 1 2 1 3 0 4 111110 1 1 4 2 0 4
Bit Flipping solution codeforces
Here is the explanation for the first testcase. Each step shows how the binary string changes in a move.
- Choose bit 11: 1⎯⎯00001→1⎯⎯111101_00001→1_11110.
- Choose bit 44: 1111⎯⎯10→0001⎯⎯011111_10→0001_01.
- Choose bit 44: 0001⎯⎯01→1111⎯⎯100001_01→1111_10.
The final string is 111110111110 and this is the lexicographically largest string we can get.