Statistics

Problem Statement for "EvenMatrices"

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

  1. 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. 2

    3

    2

    Returns: {"101", "101" }

  3. 3

    2

    3

    Returns: {"11", "11", "00" }

  4. 4

    5

    12345678901

    Returns: { }

  5. 4

    7

    159

    Returns: {"0000000", "0000101", "0111111", "0111010" }

  6. 1

    9

    0

    Returns: {"000000000" }

  7. 1

    9

    1

    Returns: { }

  8. 13

    1

    0

    Returns: {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" }

  9. 17

    1

    1

    Returns: { }

  10. 1

    1

    0

    Returns: {"0" }

  11. 1

    1

    1

    Returns: { }

  12. 1

    1

    4747474747474

    Returns: { }

  13. 7

    3

    623343336206222

    Returns: { }

  14. 9

    7

    576961242385158

    Returns: { }

  15. 8

    8

    46057578130756

    Returns: {"00010100", "01111000", "01110010", "11011000", "10101010", "10110100", "10001000", "01010000" }

  16. 8

    2

    115358343493115

    Returns: { }

  17. 2

    6

    542182894242796

    Returns: { }

  18. 10

    2

    918409682024771

    Returns: { }

  19. 7

    8

    267671939865456

    Returns: { }

  20. 10

    10

    497895626034723

    Returns: {"0000000000", "0000000000", "0000000000", "0000011101", "0010011010", "0101010111", "0111110111", "0011001111", "0001000111", "0010101111" }

  21. 5

    2

    421274276471298

    Returns: { }

  22. 7

    7

    647507370269352

    Returns: { }

  23. 5

    5

    946459560266692

    Returns: { }

  24. 2

    4

    110279014502210

    Returns: { }

  25. 7

    8

    608130897564602

    Returns: { }

  26. 6

    3

    981724936294389

    Returns: { }

  27. 5

    7

    530330615490088

    Returns: { }

  28. 3

    8

    397497525251683

    Returns: { }

  29. 6

    5

    625174619754156

    Returns: { }

  30. 6

    7

    636563685769487

    Returns: { }

  31. 2

    9

    633586326488656

    Returns: { }

  32. 8

    6

    822146696966579

    Returns: { }

  33. 10

    5

    128280392460901

    Returns: { }

  34. 5

    8

    285007524599916

    Returns: { }

  35. 10

    4

    17104466250097

    Returns: { }

  36. 4

    10

    905596547979932

    Returns: { }

  37. 3

    3

    575599773495279

    Returns: { }

  38. 10

    9

    902826960562876

    Returns: {"000000000", "000000000", "000000110", "001101010", "000111010", "110010001", "010001110", "001010101", "101111001", "001100101" }

  39. 8

    7

    854762566287365

    Returns: { }

  40. 2

    6

    725410953398598

    Returns: { }

  41. 10

    9

    797347426046146

    Returns: {"000000000", "000000000", "000000101", "110101011", "001011100", "111010101", "000101110", "100100000", "110000101", "010101100" }

  42. 7

    2

    273617664414964

    Returns: { }

  43. 5

    7

    778887452138008

    Returns: { }

  44. 4

    4

    143976747005399

    Returns: { }

  45. 3

    4

    883950356317627

    Returns: { }

  46. 7

    10

    121690993573697

    Returns: {"0000000110", "0111010101", "1101011001", "1000111000", "0110111111", "1010000011", "1110001110" }

  47. 6

    9

    734787301907868

    Returns: { }

  48. 3

    8

    415735942853045

    Returns: { }

  49. 2

    6

    158119400124765

    Returns: { }

  50. 4

    10

    552800239487076

    Returns: { }

  51. 5

    9

    510699650221529

    Returns: { }

  52. 2

    3

    940993726959666

    Returns: { }

  53. 11

    36

    715538709716760

    Returns: {"000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000001010001010110000", "111010101101001110110011111000110000", "111010101101001110111001110010000000" }

  54. 4

    41

    801914351011414

    Returns: {"00000000000000000000000000000000000000000", "00000000000000000000000000000010110110010", "01010110001111000000100001000110010101100", "01010110001111000000100001000100100011110" }

  55. 5

    26

    25010123481215

    Returns: {"00000000000000000000000000", "00000000000000000000000000", "00000101101011111100011110", "11000011010100000011111111", "11000110111111111111100001" }

  56. 7

    21

    989947243519509

    Returns: {"000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000011100001000", "010110100000110111001", "101111011110000101010", "111001111101010011011" }

  57. 37

    21

    689781364676027

    Returns: {"000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000000000000000", "000000000010011100110", "010110100011110100111", "011011010101101110111", "001101110100000110110" }

  58. 48

    36

    619163134810978

    Returns: {"000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000000000000000000000", "000000000000000000001000110011001000", "000001001101011010101011011011000100", "000001001101011010100011101000001100" }

  59. 39

    50

    696915451566701

    Returns: {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000011", "00111100111010111010001011110110111011010011011010", "00111100111010111010001011110110111011010011011001" }

  60. 38

    7

    553104011302412

    Returns: {"0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000000", "0000011", "1111011", "1100000", "1011100", "0100001", "0001111", "1000010", "0110000", "0011000", "0000000" }

  61. 23

    37

    465531997396269

    Returns: {"0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000000000000000000", "0000000000000000000000011010011101100", "0110000111010101011000011101001011010", "0110000111010101011000000111010110110" }

  62. 28

    24

    340938397808733

    Returns: {"000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000000000", "000000000000000000001001", "110110000101001110100000", "001011101111000010111011", "111101101010001100010010" }

  63. 38

    50

    672907512501020

    Returns: {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000011", "00110010000000001011111010011111111010011000111000", "00110010000000001011111010011111111010011000111011" }

  64. 10

    6

    571818935606795

    Returns: { }

  65. 9

    31

    885921413588961

    Returns: {"0000000000000000000000000000000", "0000000000000000000000000000000", "0000000000000000000000000000000", "0000000000000000000000000000000", "0000000000000000000000000000000", "0000000000000000000000000000000", "0000000000110010010110111101100", "1001110010011111100111111000010", "1001110010101101110001000101110" }

  66. 31

    3

    911612970062736

    Returns: {"000", "000", "000", "000", "000", "110", "000", "110", "110", "011", "000", "011", "101", "110", "011", "101", "110", "110", "011", "000", "000", "000", "110", "011", "000", "110", "101", "011", "000", "000", "101" }

  67. 38

    35

    880017608404271

    Returns: {"00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000000000000000000000", "00000000000000000011001000000101111", "11000100001111000111101101001011111", "11000100001111000100100101001110000" }

  68. 20

    47

    565645003318591

    Returns: {"00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000010001", "00001001110011011111010111110111100101001111111", "00001001110011011111010111110111100101001101110" }

  69. 9

    50

    396529613416965

    Returns: {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "10110100010100100001111101100000000101010000001011", "10110100010100100001111101100000000101010000001011" }

  70. 23

    12

    25436783011674

    Returns: {"000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000000", "000000000011", "011100100011", "001110110010", "101010011001", "111010110101", "000010111110" }

  71. 39

    8

    517318807551264

    Returns: {"00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "00000000", "11101011", "10011111", "11110101", "10111101", "00010010", "11110101", "01000001", "10011010" }

  72. 31

    19

    613525933657748

    Returns: {"0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000000000000000000", "0000100010110111111", "1111101000110101011", "1000001110100101001", "0111000100100111101" }

  73. 49

    42

    59125852

    Returns: {"000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000000000000000000000000000000", "000000000000000111000011000110000010111001", "000000000000000111000011000110000010111001" }

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: