Flip to Invert Solution CodeChef | CodeChef Problem Solution 2022

Flip to Invert Solution CodeChef | CodeChef Problem Solution 2022

JJ has a binary string S$S$ of length N$N$. JJ can perform the following operation on S$S$:

• Select an i$i$ such that 1≤i≤N$1\le i\le N$, and flip Si$S_i$ (i.e. change 0$0$ to 1$1$ and 1$1$ to 0$0$)

JJ wants to minimize the number of inversions in S$S$ by performing the above operation at most K$K$ times. Can you help JJ do so?

Recall that a pair of indices (i,j)$(i,j)$ in S$S$ is called an inversion if i<j$i<j$ and Si>Sj$S_i>S_j$.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers N$N$ and K$K$ - the length of the binary string S$S$ and the maximum number of times JJ can perform the given operation.
• The second line of each test case contains a binary string S$S$ of length N$N$ containing 0$0$s and 1$1$s only.

Solution Click Below:- 

Output Format

For each test case, output the minimum number of inversions possible after performing the given operation at most K$K$ times.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 0≤K≤N$0\le K\le N$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
8 3
00010111
5 1
10100
6 2
111000

Sample Output 1 

0
2
3

Explanation

Test case 1: We are allowed to perform at most 3$3$ operations. We can perform the following operation on S$S$: 00010–111→00011111$0001\underset{\_}{0}111\to 00011111$ which has 0$0$ inversions. Therefore 0$0$ is the answer.

Test case 2: We can perform the following operation on S$S$: 1–0100→00100$\underset{\_}{1}0100\to 00100$ which has 2$2$ inversions. It can be proven that this is the minimum number of inversions possible.

Test case 3: We can perform the following operations on S$S$: 11100–0→111010–→111011$1110\underset{\_}{0}0\to 11101\underset{\_}{0}\to 111011$ which has 3$3$ inversions. It can be proven that this is the minimum number of inversions possible.

Chef And Division CodeChef Solution | CodeChef Problem Solution 2022 

Akash and Equal Mean Solution | CodeChef Problem Solution 

Flip to Invert Solution CodeChef 

Antipodal Points Solution

Join Now for Solution:- 

Best Coupon Solution | CodeChef Problem Solution 2022

Antipodal Points Solution | CodeChef Problem Solution 2022