Statistics

Problem Statement for "MatrixGame"

Problem Statement

Alex likes to play the following strange game. He starts with a rectangular NxM grid where each cell contains a '0' (zero) or '1' (one). Rows of the grid are numbered 0 to N-1, inclusive, and columns are numbered 0 to M-1, inclusive. On each move, he chooses two columns in the grid and entirely swaps their content or he chooses two rows in the grid and entirely swaps their content. He can perform an arbitrary large number of moves and there are no restrictions on the order in which he performs moves.

Each NxM grid can be described as a String[] containing N elements. The j-th character in the i-th element of this String[] is the same as the character in row i, column j of the grid. Alex's goal is to achieve such a grid that the corresponding String[] is lexicographically minimal (see notes for exact definition). Since he is always unsure whether the goal has been achieved, you are to write a program that checks it for him. Given a String[] matrix describing the grid that Alex initially has, return the lexicographically smallest String[] that he can produce.

Definition

Class:
MatrixGame
Method:
getMinimal
Parameters:
String[]
Returns:
String[]
Method signature:
String[] getMinimal(String[] matrix)
(be sure your method is public)

Notes

  • A String[] A is lexicographically smaller than a String[] B of the same length if it contains a lexicographically smaller String at the first position where they differ.
  • A String A is lexicographically smaller than a String B of the same length if it contains a smaller character at the first position where they differ ('0' is smaller than '1').

Constraints

  • matrix will contain between 1 and 8 elements, inclusive.
  • Each element of matrix will contain between 1 and 8 characters, inclusive.
  • All elements of matrix will have the same length.
  • Each character in matrix will be either '0' or '1'.

