FlippingBitsDiv2

SRM 589 · 2013-06-25 · by snuke

SRM 589 · 2013-06-25 · by snuke · Dynamic Programming, Simple Math

Show categories

Class Name: FlippingBitsDiv2

Return Type: int

Method Name: getmin

Arg Types: (vector<string>, int)

Problem Statement

Goose Tattarrattat has a sequence B of bits. Tattarrattat also has a favorite positive integer M. M divides the number of bits in B.

Tattarrattat wants to have a sequence in which all the bits are 1s. She will produce such a sequence in a sequence of steps. In each step she can do one of the following three types of changes to the sequence:

Flip any bit (from 1 to 0 or from 0 to 1).
Flip the first k*M bits, for any positive integer k.
Flip the last k*M bits, for any positive integer k.

For example, suppose that B="110100001001" and M=4. There are 17 different sequences Tattarrattat can produce from this B in a single step. Among those sequences are "100100001001" (flipped the second bit), "001011111001" (flipped the first 2*M bits), and "110100000110" (flipped the last M bits).

You are given a String[] S and the int M. Concatenate all elements of S to obtain one long String. This String will represent the sequence B: each of its characters will be either '0' or '1'. Return the minimal number of steps required to obtain a sequence that consists of 1s only.

Constraints

S will contain between 1 and 50 elements, inclusive.
Each element of S will contain between 1 and 50 characters, inclusive.
Each character in each element of S will be '0' or '1'.
M will be between 1 and 2500.
M will be a divisor of N, where N is the number of characters in S.

Examples

{"00111000"}
1
Returns: 2

There are several optimal solutions. For example, she can flip the first 5*1 bits (obtaining "11000000") and then the last 6*1 bits (obtaining "11111111"). Another solution: she can flip the first 2*1 bits (obtaining "11111000") and then the last 3*1 bits (obtaining "11111111").

{"00111000"}
2
Returns: 3

{"111111"}
3
Returns: 0

This sequence already consists of 1s only, so no steps are necessary.

{"101100001101"}
4
Returns: 4

{"00100"}
5
Returns: 2

72)

{"00010","11010110","1010111","110001010","0110001100"
,"000110110","011010101","00","111","100"}
13
Returns: 31

Don't forget to concatenate the elements of S.

Submissions are judged against all 87 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FlippingBitsDiv2 with a public method int getmin(vector<string> S, int M) · 87 test cases · 2 s / 256 MB per case