PalindromeMatrix | Topcoder Archive

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".)

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

```
{"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).
```
{"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.
```
{"01"
,"10"}
```
```
1
```
```
1
```
```
Returns: 1
```
```
{"1110"
,"0001"}
```
```
0
```
```
0
```
```
Returns: 0
```
Here, we do not have to change A at all.

{"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"
,"01010101"}

Returns: 8

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

Returns: 14

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

Returns: 31

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.