Statistics

Problem Statement for "FlippingBitsDiv1"

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.

Definition

Class:
FlippingBitsDiv1
Method:
getmin
Parameters:
String[], int
Returns:
int
Method signature:
int getmin(String[] S, int M)
(be sure your method is public)

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

  1. {"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.

  2. {"101100001101"}

    3

    Returns: 2

  3. {"11111111"}

    4

    Returns: 0

  4. {"1101001000"}

    8

    Returns: 1

  5. {"1","10","11","100","101","110"}

    5

    Returns: 4

    Don't forget to concatenate the elements of S.

  6. {"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}

    206

    Returns: 0

  7. {"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}

    1

    Returns: 0

  8. {"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}

    300

    Returns: 0

  9. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    273

    Returns: 0

  10. {"00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}

    5

    Returns: 0

  11. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    1

    Returns: 0

  12. {"11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111","11111111111111111111111111111111111111111111111111"}

    16

    Returns: 0

  13. {"01101100110000111101000100011001000000010100100100","10011111000110010001100111000101111001011100111010","00111111000100001101101010011001001001001111100111","01111110011010000111001101011111111101011011001010","10010001010001110000101101100100101101000111011111","10111101101111101011011011010100111011100001101001"}

    17

    Returns: 104

  14. {"11010100101001001111111111110111000101111010011100","11000110110110100101111010101000001010100000110011","11100101001111110010011101101100101011101101011110","10001011100000000011111110011110100110101111010011","10101010100100010101100110111100010000001111110100","00100101100111100100000100000001111000111001100011"}

    13

    Returns: 107

  15. {"00011001111001011100010010010111000100001010111011","10110000101101001110101101110110011101100001010100","11101000100100010011110100100110101111000000011111","00011111000001100000100010011011100010010100010001","00110000100000101010101010000001011010111001011111","01100001111111000001010001000011010001001101100010"}

    3

    Returns: 106

  16. {"01100010010101100000000110001010111001001000111100","10010001100101100110100001110010111110000010000111","01110111001010111000111101001001111101010110100101","00110011101110001000111001011011110101111110111111","10011101010001001000101011110010111000100001100000","10110001110001011010101101101111101001000101011001"}

    18

    Returns: 106

  17. {"11101101110110001011101011000010001111101111111010","11011110011111001000010100011001001111100111110011","00010011000000010100001010010111110011111111101001","01111001110100101101010110010001100100110001100101","10010100100101000011111100000111001010110111001100","01011000101011111110001001110011111111010111001001"}

    8

    Returns: 107

  18. {"01010100011100111011100010011110011100111001010100","11111110000010010110011001111000100101001101100111","10011101001000000110101100000111110000011100111010","00101000010100111100010111110011111100011001010111","11111101000110101001110010011010110001111110110011","10000001011101010001101101000110100000101001000000"}

    2

    Returns: 111

  19. {"10111111001010011110010010110011101010111110001101","10111000110010100000001000010011010100111010101101","00101000010011100011110110100001100000101110011100","11110100101010110100000000100111000111110101010000","11010111110101100101000110011100110100011010100101","01011001111010000001000100010100000100010110100011"}

    1

    Returns: 105

  20. {"01100100010100110000111010110100111110000001001100","10001101000101100010011001100000110101110100011111","11110011010001110101100010010001111110110110011100","10001011001101010010100001011010101101000011100010","11101110000111001110010110010011110110111010001111","10011000011110101100001101000101110011010010110011"}

    1

    Returns: 108

  21. {"10010110001010100011111111101110110111001100010011","11001010111001011111110011000000110101011111010110","10101100110000011010000010000100000001111101101011","10100011011100001010100001011001010101001110010110","11001111100110001101110100010001100000010011000001","11000101011001111100000111000010000010101011000110"}

    11

    Returns: 110

  22. {"11000011101011011001000000110110110001001111000000","11010000101001011000010111111011100111000001100101","10000001110101100100001000110111101100000010011000","01100100111100001011000000101100100111001011101011","10001011101110000111010010100100000100001111111101","01101100011111001011110100010101000101110010011000"}

    6

    Returns: 113

  23. {"01001010110101011110001010000110000001010101001011","00111011011101101010001101010100011011101110000100","01010110110110101101100001010001111000110001010010","00111101111100110101000111011010001111001111111111","00010101001100010001110010000100001111110110001010","01101000101011101101001101110000001011001111001001"}

    16

    Returns: 109

  24. {"11101101111101011100001000010110010000010111010111","00011101101001101001011000101101111000101111110111","11011111101011101001101110001111001001100110010110","00110111111110111101010011100010100001101011101100","01000101000000111111011101010000111110110100001111","00001011111110100111100011111101000110111011100010"}

    13

    Returns: 109

  25. {"10110011001001101010111001111000010010111111001000","10010111011110101111111101110010100010100001011101","01001011101001111011100100000101000000010011111111","11100101101001111110100001011010101111010001001111","00111110101001101011111111111000111101011011001101","11011101010111000011101100000110001000010011000011"}

    11

    Returns: 106

  26. {"11100011100001101101101100111111010010010000110101","10100110010000100011100010100000000110110100110010","11110000000100110011000010001001111111001001111110","01001011100110101100011001010001001011100001101000","01101111000110110001010101101111011000010111011001","11010110111011000000101110110011010001100100000110"}

    8

    Returns: 111

  27. {"11001110111010110110111100101100100100000001100011","01100110111100001001000110011100100011111001001100","01100100000111100111100101010000111001110111000101","01111011110001010111110100000000101100101010001001","01110000100001100101100011010011001101010110100001","11101001111000010100010110100101000100011101100011"}

    11

    Returns: 110

  28. {"10100101000011101011101001000011000100100000000000","00100000110011011101101010000001110101011110011010","01001010110110001111000111111110101011011010001001","11011101000010001010010011010000001011101011000000","11100100011101001111100001011001100010110100000001","10010001010010101011101101110001011101111000111101"}

    172

    Returns: 54

  29. {"11100110110010011011011101101101000111100111100100","10011010101110000110110000101010110100010010010101","11100101111010001000101111000100010001101110111110","10010100110001001100000001011011100100011010110100","00101100100011010100101001001011100111111011100000","01100000001101010010000000010000110110101000111000"}

    148

    Returns: 71

  30. {"01011001110100011010010110010011101011111110001000","00100001111111110111110110101100011111001111011001","11100100001001100001101111101000111001111110001000","11101001100011000111010100110000011100011011101100","01011111011101111001110001111000100001001110001011","00101001111011001010100101010001000010011101110101"}

    283

    Returns: 8

  31. {"10100111001000011111111100011110110100011111000111","01110001010100000001001101110001111001010000100101","10101111010101111011111100000010011011100111010110","11010011110001111111000100010100100001100100000010","11011011011100011101011110101001110100010011101110","11111110000100011110001011010110001101101110100111"}

    99

    Returns: 75

  32. {"11100011110101000111000111100110110010000010110101","01101101011101100011000111100101100001000000011000","10101011100010100010101110111000101101001111111011","00000011001010010001110010000100001011000111100010","10011001100101101101111010100000100101010011101010","00001010100101100101101010001100100000000111001001"}

    59

    Returns: 87

  33. {"11011111110101000110000010000011001100111001111011","10001001100011000000000101110101010011100011000011","00101110101001110010011011100100100000111111000110","00111001100011100111001100111100000010111010010100","11111101010010101100110100101110110110001010011101","01000010101101101111110011101100111111000011000101"}

    256

    Returns: 18

  34. {"10101110011011000011111010111110010001001111101011","11100111101101001000101010101000100000110001010011","01111001100001110011101001011111110011101010111000","01101000000010110110011110011010111000100101101010","10001111101111101100000110111111110111011010010011","00011101100000010010011100001010010010100111010101"}

    162

    Returns: 63

  35. {"00010111111001100100111100100110100010010100011111","11000111100100110110111000101011010101100010011111","10011011101001100011100001000101101111000111110011","10111110110101111100101010101100010100000001101001","10000011101010100100100100001110111010000101011100","01010111010010110111010110011100001110101110110100"}

    200

    Returns: 42

  36. {"10000111100011100000100000001101010111110001011110","01001101101100101101001111110111100001011110111011","01100010111100111010110011001100100000010111111010","00101111000101011111111001111010100010101010111011","01001000001110010111001001000101111110011101111101","10000000011010110101100000011100011110101111110011"}

    242

    Returns: 27

  37. {"00101111101011101110001000101100011001101110010110","11111101100001001000110000001001000001111001100000","01010001010100110100001001011110101010110001110110","10000100010011011001000100100100101000100011001101","01101001011101000001110111101110110001111000101100","10101110000001010010101101010000110000110110100111"}

    85

    Returns: 74

  38. {"11001111110100000010100011100010100010100011111001","10000110110011111011111011011110010100111110100111","10010011001101000010001100010100011101101001101000","11010111111011011101011101111011011001001110101100","00010011000101100100111000110101110101100000110100","01011010001100001111001110000111101110010001011000"}

    187

    Returns: 55

  39. {"11110111100000110111000100111001110000111101100011","10100001001001100100000111110111101010011111000111","01101100001111000101111111001011110000010010100110","11101011100100000011010011011011000010101110110001","01001011101110010100111111001010100011101011000000","01010111101011110110011011111101010010101001100011"}

    192

    Returns: 51

  40. {"00101100110110010010110000010111100001101111000101","10101100100100101110000100011011101110111100111011","11011010111100110101001000111111100011100110101100","10111010011100000110000011011110000100111011110001","01111010111101110011001001000100111001110110101111","11000001001011110000011100101101111111001011001100"}

    48

    Returns: 93

  41. {"10111000100010010011011100010100010001111011100010","10101111000100000011110101000010100101010001011110","00110100111001010110100111001111110000000010111110","11011100101101010111101110111000011110100111011001","00010101001111101010100100011111111110001110001111","11010001001110001101111011001110011111000110100111"}

    278

    Returns: 9

  42. {"10111100100100110100100110010000001010011000101011","10110110110111111011011011001101111110001111100110","11000101011010100111111110011010011111001011111010","00110000101110100110000011101101001001101011101001","01100011000111101000111000100110000111000110011110","11000110011100001101000011100000101110000100001110"}

    179

    Returns: 60

  43. {"1111110010001001011000","100100110001000010110010011111001","10111101010110000101101101101001110001001000","1110100101010111001110010110000001110","11010011110000","00110010011001101101101110"}

    7

    Returns: 56

  44. {"10011101010000011111100111000011010001","00011110111001101111100001110111100110001101001","11110000111111","10011000101100101110001","1110010011000110110001000100000010111","011011100111001011010101110000"}

    4

    Returns: 70

  45. {"1101100000001100111101001000011111001011100","101","010010111010","111000110101101111011001110111000001001000000000","100101101000000110101011101011111011100","01"}

    20

    Returns: 44

  46. {"0000","110000001000010","1100110011101000","11110000100010","11001011001111101010111110101010001000000","100101100100110"}

    9

    Returns: 35

  47. {"00001101100100011000110111011100111","11001011111000111010000100011101001","01100001100101000111010101001100111001101100","00010101110011001111100110111011100111100001","01011010000011101100","101101010000100101001100"}

    17

    Returns: 69

  48. {"11101010010101011111","110001100010000000111110010000111010001111111","10111100100101","0011100111101011001100100111000001","10001010011010000","1100000010001011101101100010001"}

    9

    Returns: 53

  49. {"0000010100001011010011011","011101","0111011110000001100110000111","100111000100011110100010110111011","110000010001001100000","1111111"}

    1

    Returns: 35

  50. {"100","101101110000011101110000110011100","01101110101110000001101110010111111","0010110010110110000011100010110110001011101","0100","00101010000111001110001100"}

    1

    Returns: 50

  51. {"0111111111111110000111110111000111111111100100","10100111","0100111110100111100010001001010000000101111010001","011","00010110111100011010000111","000101001111010011101101111010001111000110"}

    13

    Returns: 49

  52. {"0000001111101110111001011101100001100","1110001010101111101011101001001010100101111110","1100101010000101001001","010101110","01000011","10001001101000001010010011100101010100110101101"}

    11

    Returns: 60

  53. {"0110101100000000110111110110","1000001010110001010011001110001111111","10111000110010111101011001010110000","100000001100010","10001000001000","000000001101100000000000"}

    64

    Returns: 37

  54. {"0001111000001010101001101","001101000011101100","0010001100110001100101001011110101100110101","0111101000","011010110011100010001001010001010010111101000","00101000100010"}

    12

    Returns: 51

  55. {"11100110011010000110110010001","1100100000001100011110110001101000110","101000000101","01011001001101111110","0010001","010100110100010110101110011101001010"}

    40

    Returns: 39

  56. {"10011110011110111010111000010011000110111111001011","011001100110101111010000010110011100010100","0","110010100000101101101000111001111","0010100101101","001100001010011101100001110001100011"}

    70

    Returns: 36

  57. {"00","0011110011101011000001110","010000010100101010110101000011111011100101","000010100110001110101010001110","01111000001100010101001010101","01011100000000101011001100111111001010110"}

    27

    Returns: 53

  58. {"1001111001000001110010011101100101","0100000000010011101","00010011000101001111101110001100001100","1110111111000100001011","00100","110110111000000100110011001110010100100111011"}

    49

    Returns: 37

  59. {"0111001001101001110001001110100000001011","10000001110","0111001101","11000011100110","001000110011010011011","110111011010000000110"}

    89

    Returns: 10

  60. {"0001","10110100100010011011000","001111100010110001001011110000110110000100011","0100111011","101100110101000100010100001000001","100010000000010000010001100100001"}

    145

    Returns: 1

  61. {"000010111000101101","01011011000001010001101010000100011011110","11000010100","00","110100000010010111110010110100101001010110","1000100001101110100110111"}

    18

    Returns: 42

  62. {"111011001010011100000101","101001100111111100000010101","01111000110011100011101100111111000100000100010","01111110110100110001","100000101001100","010001100011111011000000111110011000111110001100"}

    91

    Returns: 34

  63. {"1001011000101010001111111110111011011100110001001"}

    2

    Returns: 16

  64. {"00011100011100000000000000000" }

    3

    Returns: 4

  65. {"1001011000101010001111111110111011011100110001001", "100101100010101000111111110111011011100110001001", "100101100010101000111111111011101101100110001001", "100101000101010001111111110111011011100110001001", "100101100010101000111111111011101101110011000101" }

    60

    Returns: 69

  66. {"00000000010000000001000000000100000000010000000001", "00000000010000000001000000000100000000010000000001", "00000000010000000001000000000100000000010000000001", "00000000010000000001000000000100000000010000000001", "00000000010000000001000000000100000000010000000001", "00000000010000000001000000000100000000010000000001" }

    18

    Returns: 30

  67. {"1001011000101010001111111110111011011100110001001" }

    4

    Returns: 14

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: