Mock CCC '22 Contest 2 J4 - Hockey Bracket

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

The hockey event at the Winter Olympics will be happening soon! UselessLeaf will bet with his friends about how the countries will place.

The tournament will be operating in a round-robin fashion. There are N countries competing, numbered from 1 to N, and they will be split into groups of size S. \frac{S(S-1)}{2} matches will then occur in each group, where each country in their group play against each other country in the group once, resulting in a total of \frac{(S-1)N}{2} matches. After a match, the winning country gains 3 points, while the losing country gains 0. If it is a tie, both countries gain 1 point.

The tournament ends when all \frac{S(S-1)}{2} \times \frac{N}{S} = \frac{(S-1)N}{2} matches have been played. The countries in each group will then be ranked by their points. If there is a tie, the lower-numbered country should be ranked better (for example, if country i and country j where i < j got the same number of points, country i should be ranked better than country j).

A time traveller has suddenly appeared and provided UselessLeaf with the results of the \frac{(S-1)N}{2} matches. He provides the two countries in the match, a and b, and the result of the match, an uppercase letter R where W means country a won the match, L means country b won the match, and T means the match ended in a tie.

UselessLeaf is participating in a bet where he has to guess the country that places K^\text{th} in each group and needs your help figuring this out!


1 \le N \le 2 \times 10^3

1 \le S \le N

N \equiv 0 \pmod{S}

1 \le K \le S

1 \le a, b \le N

R \in \{W,L,T\}

Subtask 1 [5/15]

S = N

Subtask 2 [10/15]

No additional constraints.

Input Specification

The first line will contain two space-separated integers N, the number of countries competing, and S, the number of countries in each group.

The next \frac{N}{S} lines will contain S space-separated integers, the countries that are in the \frac{N}{S}^\text{th} group.

The next \frac{(S-1)N}{2} lines will contain two space-separated integers a and b, the countries involved in this match, and one character R, the result of the match between country a and country b.

The next line will contain one integer K, where UselessLeaf must figure out which country placed K^\text{th} in each group.

Output Specification

Output \frac{N}{S} space-separated integers, the i^\text{th} integer being the country that placed K^\text{th} in the i^\text{th} group.

Sample Input

4 2
3 1
2 4
1 3 W
2 4 T

Sample Output

3 4


In group 1, since 1 beat 3, 1 is ranked 1, while 3 is ranked 2. In group 2, there is a tie for first and second in terms of points between 2 and 4, but 2 is the lower numbered country so is ranked 1, meaning 4 is ranked 2.