Connection Status:
Competition Arena > FlippingBitsDiv1

FlippingBitsDiv1

SRM 589 · 2013-06-25 · by snuke

SRM 589 · 2013-06-25 · by snuke · Brute Force, Dynamic Programming, Search, String Manipulation
Class Name: FlippingBitsDiv1
Return Type: int
Method Name: getmin
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Goose Tattarrattat has a sequence B of bits. The length of the sequence is N. Tattarrattat also has a favorite integer M which is between 1 and N, inclusive.


A sequence of N bits is called a rotator sequence if it has the following property: its prefix of length N-M is equal to its suffix of length N-M.


For example, let M=2. Consider the sequence B="10101010". Its length is N=8, so we have N-M=6. The prefix of length 6 is "101010", the suffix of length 6 is "101010". They are the same, so this B is a rotator sequence. Now consider B="11010100". For this B we compare the prefix "110101" to the suffix "010100". They differ, so this B is not a rotator sequence.


Tattarrattat wants to change her sequence B into some rotator sequence. She will produce such a sequence in a sequence of steps. In each step she can do one of the following two 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.

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 some rotator sequence.

Constraints

  • S will contain between 1 and 6 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 N, where N is the total number of characters in S.
Examples
0)
{"00111000"}
1
Returns: 2

An optimal solution: she can flip the first 2*1 bits to obtain "11111000", and then flip the first 5*1 bits to obtain "00000000" which is a rotator sequence.

1)
{"101100001101"}
3
Returns: 2
2)
{"11111111"}
4
Returns: 0
3)
{"1101001000"}
8
Returns: 1
4)
{"1","10","11","100","101","110"}
5
Returns: 4

Don't forget to concatenate the elements of S.

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

Coding Area

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

Submitting as anonymous