Statistics

Problem Statement for "XorGame"

Problem Statement

You are given two Strings: the start string S and the end string E. Both strings have the same length, and each of their characters is either '0' or '1'. Two players A and B play the game that starts with the string S. Player A and player B take alternating turns, with player A going first. In each of her turns, player A picks a contiguous subsequence of the current string and flips it - changing all '0's to '1's and vice versa. (She is allowed to pick an empty subsequence, which results in her not changing the current string.) In each of his turns, player B may pick a character of the current string and flip it. (He is allowed not to pick any character and keep the current string unchanged.)


When the string turns into E, player A wins. If player A can win the game, return the minimum possible number of turns A has to take. (We assume that if player A can ensure a win, then player B uses a strategy that postpones his loss for as long as possible.) If player A cannot win the game, return -1 instead.

Definition

Class:
XorGame
Method:
play
Parameters:
String, String
Returns:
int
Method signature:
int play(String S, String E)
(be sure your method is public)

Constraints

  • S will contain between 1 and 50 characters, inclusive.
  • S and E will contain the same number of characters.
  • Each character in S and E will be '0' or '1'.

Examples

  1. "10101"

    "11011"

    Returns: 1

    Player A can win in the first turn by flipping characters 1 through 3 (0-based indices).

  2. "001100"

    "001100"

    Returns: 0

    Player A wins immediately after the game begins.

  3. "110"

    "011"

    Returns: 2

    In this case, player A cannot win in her first turn. However, she can start by flipping characters 1 and 2, producing the string "101". Regardless of what player B does (and even if he chooses not to flip anything), she will then have winning move in her second turn.

  4. "10101010"

    "11111111"

    Returns: -1

  5. "001011010101101"

    "001000101101101"

    Returns: 1

  6. "0"

    "0"

    Returns: 0

  7. "0"

    "1"

    Returns: 1

  8. "1"

    "0"

    Returns: 1

  9. "1"

    "1"

    Returns: 0

  10. "00"

    "01"

    Returns: 1

  11. "10"

    "11"

    Returns: 1

  12. "11"

    "00"

    Returns: 1

  13. "000"

    "111"

    Returns: 1

  14. "101"

    "010"

    Returns: 1

  15. "101"

    "111"

    Returns: 1

  16. "000"

    "101"

    Returns: 2

  17. "0000"

    "1010"

    Returns: 2

  18. "0000"

    "0101"

    Returns: 2

  19. "0000"

    "1001"

    Returns: 2

  20. "1010"

    "0101"

    Returns: 1

  21. "1101"

    "1000"

    Returns: 2

  22. "1111"

    "0110"

    Returns: 2

  23. "1010"

    "0101"

    Returns: 1

  24. "1010"

    "1110"

    Returns: 1

  25. "0110"

    "1110"

    Returns: 1

  26. "0010"

    "1001"

    Returns: 3

  27. "0111"

    "0000"

    Returns: 1

  28. "1001011010101"

    "1000011010101"

    Returns: 1

  29. "001010101001001"

    "110101010110110"

    Returns: 1

  30. "0000000000"

    "1111111111"

    Returns: 1

  31. "0000000000000000000000000000000000000000"

    "1111111111111111111111111111111111111111"

    Returns: 1

  32. "0000000000000000000000000000000000000000"

    "1000000000000000000000000000000000000001"

    Returns: -1

  33. "0000000000000000000000000000000000000000"

    "1000000000000000000000000000000000000000"

    Returns: 1

  34. "0000000000000000000000000000000000000000"

    "0000000000001000000000000000000000000000"

    Returns: 1

  35. "0000000000000000000000000000000000000000"

    "0000000000000000000001111111111000000000"

    Returns: 1

  36. "1101001010101000000011010010000100111001"

    "0101001010101000000011010010000100111000"

    Returns: -1

  37. "1100001101000011110100111011010101001110"

    "1100001101000011110100111011010101001110"

    Returns: 0

  38. "1011101001010100100101010101011110100011"

    "1011101001010100100100010101011110100011"

    Returns: 1

  39. "10100111010010"

    "10100110101100"

    Returns: 1

  40. "11110011111100111011"

    "11001100000011011011"

    Returns: 1

  41. "1111000111101100001100000000101001110000100010"

    "1111000110010011110011111100101001110000100010"

    Returns: 1

  42. "1011011000011010011111101001011111110101111"

    "1011011000000101100000010110111111110101111"

    Returns: 1

  43. "0111101110011111000000011100111010110110100011101"

    "0111101110011111000000011100100100110110100011101"

    Returns: 1

  44. "1001001010111010"

    "1111001010111010"

    Returns: 1

  45. "011111111"

    "011100001"

    Returns: 1

  46. "101011100011010001011000001010101111"

    "010100011100101110100110001010101111"

    Returns: 1

  47. "0011010011010100110001010"

    "1100110011010100110001010"

    Returns: 1

  48. "101001"

    "110110"

    Returns: 1

  49. "1111010100011011010001001101"

    "1111010100011000100001001101"

    Returns: 1

  50. "1010101011001011000011000101001110010011111111010"

    "1010101011001011000011000101000001101100000000100"

    Returns: 1

  51. "1"

    "0"

    Returns: 1

  52. "11101010101011101100111110"

    "11101010100100010100111110"

    Returns: 1

  53. "1100100101111101001111001100000001000000001010111"

    "1100011010000010110000110100000001000000001010111"

    Returns: 1

  54. "0010011100000011"

    "0010011100001101"

    Returns: 1

  55. "01111110111100101010001101"

    "01111110100011010101111101"

    Returns: 1

  56. "11111001110010001111001001011100110101010110000"

    "11000110001101110111001001011100110101010110000"

    Returns: 1

  57. "011011001011001010101111010000011"

    "011011001011000101011111010000011"

    Returns: 1

  58. "0001100010111100100001111011001"

    "0001100101000011011110000100110"

    Returns: 1

  59. "010101001111011010010"

    "011101001111011010010"

    Returns: 1

  60. "11011010010101010100000000000010110"

    "11011010011101010100000000000010110"

    Returns: 1

  61. "1100110100010111110"

    "1100110110010111110"

    Returns: 1

  62. "0001101010000010111111100111000001000001010011110"

    "0001101010000010111111100111000001000101010011110"

    Returns: 1

  63. "011100111011110011111100011011"

    "011101111011110011111100011011"

    Returns: 1

  64. "00001011"

    "01001011"

    Returns: 1

  65. "010110010101111101111001"

    "010110010111111101111001"

    Returns: 1

  66. "0101101101110010001000010011"

    "0101101101100010001000010011"

    Returns: 1

  67. "1001000000010111110000111010001"

    "1001000000010111110000101010001"

    Returns: 1

  68. "001110000011011001101"

    "001111000011011001101"

    Returns: 1

  69. "00111110010010000001010001010010111"

    "01000011111001000001111110110100001"

    Returns: -1

  70. "11101100000011011011000"

    "10001010000111101010010"

    Returns: -1

  71. "11011111111110110110110111101000101000"

    "11100110111111100100110000001110011010"

    Returns: -1

  72. "1000000011011000101011011100111000"

    "0001111001001100111000000000111010"

    Returns: -1

  73. "0000101100111100110"

    "0011110101011110101"

    Returns: -1

  74. "1001010100011010101"

    "0000110011110001101"

    Returns: -1

  75. "000000000111001011000110111010110001101100"

    "111001011010110100011000101000100001101100"

    Returns: -1

  76. "00000"

    "11000"

    Returns: 1

  77. "1010111011011110001100"

    "0011101001110100011010"

    Returns: -1

  78. "11010111110011011001001110000101110111001"

    "11101000101011010100000110101100110110101"

    Returns: -1

  79. "1110010011100101100001000101"

    "1110010011100101100110111001"

    Returns: 1

  80. "101100"

    "111011"

    Returns: -1

  81. "001011011100111011101101100111000010110"

    "000100100000111011101101111000111101110"

    Returns: -1

  82. "10011010000101011110000000110110"

    "10011010000100100001100000100110"

    Returns: -1

  83. "0000111101000000001011111111110010001101000100101"

    "0000111110111110001100000000001110001101000100101"

    Returns: -1

  84. "0111"

    "1100"

    Returns: 3

  85. "111"

    "010"

    Returns: 2

  86. "1111100011001100110001"

    "1111101100110011001001"

    Returns: 1

  87. "101010101"

    "110010110"

    Returns: -1

  88. "00000101001001000011001100011100110010"

    "00000100110110101100110011011100110010"

    Returns: -1

  89. "0000"

    "1011"

    Returns: 3

  90. "0000"

    "1101"

    Returns: 3

  91. "0101"

    "0000"

    Returns: 2

  92. "0000"

    "1001"

    Returns: 2

  93. "0000"

    "1010"

    Returns: 2

  94. "1101"

    "0000"

    Returns: 3

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: