Statistics

Problem Statement for "PalindromeMatrix"

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.

Fox Ciel has a matrix A that consists of N rows by M columns. Both N and M are even. Each element of the matrix is either 0 or 1. The rows of the matrix are numbered 0 through N-1 from top to bottom, the columns are numbered 0 through M-1 from left to right. The element in row i, column j is denoted A(i, j). You are given a String[] A that describes the matrix A. The character A[i][j] is '1' if A(i, j)=1 and it is '0' otherwise.

A palindrome is a string that reads the same forwards and backwards. For example, "1001" and "0111001110" are palindromes while "1101" and "000001" are not.

Some rows and some columns in Ciel's matrix may be palindromes. For example, in the matrix below both row 0 and column 3 are palindromes. (Row 0 is the palindrome "0000", column 3 is the palindrome "0110".) 

0000
0011
0111
1110

You are also given two ints: rowCount and columnCount. Ciel wants her matrix A to have at least rowCount rows that are palindromes, and at the same time at least columnCount columns that are palindromes. If this is currently not the case, she can change A by changing some of the elements (from '0' to '1' or vice versa). Compute and return the smallest possible number of elements she needs to change in order to reach her goal.

Definition

Class:
PalindromeMatrix
Method:
minChange
Parameters:
String[], int, int
Returns:
int
Method signature:
int minChange(String[] A, int rowCount, int columnCount)
(be sure your method is public)

Constraints

  • N and M will be between 2 and 14, inclusive.
  • N and M will be even.
  • A will contain N elements.
  • Each element of A will contain M characters.
  • Each character of A will be either '0' or '1'.
  • rowCount will be between 0 and N.
  • columnCount will be between 0 and M.