Examples

  1. {"000", "000", "000"}

    Returns: {"000", "000", "000" }

    Any move has no effect.

  2. {"010", "000", "110"}

    Returns: {"000", "001", "011" }

    The following sequence of moves can be used: 010 000 000 000 000 -> 010 -> 001 -> 001 110 110 101 011

  3. {"111", "111", "111"}

    Returns: {"111", "111", "111" }

  4. {"01010", "10101", "01010", "10101"}

    Returns: {"00011", "00011", "11100", "11100" }

  5. {"11010100", "11110001", "00011101", "11111111", "01110100", "10000110", "00001001", "11010111"}

    Returns: {"00000011", "00001111", "00110100", "01011100", "01111101", "11001100", "11011001", "11111111" }

  6. {"0"}

    Returns: {"0" }

  7. {"11"}

    Returns: {"11" }

  8. {"111"}

    Returns: {"111" }

  9. {"0110"}

    Returns: {"0011" }

  10. {"11011"}

    Returns: {"01111" }

  11. {"000010"}

    Returns: {"000001" }

  12. {"0000011"}

    Returns: {"0000011" }

  13. {"11100001"}

    Returns: {"00001111" }

  14. {"1", "1"}

    Returns: {"1", "1" }

  15. {"11", "10"}

    Returns: {"01", "11" }

  16. {"001", "011"}

    Returns: {"001", "011" }

  17. {"1111", "0000"}

    Returns: {"0000", "1111" }

  18. {"11100", "00000"}

    Returns: {"00000", "00111" }

  19. {"111010", "110110"}

    Returns: {"001111", "010111" }

  20. {"0010011", "0010110"}

    Returns: {"0000111", "0001011" }

  21. {"00101001", "00010100"}

    Returns: {"00000011", "00011100" }

  22. {"0", "0", "1"}

    Returns: {"0", "0", "1" }

  23. {"11", "11", "11"}

    Returns: {"11", "11", "11" }

  24. {"111", "001", "100"}

    Returns: {"001", "010", "111" }

  25. {"0100", "1010", "0000"}

    Returns: {"0000", "0001", "0110" }

  26. {"10101", "00101", "01101"}

    Returns: {"00011", "00111", "01011" }

  27. {"011001", "011100", "110000"}

    Returns: {"000011", "001101", "010101" }

  28. {"0100010", "1010001", "1101000"}

    Returns: {"0000011", "0001101", "0110100" }

  29. {"00100101", "01110110", "00101000"}

    Returns: {"00000011", "00001101", "01110101" }

  30. {"0", "0", "0", "0"}

    Returns: {"0", "0", "0", "0" }

  31. {"00", "11", "11", "01"}

    Returns: {"00", "01", "11", "11" }

  32. {"010", "110", "110", "010"}

    Returns: {"001", "001", "011", "011" }

  33. {"1011", "1110", "1010", "0000"}

    Returns: {"0000", "0011", "0111", "1011" }

  34. {"10111", "00000", "01010", "11010"}

    Returns: {"00000", "00011", "00111", "11101" }

  35. {"000110", "011110", "001010", "100011"}

    Returns: {"000011", "000101", "001111", "110001" }

  36. {"1001000", "1110100", "1011100", "1100000"}

    Returns: {"0000011", "0000101", "0011011", "0011101" }

  37. {"11010110", "00100000", "00000111", "01000010"}

    Returns: {"00000001", "00000110", "00011010", "01101110" }

  38. {"1", "0", "0", "0", "0"}

    Returns: {"0", "0", "0", "0", "1" }

  39. {"01", "11", "01", "10", "00"}

    Returns: {"00", "01", "01", "10", "11" }

  40. {"101", "001", "111", "001", "011"}

    Returns: {"001", "001", "011", "101", "111" }

  41. {"1100", "0111", "1110", "0010", "0111"}

    Returns: {"0001", "0110", "0111", "1011", "1011" }

  42. {"00000", "00100", "01110", "01010", "01110"}

    Returns: {"00000", "00001", "00110", "00111", "00111" }

  43. {"001001", "110100", "000101", "001100", "001010"}

    Returns: {"000011", "000101", "000110", "001001", "110010" }

  44. {"0010010", "0010001", "1111010", "0110111", "0000000"}

    Returns: {"0000000", "0000011", "0000101", "0011111", "1101011" }

  45. {"01111010", "11001000", "00100111", "10001100", "10110010"}

    Returns: {"00000111", "00001011", "01110001", "01110110", "10111000" }

  46. {"0", "0", "0", "1", "1", "1"}

    Returns: {"0", "0", "0", "1", "1", "1" }

  47. {"01", "00", "11", "10", "00", "01"}

    Returns: {"00", "00", "01", "01", "10", "11" }

  48. {"101", "001", "001", "001", "000", "000"}

    Returns: {"000", "000", "001", "001", "001", "011" }

  49. {"1101", "0101", "1100", "0000", "0000", "0000"}

    Returns: {"0000", "0000", "0000", "0011", "0101", "0111" }

  50. {"01000", "10100", "10010", "00001", "10011", "01001"}

    Returns: {"00001", "00010", "00011", "01100", "01101", "10100" }

  51. {"100010", "000110", "010000", "001000", "011110", "111111"}

    Returns: {"000001", "000010", "001100", "001111", "010100", "111111" }

  52. {"0001011", "0100011", "1110111", "0110101", "1011010", "1100110"}

    Returns: {"0000111", "0001011", "0110101", "1010110", "1101001", "1110111" }

  53. {"10000010", "10110110", "11010100", "00000001", "00011101", "10110101"}

    Returns: {"00000001", "00000110", "00111001", "01011010", "10011011", "10011110" }

  54. {"1", "1", "1", "1", "0", "0", "1"}

    Returns: {"0", "0", "1", "1", "1", "1", "1" }

  55. {"11", "11", "10", "00", "10", "10", "01"}

    Returns: {"00", "01", "01", "01", "10", "11", "11" }

  56. {"000", "011", "000", "000", "010", "001", "001"}

    Returns: {"000", "000", "000", "001", "001", "010", "011" }

  57. {"0100", "1011", "1101", "1000", "0000", "1000", "0111"}

    Returns: {"0000", "0001", "0001", "0010", "0111", "1101", "1110" }

  58. {"10111", "00100", "10010", "11011", "01011", "10000", "00110"}

    Returns: {"00001", "00010", "00101", "00110", "01111", "11100", "11101" }

  59. {"000101", "000000", "101111", "000001", "010010", "001001", "100100"}

    Returns: {"000000", "000001", "000011", "000101", "001010", "011111", "110000" }

  60. {"0001101", "0010000", "1100111", "0111010", "1010101", "0001110", "1100110"}

    Returns: {"0000001", "0001110", "0010110", "0101011", "1010101", "1101100", "1111100" }

  61. {"10001111", "10110001", "11100100", "01011000", "00100011", "10000000", "10111111"}

    Returns: {"00000001", "00001110", "00010111", "01100011", "10101101", "10111111", "11010000" }

  62. {"1", "1", "1", "1", "1", "1", "0", "1"}

    Returns: {"0", "1", "1", "1", "1", "1", "1", "1" }

  63. {"10", "01", "10", "11", "10", "00", "11", "00"}

    Returns: {"00", "00", "01", "01", "01", "10", "11", "11" }

  64. {"110", "000", "010", "100", "001", "101", "001", "010"}

    Returns: {"000", "001", "001", "010", "010", "100", "101", "110" }

  65. {"1101", "1011", "1110", "1010", "1100", "0100", "0110", "0110"}

    Returns: {"0001", "0011", "0011", "0101", "0110", "0111", "1101", "1110" }

  66. {"10100", "01011", "01011", "01001", "00001", "11000", "00101", "10111"}

    Returns: {"00001", "00011", "00101", "01010", "01100", "10011", "10011", "11101" }

  67. {"100010", "000111", "000100", "100011", "100101", "011000", "101110", "111111"}

    Returns: {"000001", "000110", "001011", "001101", "001110", "010111", "110000", "111111" }

  68. {"1011101", "1000011", "0110000", "1110011", "1001111", "1100100", "0111000", "1001111"}

    Returns: {"0000011", "0000111", "0011001", "0111110", "1101000", "1101011", "1111100", "1111100" }

  69. {"01101110", "00000111", "00010111", "00111101", "01000111", "10110100", "10001101", "11011000"}

    Returns: {"00000111", "00001111", "00010111", "01100011", "01111000", "10101001", "11001011", "11010101" }

  70. {"11111111", "11111111", "11111111", "11111111", "11111111", "11111111", "11111111", "11111111"}

    Returns: {"11111111", "11111111", "11111111", "11111111", "11111111", "11111111", "11111111", "11111111" }

  71. {"11111111", "01110111", "11111100", "11111111", "11111111", "11111111", "11111111", "11111101"}

    Returns: {"00111111", "01111111", "11001111", "11111111", "11111111", "11111111", "11111111", "11111111" }

  72. {"10111111", "11111111", "11011111", "11010011", "01111101", "01000010", "11100101", "11011011"}

    Returns: {"00000011", "00011111", "00111111", "01111111", "11001101", "11110101", "11111110", "11111111" }

  73. {"10101011", "00011110", "11001000", "01111011", "11011100", "11111011", "10111001", "10011110"}

    Returns: {"00000111", "00011111", "00111001", "00111011", "11001011", "11100011", "11101101", "11101111" }

  74. {"11010111", "10010111", "11101011", "11010110", "11010101", "01001110", "00101100", "01111111"}

    Returns: {"00000111", "00011011", "01111001", "10111110", "11011111", "11101001", "11110001", "11111001" }

  75. {"01101111", "01010100", "11001010", "00001000", "11111011", "11001001", "10011001", "11100001"}

    Returns: {"00000001", "00001110", "00110011", "00110101", "01010011", "10110010", "11101011", "11110111" }

  76. {"00001100", "00011110", "10001111", "00010010", "11101101", "00000101", "00101100", "10000100"}

    Returns: {"00000011", "00000101", "00001001", "00010011", "00101111", "01011111", "10100000", "10100011" }

  77. {"10100001", "10000110", "10001001", "00111001", "00100000", "00011110", "00010000", "01000100"}

    Returns: {"00000001", "00000010", "00001100", "00110001", "01010011", "01110000", "10100100", "11000110" }

  78. {"00000010", "00000000", "00000110", "00010000", "00000000", "00001001", "00110000", "00000011"}

    Returns: {"00000000", "00000000", "00000001", "00000010", "00000101", "00001001", "00010010", "00100100" }

  79. {"00000000", "00010001", "00000000", "00100000", "00000000", "00000000", "00000000", "00001010"}

    Returns: {"00000000", "00000000", "00000000", "00000000", "00000000", "00000001", "00000110", "00011000" }

  80. {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000"}

    Returns: {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000" }

  81. {"00000000", "00000000", "01101101", "11101010", "00001001", "00110111", "10100001", "00000100"}

    Returns: {"00000000", "00000000", "00000001", "00000110", "00011010", "00101111", "01111100", "11001011" }

  82. {"00001010", "00010111", "00011000", "01000010", "11010100", "00111110", "00010010", "01010101"}

    Returns: {"00000011", "00000101", "00000110", "00001001", "00110011", "00111010", "01010111", "10011010" }

  83. {"10100001", "11101110", "00001111", "11010000", "01111000", "01111101", "11010101", "01101110"}

    Returns: {"00000111", "00011001", "00101110", "01010111", "01111110", "11101010", "11101011", "11110000" }

  84. {"00011000", "10000100", "11000101", "01010101", "11010000", "00001100", "01010110", "10100010"}

    Returns: {"00000011", "00000101", "00001010", "00011100", "00110101", "00111001", "01011001", "11000100" }

  85. {"00000111", "11111001", "11100001", "11101111", "11110010", "01001111", "11101000", "00000111"}

    Returns: {"00000111", "00000111", "00011111", "01101001", "01111000", "01111111", "11101010", "11111001" }

  86. {"01010011", "11011111", "01101110", "00010111", "00011111", "10001000", "11101111", "00100100"}

    Returns: {"00000011", "00001100", "00110111", "01111111", "11010001", "11010101", "11110000", "11111101" }

  87. {"00000011", "00001000", "11111010", "00011101", "01000000", "11100101", "00010100", "00001110"}

    Returns: {"00000001", "00000010", "00001100", "00010101", "00101101", "00110000", "11011011", "11100110" }

  88. {"00010010", "00110011", "00000011", "10001101", "11110001", "10100110", "01111010", "00010011"}

    Returns: {"00000011", "00000101", "00000111", "00001111", "00111001", "01011110", "10110010", "11001101" }

  89. {"00100000", "10100001", "01000011", "00100111", "00000101", "00001101", "11010001", "00011000"}

    Returns: {"00000001", "00000110", "00001011", "00010110", "00100111", "01010000", "10100010", "11001010" }

  90. {"00001011", "01001100", "11010000", "11111111", "00110000", "01010010", "11011100", "10010010"}

    Returns: {"00000011", "00001101", "00010101", "00011001", "01100100", "01101101", "10110000", "11111111" }

  91. {"00101001", "01010100", "11100011", "11000010", "01110100", "10000110", "01110000", "00101001"}

    Returns: {"00000111", "00000111", "00011001", "00111000", "00111001", "11001000", "11001011", "11100000" }

  92. {"11010100", "11110001", "00011101", "11111111", "01110100", "10000110", "00001001", "11010111" }

    Returns: {"00000011", "00001111", "00110100", "01011100", "01111101", "11001100", "11011001", "11111111" }

  93. {"1100", "1110", "0111", "1001" }

    Returns: {"0011", "0101", "1011", "1110" }

  94. {"11001010", "11110000", "00000001", "10101111", "01010110", "00000011", "10101110", "10001111" }

    Returns: {"00000001", "00000011", "00011110", "00101111", "01101110", "01101111", "10110010", "11010100" }

  95. {"11110001", "10110101", "10001101", "11111111", "00000000", "10000111", "01010111", "00011111" }

    Returns: {"00000000", "00001111", "00010111", "00111011", "01100111", "10101011", "11100101", "11111111" }

  96. {"10010011", "10001111", "00110100", "01011101", "01101101", "11001100", "11110100", "11110100" }

    Returns: {"00000111", "00011111", "00011111", "00111001", "01101011", "01101101", "11010010", "11110001" }

  97. {"01011110", "10101111", "11010111", "10101101", "10101011", "10001111", "10101110", "10101011" }

    Returns: {"00011111", "00011111", "00101111", "00110111", "00111011", "00111111", "11100101", "11101110" }

  98. {"11100000", "00111011", "00110000" }

    Returns: {"00000011", "00001101", "01110011" }

  99. {"10101010", "00110011", "11111110", "10101111", "11001100", "11001100", "10101010" }

    Returns: {"00001111", "00001111", "00110011", "00110011", "01011111", "10111111", "11001100" }

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: