[Solution] Split The String solution codechef

Split The String solution codechef – For a binary string AA, let f(A)f(A) denote its badness, defined to be the difference between the number of zeros and number of ones present in it. That is, if the string has c0c0 zeros and c1c1 ones, its badness is |c0c1||c0−c1|. For example, the badness of “0101” is |11|=0|1−1|=0, the badness of “100100” is |21|=1|2−1|=1, the badness of “11011101” is |13|=2|1−3|=2, and the badness of the empty string is |00|=0|0−0|=0.

Table of Contents

[Solution] Split The String solution codechef

You are given an integer NN and a binary string SS.

You would like to partition SS into KK disjoint subsequences (some of which may be empty), such that the maximum badness among all these KK subsequences is minimized. Find this value.

Formally,

  • Let S1,S2,,SKS1,S2,…,SK be a partition of SS into disjoint subsequences. Every character of SS must appear in one of the SiSi. Some of the SiSi may be empty.
  • Then, find the minimum value of max(f(S1),f(S2),,f(SK))max(f(S1),f(S2),…,f(SK)) across all possible choices of S1,S2,,SKS1,S2,…,SK satisfying the first condition.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • The description of each test case is as follows:
    • The first line contains two space-separated integers NN and KK.
    • The second line contains the binary string SS of length NN.

[Solution] Split The String solution codechef

​For each test case, print the minimum possible value of the maximum badness when SS is partitioned into KK subsequences.

Constraints

  • 1T10001≤T≤1000
  • 1N21051≤N≤2⋅105
  • 1K1091≤K≤109
  • SS is a binary string, i.e, contains only the characters 00 and 11
  • The sum of NN across all test cases doesn’t exceed 21052⋅105

Sample Input 1 

3
7 5
1010100
4 1
1100
6 2
101111

Sample Output 1 

1
0
2

[Solution] Split The String solution codechef

Test case 11: Let’s take a couple of examples.

  • Suppose the partition is {10,10,0,10, }{“10″,”10″,”0″,”10″,” “}, obtained as 10101001010100 (elements of one color form a subsequence). The respective badness values are {0,0,1,0,0}{0,0,1,0,0}, the maximum of which is 11.
  • Suppose the partition is {101,00, ,10, }{“101″,”00″,” “,”10″,” “}, obtained as 10101001010100. The respective badness values are {1,2,0,0,0}{1,2,0,0,0}, the maximum of which is 22.

The first partition, with a maximum badness of 11, is one of the optimal partitions.

Test case 22: The only possible partition is {1100}{“1100”}, which has a badness of 00.

Test case 33: The partitions {1011,11}{“1011″,”11”} and {0111,11}{“0111″,”11”} both lead to a badness of max(2,0)=2max(2,0)=2, which is the minimum possible.

For Solution

Click Here

Leave a Comment