Connection Status:
Competition Arena > TheContest

TheContest

SRM 459 · 2009-11-12 · by gojira_tc

SRM 459 · 2009-11-12 · by gojira_tc · Graph Theory
Class Name: TheContest
Return Type: String[]
Method Name: getSchedule
Arg Types: (int, int)
Problem Statement

Problem Statement

A contest is held between two teams of fighters. The first team is comprised of N persons and the second is comprised of M persons. In the course of the contest, each fighter of the first team will confront each fighter of the second team once. To make the contest more entertaining and less protracted, the organizers divided it into several rounds. In each of the rounds, several fights occur simultaneously. Therefore, a fighter may only participate in one fight per round.

The contest must be divided into the least number of rounds. One can easily see that this number is the maximum between N and M. Now the exact schedule of fights must be determined. Return a String[] containing exactly N elements. Each element of the return must contain exactly M characters from the set {'1'-'9', 'A'-'Z', 'a'-'o'}. Letters 'A'-'Z' stand for numbers 10-35 and 'a'-'o' stand for numbers 36-50. The j-th character of element i corresponds to the number of the round in which fighter i of the first team encounters fighter j of the second team. If there are several possible schedules, return the one with the lexicographically least first element. If there still are multiple choices, choose the schedule with the lexicographically least second element, and so on.

Notes

  • A string A is lexicographically less than another string B of the same length if there exists a position i such that each character of A before the i-th position is equal to the character at the corresponding position in B, and A[i] is less than B[i]. When comparing the characters, refer to the following list of characters in ascending order: '1', '2', ..., '9', 'A', 'B', ..., 'Z', 'a', 'b', ..., 'o'.

Constraints

  • N will be between 1 and 50, inclusive.
  • M will be between 1 and 50, inclusive.
Examples
0)
3
3
Returns: {"123", "231", "312" }

There are three persons on each team, so the whole contest is divided into three rounds. If we denote the i-th person of the first team as Ai and the j-th person of the second team as Bj, the fights schedule for each of the rounds is: Round 1: A1-B1, A2-B3, A3-B2 Round 2: A1-B2, A2-B1, A3-B3 Round 3: A1-B3, A2-B2, A3-B1

1)
4
4
Returns: {"1234", "2143", "3412", "4321" }

This time, both teams comprise of four persons, so the contest takes 4 rounds to finish. Round 1: A1-B1, A2-B2, A3-B3, A4-B4 Round 2: A1-B2, A2-B1, A3-B4, A4-B3 Round 3: A1-B3, A2-B4, A3-B1, A4-B2 Round 4: A1-B4, A2-B3, A3-B2, A4-B1

2)
4
6
Returns: {"123456", "214365", "345612", "436521" }

The competition now is held in 6 rounds. Note that since the teams are of unequal size, two of the second team's fighters are taking rest in each of the rounds. Round 1: A1-B1, A2-B2, A3-B5, A4-B6 Round 2: A1-B2, A2-B1, A3-B6, A4-B5 Round 3: A1-B3, A2-B4, A3-B1, A4-B2 Round 4: A1-B4, A2-B3, A3-B2, A4-B1 Round 5: A1-B5, A2-B6, A3-B3, A4-B4 Round 6: A1-B6, A2-B5, A3-B4, A4-B3

3)
5
3
Returns: {"123", "214", "345", "451", "532" }
4)
28
40
Returns: {"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcde", "21436587A9CBEDGFIHKJMLONQPSRUTWVYXaZcbed", "34127856BC9AFGDEJKHINOLMRSPQVWTUZaXYdebc", "43218765CBA9GFEDKJIHONMLSRQPWVUTaZYXedcb", "56781234DEFG9ABCLMNOHIJKTUVWPQRSbcdeXYZa", "65872143EDGFA9CBMLONIHKJUTWVQPSRcbedYXaZ", "78563412FGDEBC9ANOLMJKHIVWTURSPQdebcZaXY", "87654321GFEDCBA9ONMLKJIHWVUTSRQPedcbaZYX", "9ABCDEFG12345678PQRSTUVWXYZabcdeHIJKLMNO", "A9CBEDGF21436587QPSRUTWVYXaZcbedIHKJMLON", "BC9AFGDE34127856RSPQVWTUZaXYdebcJKHINOLM", "CBA9GFED43218765SRQPWVUTaZYXedcbKJIHONML", "DEFG9ABC56781234TUVWPQRSbcdeXYZaLMNOHIJK", "EDGFA9CB65872143UTWVQPSRcbedYXaZMLONIHKJ", "FGDEBC9A78563412VWTURSPQdebcZaXYNOLMJKHI", "GFEDCBA987654321WVUTSRQPedcbaZYXONMLKJIH", "HIJKLMNOPQRSTUVWXYZabcde123456789ABCDEFG", "IHKJMLONQPSRUTWVYXaZcbed21436587A9CBEDGF", "JKHINOLMRSPQVWTUZaXYdebc34127856BC9AFGDE", "KJIHONMLSRQPWVUTaZYXedcb43218765CBA9GFED", "LMNOHIJKTUVWPQRSbcdeXYZa56781234DEFG9ABC", "MLONIHKJUTWVQPSRcbedYXaZ65872143EDGFA9CB", "NOLMJKHIVWTURSPQdebcZaXY78563412FGDEBC9A", "ONMLKJIHWVUTSRQPedcbaZYX87654321GFEDCBA9", "PQRSTUVWXYZabcde9ABCDEFGHIJKLMNO12345678", "QPSRUTWVYXaZcbedA9CBEDGFIHKJMLON21436587", "RSPQVWTUZaXYdebcBC9AFGDEJKHINOLM34127856", "SRQPWVUTaZYXedcbCBA9GFEDKJIHONML43218765" }

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

Coding Area

Language: C++17 · define a public class TheContest with a public method vector<string> getSchedule(int N, int M) · 138 test cases · 2 s / 256 MB per case

Submitting as anonymous