Connection Status:
Competition Arena > EvenMatrices

EvenMatrices

TCO19 SRM 740 · 2018-10-19 · by misof

TCO19 SRM 740 · 2018-10-19 · by misof · Math
Class Name: EvenMatrices
Return Type: String[]
Method Name: findKth
Arg Types: (int, int, long long)
Problem Statement

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.

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

1)
2
3
2
Returns: {"101", "101" }
2)
3
2
3
Returns: {"11", "11", "00" }
3)
4
5
12345678901
Returns: { }
4)
4
7
159
Returns: {"0000000", "0000101", "0111111", "0111010" }

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

Coding Area

Language: C++17 · define a public class EvenMatrices with a public method vector<string> findKth(int r, int c, long long k) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous