ExamSeating | Topcoder Archive

Problem Statement

There is a bunch of students. Each student needs to take exactly one exam. There are 26 different exams, labelled 'a'-'z'. You are given the String students with the exam of each student.

Due to some unforeseen circumstances there is only one qualified proctor. All students will therefore have to take their exams in the same classroom.

A classroom is a rectangular grid of seats. In order to prevent cheating, two students who are taking the same exam can never sit next to each other (horizontally or vertically).

The proctor can book a classroom of any size, as long as both the number of rows and the number of seats in each row is at most 50.

Find the classroom with the smallest area sufficient for all students to take the exam. Return a String[] with one possible seating plan. Use '-' (dash) for seats that are left empty.

Any solution with the optimal area will be accepted. If no solution exists, return an empty String[].

Definition

Class:: ExamSeating
Method:: distribute
Parameters:: String
Returns:: String[]
Method signature:: String[] distribute(String students)
(be sure your method is public)

Notes

Remember that a valid seating plan must be at most 50 x 50. If no such plan exists, you are supposed to return an empty String[] instead.
The returned seating plan must be rectangular, i.e., all elements of the return value must have the same length.
The returned seating plan must contain exactly the correct number of seats for each of the 26 exams.
The proctor does not need a seat in the classroom.

Constraints

students will have between 1 and 2,500 characters, inclusive.
Each character in students will be a lowercase English letter ('a'-'z').

Examples

```
"aabcda"
```
```
Returns: {"a", "c", "a", "d", "a", "b" }
```
A classroom with six rows with one seat in each of them. Everyone's neighbors are taking a different exam.
```
"aabb"
```
```
Returns: {"ab", "ba" }
```
A 2x2 classroom. Students taking the same exam may be diagonally adjacent.

"zzz"

Returns: {"z", "-", "z", "-", "z" }

We need to leave some empty seats.

```
"qwertyuiopasdfghjklz"
```
```
Returns: {"qwert", "yuiop", "asdfg", "hjzkl" }
```
As each student writes a different exam, we just need to minimize the classroom area, any seating plan works.

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.