Statistics

Problem Statement for "ExamVersions"

Problem Statement

There is a classroom with seats arranged into a rectangle. There are R rows of seats. Each row consists of C seats.

An exam is going to take place in the classroom. There are R*C students waiting to take the exam: one in each seat.

The teacher has prepared N different versions of the exam. The versions are labeled using the first N uppercase English letters: 'A', 'B', 'C', ...

In order to prevent cheating, no two students who are adjacent (either horizontally or diagonally) should have the same version of the exam.


You are given R, C and N. Determine whether it is possible to distribute the exam versions to the students in such a way that cheating is prevented.

If yes, return a String[] with any one valid arrangement. (R elements, each containing C characters. In element r, character c should be the exam version for the student sitting in row r, column c.) If no, return an empty String[].

Definition

Class:
ExamVersions
Method:
distribute
Parameters:
int, int, int
Returns:
String[]
Method signature:
String[] distribute(int R, int C, int N)
(be sure your method is public)

Notes

  • Formally, a student in row r1, column c1 and another student in row r2, column c2 are adjacent if and only if both abs(r1-r2) <= 1 and abs(c1-c2) <= 1.
  • You can use arbitrarily many copies of each exam version, including zero.

Constraints

  • R will be between 1 and 50, inclusive.
  • C will be between 1 and 50, inclusive.
  • N will be between 1 and 26, inclusive.

Examples

  1. 1

    8

    25

    Returns: {"TOPCODER" }

    You are not required to use all available exam versions. There are many other valid solutions.

  2. 3

    5

    7

    Returns: {"CAGEB", "FDCFG", "EBAED" }

    The classroom corresponding to the return value looks as follows: CAGEB FDCFG EBAED We can easily verify that only letters 'A'-'G' are used and no two equal letters are horizontally or diagonally adjacent.

  3. 5

    1

    3

    Returns: {"B", "A", "C", "B", "C" }

  4. 7

    4

    2

    Returns: { }

    Two exam versions are not enough to prevent cheating in this classroom.

  5. 7

    4

    3

    Returns: { }

  6. 7

    4

    4

    Returns: {"ABAB", "CDCD", "ABAB", "CDCD", "ABAB", "CDCD", "ABAB" }

  7. 2

    2

    3

    Returns: { }

  8. 2

    2

    4

    Returns: {"AB", "CD" }

  9. 1

    7

    3

    Returns: {"ABABABA" }

  10. 1

    7

    2

    Returns: {"ABABABA" }

  11. 1

    7

    1

    Returns: { }

  12. 8

    1

    3

    Returns: {"A", "B", "A", "B", "A", "B", "A", "B" }

  13. 8

    1

    2

    Returns: {"A", "B", "A", "B", "A", "B", "A", "B" }

  14. 8

    1

    1

    Returns: { }

  15. 44

    33

    1

    Returns: { }

  16. 1

    1

    2

    Returns: {"A" }

  17. 1

    1

    1

    Returns: {"A" }

  18. 50

    50

    4

    Returns: {"ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD" }

  19. 50

    49

    7

    Returns: {"ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC", "ABABABABABABABABABABABABABABABABABABABABABABABABA", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC" }

  20. 49

    50

    5

    Returns: {"ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABABAB" }

  21. 47

    48

    26

    Returns: {"ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCD", "ABABABABABABABABABABABABABABABABABABABABABABABAB" }

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: