LCC '18 Contest 2 S3 - Earth Rumble

View as PDF

Submit solution

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

Problem type

The Earth Rumble tournament is a king-of-the-hill style tournament where two competitors face each other in each round and the winner moves on to face a new competitor in the next round. The winner of the final pairing is crowned the Earthbending champion.

The strengths of each competitor are mostly set it stone, so the organisers of the tournament know who the winner would be in any pairing of competitors. They would like to make their tournament as exciting as possible by ordering the competitors so that no person wins two rounds in a row. Could you help them find such an ordering?

Input Specification

The first line of input contains one integer N (2 \le N \le 2 000), the number of competitors. The next N lines each contain N integers such that the j^\text{th} entry of the i^\text{th} line is 1 if competitor i beats competitor j and 0 otherwise.

Output Specification

A single line containing an ordering of the competitors as described in the problem statement, or -1 if no such ordering exists.

Sample Input 1

0 1
0 0

Sample Output 1

1 2

Sample Input 2

0 0 1 1
1 0 1 1
0 0 0 1
0 0 0 0

Sample Output 2

3 4 1 2


There are no comments at the moment.