[Solution] Bit Flipping solution codeforces

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 1111 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.
Input

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𝑛21051≤n≤2⋅1050𝑘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 21052⋅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.

Example
input

Copy
6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110

[Solution] Bit Flipping solution codeforces

output

Copy
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 111⎯⎯000011⎯⎯111101_00001→1_11110.
  • Choose bit 441111⎯⎯100001⎯⎯011111_10→0001_01.
  • Choose bit 440001⎯⎯011111⎯⎯100001_01→1111_10.

The final string is 111110111110 and this is the lexicographically largest string we can get.

 

For Solution

Click here

Leave a Comment