EvenMatrices | Topcoder Archive

Problem Statement

Each matrix in this problem is a binary matrix, i.e., each element of the matrix is either 0 or 1. Each matrix in this problem has r rows and c columns.

A binary matrix is called even if each row and each column of the matrix contains an even number of 1s.

Lexicographic order on binary matrices of fixed dimensions is defined as follows: Given two distinct matrices, we find the first element in row major order on which they differ. The one with a 0 on that location is smaller.

For example, any matrix that starts like the one on the left is smaller than any matrix that is an extension of the one on the right:

11101    11101
010..    011..
.....    .....

You are given the ints r and c, and a long k. Imagine that we took all even matrices with r rows and c columns, we sorted them lexicographically, and then we numbered them starting from 0.

Find and return the matrix that will receive the number k. Return it formatted as a String[] with r elements, each containing c characters. If there is no matrix that will receive the number k (i.e., k is too large), return an empty String[] instead.

Definition

Class:: EvenMatrices
Method:: findKth
Parameters:: int, int, long
Returns:: String[]
Method signature:: String[] findKth(int r, int c, long k)
(be sure your method is public)

Constraints

r will be between 1 and 50, inclusive.
c will be between 1 and 50, inclusive.
k will be between 0 and 10^15, inclusive.

Examples

```
2
```
```
2
```
```
0
```
```
Returns: {"00", "00" }
```
There are only two even matrices that have two rows and two columns. The smallest one (matrix #0) is {"00", "00"} Then, matrix #1 is {"11", "11"} There is no matrix #2.
```
2
```
```
3
```
```
2
```
```
Returns: {"101", "101" }
```
```
3
```
```
2
```
```
3
```
```
Returns: {"11", "11", "00" }
```
```
4
```
```
5
```
```
12345678901
```
```
Returns: { }
```

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.