Examples

  1. {"0000" ,"1000" ,"1100" ,"1110"}

    2

    2

    Returns: 1

    An optimal solution is to change A(3, 0) to 0. Then we will have palindromes in two rows (0 and 3), and in two columns (0 and 3).

  2. {"0000" ,"1000" ,"1100" ,"1110"}

    3

    2

    Returns: 3

    This is similar to the previous example, but in this case we must have three row palindromes. An optimal solution is to change A(1, 0), A(2, 0) and A(3, 0) to 0.

  3. {"01" ,"10"}

    1

    1

    Returns: 1

  4. {"1110" ,"0001"}

    0

    0

    Returns: 0

    Here, we do not have to change A at all.

  5. {"01010101" ,"01010101" ,"01010101" ,"01010101" ,"01010101" ,"01010101" ,"01010101" ,"01010101"}

    2

    3

    Returns: 8

  6. {"000000000000" ,"011101110111" ,"010001010101" ,"010001010101" ,"011101010101" ,"010101010101" ,"010101010101" ,"011101110111" ,"000000000000" ,"000000000000"}

    5

    9

    Returns: 14

  7. {"11111101001110" ,"11000111111111" ,"00010101111001" ,"10110000111111" ,"10000011010010" ,"10001101101101" ,"00101010000001" ,"10111010100100" ,"11010011110111" ,"11100010110110" ,"00100101010100" ,"01001011001000" ,"01010001111010" ,"10100000010011"}

    6

    8

    Returns: 31

  8. {"00000000100000","11010001101100","10010101000011","00110001111010","00000000100101","01100100010100","10010000101010","10110110000010","01010011110000","11110001100001","00001010000001","00011000001000","10000001000100","01000110110100"}

    7

    7

    Returns: 26

  9. {"11111110000000" ,"11111110000000" ,"11111110000000" ,"11111110000000" ,"11111110000000" ,"11111110000000" ,"11111110000000" ,"00000001111111" ,"00000001111111" ,"00000001111111" ,"00000001111111" ,"00000001111111" ,"00000001111111" ,"00000001111111"}

    14

    14

    Returns: 98

  10. {"01", "01"}

    2

    2

    Returns: 2

  11. {"1110", "1000"}

    2

    1

    Returns: 2

  12. {"010011", "110111"}

    1

    4

    Returns: 1

  13. {"01", "00", "01", "00"}

    4

    2

    Returns: 2

  14. {"1100", "1001", "1110", "1010"}

    1

    2

    Returns: 1

  15. {"000001", "000000", "111111", "001110"}

    4

    6

    Returns: 10

  16. {"10", "01", "10", "10", "10", "11"}

    1

    2

    Returns: 3

  17. {"0011", "0011", "1001", "0100", "0000", "0010"}

    3

    1

    Returns: 1

  18. {"010001", "100111", "010010", "001100", "110001", "110011"}

    5

    5

    Returns: 8

  19. {"10111101111101", "10011011101101"}

    1

    3

    Returns: 1

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

    2

    1

    Returns: 2

  21. {"01100101111011", "11111100001010", "10010110111110", "01111111101010"}

    1

    3

    Returns: 2

  22. {"0000", "1010", "1100", "0111", "0001", "0000", "1100", "1011", "1011", "0100", "1101", "1000", "0010", "1010"}

    3

    2

    Returns: 6

  23. {"10110111011001", "10101111111110", "11001111111101", "00110111010101", "00111010110110", "00101101001110"}

    2

    2

    Returns: 6

  24. {"000110", "010001", "101100", "101010", "011111", "100001", "000011", "000000", "000110", "001001", "000101", "001001", "001111", "010011"}

    2

    3

    Returns: 8

  25. {"10000000110010", "10010000011101", "10001001010111", "11001101000101", "11101110000010", "10101100100110", "01010100110000", "10000001110111", "01100010111100", "01110111000100", "00010100000000", "01011100001101", "00001100110100", "10001010000110"}

    0

    0

    Returns: 0

  26. {"00001011111101", "10100111111110", "01101110001010", "00011101001010", "11101110011111", "11110100010111", "11000010111010", "11001111101101", "11001110001101", "10000101011100", "10011110011010", "11011000110101", "01001001101111", "10000010101010"}

    14

    0

    Returns: 63

  27. {"11111111001111", "11100010001110", "11101011100000", "01111111110010", "10011011110111", "10001010001101", "11110111100101", "01101111111111", "11101111110011", "10110100000100", "11111111110011", "01110000001111", "01101110111111", "11011011011011"}

    0

    14

    Returns: 46

  28. {"10000110011101", "00101101011111", "10011101111001", "01010000110010", "01010110111101", "01111111010101", "10110010110101", "11101110010001", "11001011001001", "11101010111111", "10100101000110", "11010011001111", "10011100111111", "10110110111110"}

    14

    14

    Returns: 58

  29. {"00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000"}

    5

    5

    Returns: 0

  30. {"00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000", "00000000000000"}

    7

    8

    Returns: 0

  31. {"11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111"}

    5

    7

    Returns: 0

  32. {"11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111", "11111111111111"}

    6

    7

    Returns: 0

  33. {"00000101011110", "01010110010100", "01011100001100", "10110100011110", "00110101010000", "10001000111011", "11100001111000", "10100010100110", "00000000111111", "01001101011100", "10001100110111", "01101110110100", "10101010110110", "11000111001101"}

    6

    5

    Returns: 24

  34. {"01000111010000", "01111110000111", "10111000110101", "01111101111111", "10100110011010", "10010100010010", "11100010001000", "11001001110110", "11000000110010", "01111000101101", "01001010101110", "00111010001001", "11000110011100", "10101100110111"}

    8

    6

    Returns: 31

  35. {"00010001000100", "10000110011110", "10110101011110", "10000001110010", "10111100101001", "10110010110001", "11100111100011", "11001101101111", "00000011000110", "01110111010111", "00101011010111", "00111110010111", "00011001110111", "01001011011001"}

    5

    7

    Returns: 22

  36. {"10001001100101", "01110000100000", "11101101111101", "01010111001111", "01111110101000", "11011001110101", "01001111001100", "10110011110011", "11111111101101", "11010000011100", "10101001000011", "00011111010101", "11010111000011", "01111000100111"}

    7

    7

    Returns: 32

  37. {"01100111110001", "01111101000101", "00010011100100", "01110111001000", "01101010100110", "10000100000101", "10110110111001", "11011101111010", "10010101100110", "00100000011111", "11000000101101", "00001001001001", "10110110011010", "11101011111101"}

    7

    7

    Returns: 29

  38. {"11011001001111", "10111011000011", "00101101011110", "01001111010100", "10111001111111", "11010111010010", "01010110101100", "01010111000100", "00011001110011", "11000011011100", "10110000001000", "10100010100001", "01001110001000", "10100100001101"}

    5

    6

    Returns: 24

  39. {"01101001001110", "01011110001111", "11000101011111", "11111010111100", "10111010111010", "00110111110011", "01111101101000", "01000010110101", "11110101001110", "00100011111010", "01111101110101", "01110010101001", "00101111100101", "01001011111110"}

    5

    5

    Returns: 23

  40. {"10010110011100", "01100101101000", "00101101000011", "00000111100100", "11110001000101", "00011010011101", "10111110010100", "00101000011011", "10011000011111", "01000100110001", "11111011101001", "00100110001010", "00010010100111", "10101101001011"}

    7

    6

    Returns: 27

  41. {"01100011111000", "10001101000101", "00000100110010", "10001110001111", "10101011000010", "00110001011101", "11011001000110", "11001000011111", "00000111010010", "11011001111000", "00001010110100", "00011010100000", "01010111111010", "00011011101101"}

    7

    8

    Returns: 32

  42. {"00000110100011", "10000010010001", "00010111010100", "10010000110011", "01011101100010", "11001101011100", "00101111101100", "10001011000001", "01000010000010", "11100000101110", "10110010101000", "01010101100101", "00111111100111", "11111000000100"}

    10

    14

    Returns: 58

  43. {"10100000010011", "11110100011110", "00000010001100", "11100000101111", "10001100101111", "01010010010011", "00000000101110", "00100001001101", "01000100100110", "01001100111001", "11111100100001", "10111111100101", "10001010111110", "01001100010110"}

    14

    13

    Returns: 52

  44. {"11101100001001", "01111100110111", "01111110111110", "01011010000011", "10100100001011", "10011010100111", "00001000001011", "10010001011111", "01001001011010", "11001101110110", "00011101011111", "10000001001010", "10110111000101", "10011111111111"}

    11

    12

    Returns: 55

  45. {"00111000010011", "10111100111100", "00001100110010", "01000111001010", "10011110100010", "10101111111000", "00100011111111", "01011100011111", "11011001010011", "01010110110010", "11100011111111", "11101000010110", "00111001011010", "00100000101111"}

    11

    14

    Returns: 54

  46. {"11010110100110", "10100000010011", "01111110011011", "00011000000001", "00010110001010", "10000001111110", "00101111101000", "10010011011000", "00000010101001", "10111010111101", "11010101000010", "01010001101000", "11100110010011", "01101110111000"}

    11

    11

    Returns: 50

  47. {"10101011111110", "10001011010100", "00011001000110", "01100011101101", "01110110011001", "11111011000000", "00010111011010", "10111001100100", "00001010110100", "01111011010001", "00011101111110", "01110110101100", "01011000110000", "10111010011001"}

    12

    12

    Returns: 50

  48. {"10011111100100", "10011001011110", "01100101010100", "11011111100101", "00011111011111", "11001001011000", "00111010111000", "11100101100000", "00011010111000", "10100110011010", "01001111110011", "11111110011111", "11110110011011", "00101011101101"}

    11

    10

    Returns: 44

  49. {"11010011101000", "00000100111000", "10001110011101", "10001110110101", "01110001111011", "11111000001000", "10110000111100", "10010110011100", "11000001011000", "01001110100101", "00110010000101", "11101000101010", "10100101110110", "01001100101011"}

    13

    13

    Returns: 64

  50. {"00100111000110", "01011110100010", "00011011011000", "11100010000000", "01100011110101", "11001101111010", "10101000110100", "11101010111000", "00000000010100", "00101110010001", "11010011101011", "01010100110100", "01010001111001", "00000000101110"}

    14

    14

    Returns: 56

  51. {"00100111011011", "11001011010010", "10001100110000", "10111010000000", "00000110101111", "11010000001110", "01000010101010", "10110010000100", "11000011100101", "11000001101011", "01010000001110", "11110100111101", "01101001001000", "11001100101101"}

    14

    12

    Returns: 56

  52. {"10000111100001", "01101111110110", "10110111101101", "01010100101010", "00011100111000", "01111011011110", "01110111101110", "01110111101110", "01111011011110", "00011100111000", "01010100101010", "10110111101101", "01101111110110", "10000111100001"}

    7

    7

    Returns: 0

  53. {"00100100100000", "01000000000010", "01010111101010", "11000111100111", "11110011001111", "01100000100110", "10111111111101", "10111111111101", "01100100100110", "11110011001111", "11100111100111", "01010111101010", "01000000000010", "00100100100100"}

    7

    7

    Returns: 0

  54. {"01111111111110", "00010000001010", "10010000011001", "00000011100000", "10011111111001", "11001100110011", "11001011010011", "11001011011011", "11001100110111", "10011111111001", "00000111100000", "10010000011001", "00010000001000", "01111111111110"}

    7

    7

    Returns: 0

  55. {"01010100101000", "00110100100000", "00100100100100", "10111111111101", "00111111111100", "10001011010101", "01101100010110", "01101100110110", "10101011010101", "00111111111100", "10011111111001", "00100100100100", "00000100100010", "01010100100010"}

    7

    7

    Returns: 0

  56. {"11110111101111", "01111111111111", "01011100110011", "00111011011110", "10010111101001", "00111100110000", "00110011001000", "00110011001100", "00111100111100", "10010111101001", "01111011011110", "11011100111011", "01111110111110", "11110111101111"}

    7

    7

    Returns: 0

  57. {"10011111011001", "11101100110101", "00001111110000", "10011111001001", "00001000010000", "00001111111010", "00010101101000", "00010101111000", "00011111110000", "00001000010100", "11111010011001", "00001111111000", "11101100110111", "10011111111001"}

    7

    7

    Returns: 3

  58. {"00100111010110", "01010010001000", "01011011011010", "00111101111100", "10101011110101", "10101100100101", "01011000011000", "00001000011000", "10101100110101", "10111011010101", "11111011111100", "01011001011010", "00010011001000", "10101011010100"}

    7

    7

    Returns: 4

  59. {"10001011011001", "01001000010011", "01100011010100", "00101000010100", "10101111111001", "10100101000010", "00011100111010", "00010100001000", "00100100101000", "10011111111001", "00101000000100", "00101111010100", "01001000011010", "10011011111001"}

    7

    7

    Returns: 7

  60. {"01001000010010", "00111000000101", "00100011000000", "01011011111011", "10010100100001", "01101111100110", "01111011010110", "01101010100100", "01100010100110", "10010100101001", "01011111101011", "01010011000000", "00100000000100", "01001010000011"}

    7

    7

    Returns: 7

  61. {"10001100110001", "11010111101011", "10011001111001", "10110011100000", "11010000001010", "10001011000101", "11011100011111", "11011001011011", "10101011010101", "01010001111010", "00010100101000", "00011101111001", "11010011101111", "11001110110001"}

    7

    7

    Returns: 6

  62. {"01001110001101", "11010110010100", "11001101001100", "10011110000110", "11100010111000", "00110101010011", "11111001100000", "00000110011111", "11001010101100", "00011101000111", "01100001111001", "00110010110011", "00101001101011", "10110001110010"}

    14

    14

    Returns: 98

  63. {"10011001100110", "10010001110110", "10101010101010", "01010001110101", "00110110010011", "10110101010010", "10111001100010", "01000110011101", "01001010101101", "11001001101100", "10101110001010", "01010101010101", "01101110001001", "01100110011001"}

    14

    14

    Returns: 98

  64. {"11011010100100", "00000001111111", "00001110001111", "11001101001100", "10101101001010", "00011110000111", "11100101011000", "00011010100111", "11100001111000", "01010010110101", "00110010110011", "11110001110000", "11111110000000", "00100101011011"}

    14

    7

    Returns: 98

  65. {"00111001100011", "01011110000101", "10110110010010", "10011101000110", "01000001111101", "11000110011100", "11100101011000", "00011010100111", "00111001100011", "10111110000010", "01100010111001", "01001001101101", "10100001111010", "11000110011100"}

    14

    7

    Returns: 98

  66. {"11110101010000", "11100010111000", "01100110011001", "11010010110100", "01110001110001", "00010010110111", "01011010100101", "10100101011010", "11101101001000", "10001110001110", "00101101001011", "10011001100110", "00011101000111", "00001010101111"}

    7

    14

    Returns: 98

  67. {"11001001101100", "01001001101101", "00101001101011", "00110010110011", "00111010100011", "11110110010000", "00100010111011", "11011101000100", "00001001101111", "11000101011100", "11001101001100", "11010110010100", "10110110010010", "00110110010011"}

    11

    12

    Returns: 92

  68. {"11111101001110", "11000111111111", "00010101111001", "10110000111111", "10000011010010", "10001101101101", "00101110000011", "10111010100100", "11010011110111", "11100010110110", "00100101010100", "01011011001010", "01010101111010", "10100010010011" }

    7

    7

    Returns: 30

  69. {"11010000111010", "01101001001101", "01100001010100", "11110011000010", "00010110111110", "11000000001101", "10010000111000", "11001100111110", "10011100000000", "00110001100010", "11010111101100", "10000010010001", "10011101000111", "00100110010100" }

    7

    7

    Returns: 28

  70. {"11001000001111", "11101010010010", "01101010111011", "01101110100111", "11100100000000", "01010001101100", "00001001011000", "11111000101011", "00011110001011", "10100010001111", "11111110100000", "10010101010111", "00100001010010", "11000011010111" }

    7

    7

    Returns: 28

  71. {"01101111011111", "11000001101000", "00001001100000", "00101101100011", "10100010001001", "11000101000011", "10110100010100", "00110000110000", "11110110110010", "00000110110011", "01011010001111", "11111000101011", "01001111001110", "00110110100001" }

    8

    9

    Returns: 42

  72. {"01110010010101", "10111100111011", "00111101101011", "01010001001001", "00000001100101", "01111001100100", "10010111011000", "00010100111011", "00011110110000", "01101000000111", "11011111010100", "10001100111111", "11110100111110", "00111010100011" }

    7

    7

    Returns: 26

  73. {"00101101010001", "11110101010001", "10010101011110", "01011101111100", "00111100010000", "10101110101101", "11011101101010", "00001010111000", "11111001011010", "01000100110101", "00010001100010", "00010101011011", "10010100111000", "00001001110110" }

    7

    7

    Returns: 27

  74. {"11111101001110", "11000111111111", "00010101111001", "10110000111111", "10000011010010", "10001101101101", "00101010000001", "10111010100100", "11010011110111", "11100010110110", "00100101010100", "01001011001000", "01010001111010", "10100000010011" }

    7

    7

    Returns: 30

  75. {"11100000110100", "11110011110110", "01100101111110", "10110101110000", "00010010111001", "01111010111011", "11101001100001", "00111010110011", "11100100010010", "10000100111011", "01010001100011", "01101010100000", "00001000011111", "01110110001110" }

    7

    7

    Returns: 31

  76. {"01010101010101", "10101010101010", "01010101010101", "10101010101010", "01010101010101", "10101010101010", "01010101010101", "10101010101010", "01010101010101", "10101010101010", "01010101010101", "10101010101010", "01010101010101", "10101010101010" }

    8

    7

    Returns: 56

  77. {"00000000000000", "10010010110110", "10010010110110", "00000000000000", "00000000000000", "10010010110110", "00000000000000", "10010010110110", "10010010110110", "00000000000000", "00000000000000", "00000000000000", "10010010110110", "10010010110110" }

    7

    7

    Returns: 0

  78. {"00010001111111", "00000001111111", "00100001110111", "00000001111111", "00000001111111", "00000001101111", "00000001111111", "11111110000000", "11111110001000", "11111110000000", "11111110000000", "11111110000000", "11111110000000", "11111110000000" }

    2

    5

    Returns: 35

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: