Statistics

Problem Statement for "ReversalChain"

Problem Statement

Given a string, the reversal operation r(i, j) reverses the substring of the string from the i-th character to the j-th character (0-indexed, inclusive). A reversal chain is a sequence of reversals where the range of each reversal is included in the range of the previous reversal. Formally, the sequence r(i1, j1), r(i2, j2), ..., r(im, jm) is a reversal chain if i1 <= i2 <= ... <= im, and j1 >= j2 >= ... >= jm.

You are given a string init which contains only '0' (zero) and '1' (one) characters. You want to transform this string into the string goal using a reversal chain. Return the minimum possible length of a reversal chain that transforms init into goal. Return -1 if it is impossible.

Definition

Class:
ReversalChain
Method:
minReversal
Parameters:
String, String
Returns:
int
Method signature:
int minReversal(String init, String goal)
(be sure your method is public)

Constraints

  • init will contain between 1 and 50 characters, inclusive.
  • init and goal will contain the same number of characters.
  • Each character of init and goal will be '0' (zero) or '1' (one).

Examples

  1. "1100"

    "0110"

    Returns: 1

    r(0, 2) transforms "1100" into "0110".

  2. "111000"

    "101010"

    Returns: 2

    r(1, 4) and r(2, 3) transforms "111000" into "101010".

  3. "0"

    "1"

    Returns: -1

    It is impposible to transform "0" into "1" by a reversal chain.

  4. "10101"

    "10101"

    Returns: 0

    You do not have to do anything.

  5. "111000111000"

    "001100110011"

    Returns: 4

  6. "001100"

    "100001"

    Returns: -1

  7. "1010101010101010101010101010101010101010"

    "1111111111111111111100000000000000000000"

    Returns: 19

  8. "11110000001111"

    "10001111110001"

    Returns: -1

  9. "111110111100111000110000100000"

    "111000111000111000111000111000"

    Returns: 4

  10. "001000011000000111000000001111"

    "100100100100100100100100100100"

    Returns: 9

  11. "001000011000000111000000001111"

    "001001001001001001001001001001"

    Returns: 8

    rev: 6 29 rev: 6 26 rev: 9 26 rev: 10 24 rev: 12 23 rev: 15 23 rev: 16 21 rev: 18 20

  12. "001001000011000011001001"

    "000000000000000011111111"

    Returns: 5

  13. "000000000000000000000000000000"

    "000000000000000000000000000000"

    Returns: 0

  14. "0000000000"

    "1111111111"

    Returns: -1

  15. "1111000110"

    "1010101011"

    Returns: 4

  16. "10110111011110111011010"

    "11110111101111011110000"

    Returns: 4

  17. "11111111111111111100000000000000001111111111111111"

    "11111111110000000011111111111111110000000011111111"

    Returns: 2

  18. "111111000111100110111111000111100110"

    "001111001111001111001111001111001111"

    Returns: 5

  19. "01001"

    "00110"

    Returns: 2

  20. "01100111001011010101011110010010001111100011100100"

    "00111111101111000001101100111101001101000100100100"

    Returns: 10

  21. "11111100111010010010101100001010110110110100001111"

    "00000100000010110000110110011111111110110011111111"

    Returns: 12

  22. "00001011111010111110001111000001000001011011100100"

    "00111111001110010100010011010010101000110010011001"

    Returns: 16

  23. "011111100001000011000101000001001100111110"

    "100010000101000011010110010110100110110101"

    Returns: -1

  24. "0101000000001011001001010101110000001100010100"

    "0001001000101100010100111000101110100000000010"

    Returns: 9

  25. "0101111110110100111011101111001110111"

    "1111100011101110111100111101001110111"

    Returns: 5

  26. "110110101000110010000101010"

    "101011110101010100000001001"

    Returns: 6

  27. "11111111111101100110111101111111110"

    "10111101111110011011111111111111110"

    Returns: 2

  28. "1111111101110000110111111110101100"

    "1111010101110110111011110110100111"

    Returns: 9

  29. "11010010110001011010000100100100001010"

    "01110000000101000000110111000001101011"

    Returns: 10

  30. "11110011101111111011111011111111"

    "01101001111111111111111111011111"

    Returns: 5

  31. "111101101111"

    "110111111110"

    Returns: -1

  32. "01000101011011010101100111111011101001010111"

    "10011111011001111000111110001010111000110011"

    Returns: 12

  33. "011101011010011111111110101"

    "110010011111101111011111100"

    Returns: 7

  34. "0001000000000001000000001001000000011000000000"

    "0100100010000000000000110000100000000000000000"

    Returns: 5

  35. "010001111001110101110011011"

    "111101010110101101011100010"

    Returns: 6

  36. "1101011000010001000010101001"

    "0000011011100100000110101001"

    Returns: 6

  37. "000000001111000000010"

    "000000000110001001001"

    Returns: 4

  38. "100000000001011000100001000000000"

    "000000010000000110000000111000000"

    Returns: 5

  39. "00000010110011000000000010000101000"

    "00000101010000100000000000101001001"

    Returns: -1

  40. "0000000000010000000000000000000"

    "0000000000000000000000010000000"

    Returns: 1

  41. "00001000100000000000000000000"

    "00000000000000000000000001010"

    Returns: 2

  42. "1111111111011110111111011111111111111111101111111"

    "1111111101111111111111111101011111111101111111111"

    Returns: 3

  43. "10100110001010101000000010100111"

    "01000100100001110001000111001110"

    Returns: -1

  44. "1111011011011010111100111100000110000111111"

    "0111111101011100010111010110010101001111110"

    Returns: -1

  45. "010111110001"

    "011110111000"

    Returns: 3

  46. "11101111110"

    "11110111110"

    Returns: 1

  47. "11001110111010101010010110001010001011010"

    "11011011011101000110100111110100000010001"

    Returns: 10

  48. "11111111011111111111110"

    "11111110111111111111101"

    Returns: 1

  49. "1010000010101000111000001110010"

    "0001100000011100110100010111000"

    Returns: -1

  50. "10010101100110010101100010100011010000000"

    "01010110001000110001000011000000010111011"

    Returns: -1

  51. "000000000000000000000000000000000010000"

    "000000000000000000000000000000000001000"

    Returns: 1

  52. "001010000000001000111101000010100"

    "011011000010000001010100100100000"

    Returns: 7

  53. "111100111111110101111101111100110110101111111"

    "110111011011111111011011111001101111111010111"

    Returns: 11

  54. "0010011010"

    "1000100110"

    Returns: 2

  55. "111111111111111111111111111111111111111111"

    "111111111111111111111111111111111111111111"

    Returns: 0

  56. "0010101000001010000000010000001000000000000"

    "0100000000100001010000000100000000000000110"

    Returns: 8

  57. "100000000100000001010100000000"

    "001010000000101000000000000001"

    Returns: 3

  58. "1111111111"

    "1111111111"

    Returns: 0

  59. "00000000110100"

    "00000010000110"

    Returns: 2

  60. "11"

    "11"

    Returns: 0

  61. "010000101101000110110101100010"

    "101010110010001111000010010001"

    Returns: -1

  62. "010111011100100111110111111101100111111"

    "111110111111111111010001000110111011101"

    Returns: 8

  63. "000101010000111110100011101010011110110111"

    "110111001011101111010010000110100010101011"

    Returns: 8

  64. "010001110111110010110"

    "011011111000011001101"

    Returns: -1

  65. "10010000011110110010"

    "11111000101000100001"

    Returns: 7

  66. "0000000010000100001"

    "0011000010000000000"

    Returns: 2

  67. "0000000000000000000000000000000000"

    "0000000000000000000000000000000000"

    Returns: 0

  68. "0101001111110111110010011111111110001"

    "0110111010001110111101101011111101011"

    Returns: -1

  69. "10010000000001001001000001010000100000100"

    "00100000000000000010010001010001010100001"

    Returns: 6

  70. "001001010001000011"

    "000010000001001111"

    Returns: 3

  71. "11101110101111101011110110011111111010"

    "10111011111100111101111111101110011001"

    Returns: 11

  72. "000101100101010001010011110011001111"

    "000010101011111001010011011000111100"

    Returns: 8

  73. "11111111111111111111111111111111111111111111111111"

    "11111111111111111111111111111111111111111111111111"

    Returns: 0

  74. "01001011110011000000110000010000010000000101001000"

    "10000000101100011011010000010000100010101010000000"

    Returns: -1

  75. "00000100000010000000000110000100000000100000000100"

    "10000000000000000000001000001000001010000000000101"

    Returns: -1

  76. "11111110100111111111111111111101111011111101111111"

    "11101110101111111011111111111111111110111111011111"

    Returns: 5

  77. "00000000000100000100001010000000000000000000011000"

    "00000000000010000001000000000101000000001010000000"

    Returns: 8

  78. "10100111011111001001101100010111010101011100101111"

    "01110010011001110111111100110100101110001110111001"

    Returns: -1

  79. "11111101011111111111110111111111111111111111111111"

    "10111111111111101111111111110111111111111111111111"

    Returns: 2

  80. "11011010011100110111100111111111011001101101011100"

    "10011011101111101111011011100100011111111010001011"

    Returns: 10

  81. "10111101110111110110101000110010110111111101001100"

    "01110110011001111110110010111111111011011100000011"

    Returns: -1

  82. "11111111101111100111111011111111100001111101111101"

    "01111101111111100011111111111110111001111111010111"

    Returns: 7

  83. "01110111011110110110110011110111111010001110010011"

    "10110111011011101101111111001011111000111001110001"

    Returns: 10

  84. "11011001001101000010000110010100000000000001010010"

    "00001100001100000001011001010010101100010010100000"

    Returns: -1

  85. "11111011111110011001011010110111101111111111111101"

    "11111101111110101101110010101101011110111111111111"

    Returns: 7

  86. "11000011011101101001000101011010011001010010111001"

    "11101011111101010010100001011010011110001000001010"

    Returns: 13

  87. "01011000001001110000000100000011001001011111010100"

    "00101010100110010101001010110111001000001100000000"

    Returns: -1

  88. "01101011101111111101111111010110100011111111111011"

    "01101101011111110111111011111110110010110111011111"

    Returns: 8

  89. "01000100000000010000000000000100000000000000000000"

    "00010000000000000000000000010001000100000000000000"

    Returns: 4

  90. "00100001101000010100110010111010100000000010110010"

    "10010000001000100011010110010100000101101011100000"

    Returns: 12

  91. "11000011110010011011000111111100001101001111000110"

    "00001100011011001111001110111110101110000001110110"

    Returns: -1

  92. "00100100000101001100000110110000000001101000101111"

    "00001001000010010010110010100011010001100001010110"

    Returns: -1

  93. "1100010000101"

    "1001100001001"

    Returns: 3

  94. "000000000000010000000000110010010000000000001"

    "000000010010000000000000000101010010000000000"

    Returns: 5

  95. "0000111010010001101001100000011000100111"

    "0110010100011110100011010000000000001111"

    Returns: 12

  96. "101111100101100111001011110101101111011011111000"

    "110101111111110001111011111101110100111001000010"

    Returns: 13

  97. "0111110101011100111001111000111110111100101000101"

    "1011100111000111000100010111101101100111011111110"

    Returns: 15

  98. "101000100111110101011101110001111100010110"

    "111111111100000110011101011101000110010010"

    Returns: 16

  99. "01011000001111010000111000100111110000000000110"

    "10100100101101011101000000110010101010001010000"

    Returns: 17

  100. "10000001110100110111001110000000011101110101111100"

    "11010111110001101110001110111000010101110000100000"

    Returns: 19

  101. "11111111111111111111111110000000000000000000000000"

    "10101010101010101010101010101010101010101010101010"

    Returns: 24

  102. "11010110010011100111010000010110001010000001100110"

    "11010100000000110111110110000011010000111000011010"

    Returns: 20

  103. "10001111111101001100100100000101110111101110100111"

    "11111111101010011111110010110010110110001010001000"

    Returns: 21

  104. "00001111001001011111100111100010111011111111011011"

    "01001111111111011100001011100110011110100101011111"

    Returns: 22

  105. "1010101000101010000100100010001010001011110000100"

    "1100100100001001000010101001000111010010100010001"

    Returns: 10

  106. "01010111101010001100001011000111001110101101111001"

    "10111100110101100000101100011110001110101111010010"

    Returns: 9

  107. "1011000011"

    "0100101101"

    Returns: 3

  108. "100011101001"

    "010101110001"

    Returns: 2

  109. "011010"

    "100110"

    Returns: 2

  110. "10011000000000000000000000000000000000000000000000"

    "01101000000000000000000000000000000000000000000000"

    Returns: 2

  111. "010010"

    "001100"

    Returns: 2

  112. "101001"

    "100110"

    Returns: 2

  113. "00100100"

    "00011000"

    Returns: 2

  114. "11100101"

    "11011001"

    Returns: 2

  115. "101100"

    "110010"

    Returns: 2

  116. "0110"

    "1001"

    Returns: -1

  117. "11010101010100100010101111000"

    "11111110000110000111100001000"

    Returns: 9

  118. "01101"

    "10011"

    Returns: 2

  119. "0110011"

    "0101101"

    Returns: 2

  120. "11011011"

    "11100111"

    Returns: 2

  121. "100110"

    "101001"

    Returns: 2

  122. "10011"

    "01101"

    Returns: 2

  123. "011010111001"

    "010111001110"

    Returns: 2

  124. "10011000010000111010100110101001010101010110011010"

    "11001010101101010100100010001001010101010101010011"

    Returns: -1

  125. "11101000001000100001101001111111001001010011110110"

    "00101111100110000000111000001100011011011110111010"

    Returns: -1

  126. "000111011101010101011010001110101010001000110"

    "000111011101010101100101001110101010001000110"

    Returns: 2

  127. "001001000"

    "000110000"

    Returns: 2

  128. "00000000001111111111000000000011111111110000011111"

    "10101010101010101010101010101010101010101010101010"

    Returns: -1

  129. "10110000111"

    "01001011011"

    Returns: 3

  130. "100100"

    "011000"

    Returns: 2

  131. "001100"

    "010010"

    Returns: 2

  132. "1000000100000000100000010001110000"

    "1100000000000000100000010101000001"

    Returns: 6

  133. "11001111110011000100010111010111110101010110110001"

    "00010110111001010101110000001110111010111110111011"

    Returns: 10

  134. "10110100"

    "00101110"

    Returns: 2

  135. "1001"

    "0110"

    Returns: -1

  136. "10010"

    "01100"

    Returns: 2

  137. "11011101111111101111101111111011111011101011110110"

    "01101111111110111111101111111011011111101111100011"

    Returns: 7

  138. "10101010101010101010101010101010101010101010101010"

    "11111111111111111111111110000000000000000000000000"

    Returns: 24

  139. "00110"

    "01001"

    Returns: 2

  140. "0010000"

    "0000010"

    Returns: 1

  141. "11001100111100110011110011001111001100111100110011"

    "11101110001110111000111011100011101110001110111000"

    Returns: 11

  142. "000111000"

    "001010100"

    Returns: 3

  143. "1001101001"

    "1101000011"

    Returns: 2

  144. "10101111001101011100000010110001010000101110001111"

    "11101010010000001011100000100101111101011110000111"

    Returns: 11

  145. "00010100001000010010010000000001010000001011111100"

    "00010001110011000001011000100010010001010000010000"

    Returns: 12

  146. "10110"

    "11001"

    Returns: 2

  147. "101"

    "010"

    Returns: -1

  148. "00101101"

    "01110100"

    Returns: 2

  149. "100001000111100111011000011111"

    "100001010000011011111101100111"

    Returns: 5

  150. "0001"

    "0010"

    Returns: 1

  151. "111011011101101101000011011111010001"

    "011011011101101101000111011100010111"

    Returns: 6

  152. "1101110"

    "1110011"

    Returns: 2

  153. "11001000010100100100000100000000000000010000010000"

    "01011000010100100100000100000000000010000000001000"

    Returns: 5

  154. "000000000000001111111111111111111000000000000000"

    "111010001111100001000001000100000110010010011100"

    Returns: -1

  155. "01110"

    "10101"

    Returns: -1

  156. "00000000000000000000000001000000000000000000000000"

    "00000000000000000000000000000000000000000000000000"

    Returns: -1

  157. "11101000001000101001101001111111001011010011110110"

    "00101111100110000000111000101100011011011110111110"

    Returns: 12

  158. "11001000001111111010100100100110101011101101101110"

    "11011100001010111101101011100010100101001111110010"

    Returns: 10

  159. "01000110011000100110101011010001100010000010010110"

    "01110100011000001101101001110010001100000010110000"

    Returns: 6

  160. "00100011"

    "00001101"

    Returns: 2

  161. "10111100110101100000101100011110001110101111010010"

    "01100111010100111101101011000010001011101100101110"

    Returns: 13

  162. "00000000000000000000000001111111111111111111111111"

    "00000000000000000000000001111111111111111111111110"

    Returns: -1

  163. "111000111000101010101010101010101010101010101010"

    "001100110011010101010101010101010101010101010101"

    Returns: 6

  164. "111111111111111000000000000000000000000000000000"

    "111111010010001000000010000000000001010111000000"

    Returns: 7

  165. "0111101011"

    "1011011011"

    Returns: 2

  166. "01000110011000100110101011010001100010000010010110"

    "00010101110010011010110101001001001000000000110011"

    Returns: 9

  167. "11111111111111111111111110000000000000000000000000"

    "01010101010101010101010101010101010101010101010101"

    Returns: 25

  168. "00000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000000"

    Returns: 0

  169. "01010101010101010101010101010101010101010101010101"

    "00000111110000011111000001111100000111110000011111"

    Returns: 20

  170. "011101101011"

    "111011010111"

    Returns: -1

  171. "10110111011110111110111111011111110111111110"

    "00000000111111111111111111111111111111111111"

    Returns: 8

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: