PalindromeMatrixDiv2

SRM 600 · 2013-06-25 · by ir5

SRM 600 · 2013-06-25 · by ir5 · Brute Force

Show categories

Class Name: PalindromeMatrixDiv2

Return Type: int

Method Name: minChange

Arg Types: (vector<string>, int, int)

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.

Constraints

N and M will be between 2 and 8, 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"}
2
2
Returns: 8

Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PalindromeMatrixDiv2 with a public method int minChange(vector<string> A, int rowCount, int columnCount) · 72 test cases · 2 s / 256 MB per case