Problem P
Tournament Ranking
The Extreme Hockey League (XHL) debuted this year! Each team will play every other team exactly once during the regular season before playoffs begin. Unfortunately, due to low ratings the XHL was cancelled immediately after the regular season. No playoffs will take place.
You, the XHL commissioner, want to give the very few loyal fans some closure by declaring a winner. In fact, you want to give a complete ranking of the teams. Instead of using a traditional scoring system to determine the ranking of the teams, you simply look for a ranking that minimizes disagreement with the outcomes of the games played in the regular season.
Concretely, your task is to find a permutation $a_1, a_2, \ldots , a_N$ of teams $1, 2, \ldots , N$. Here, $a_i$ is the team that you declare finished in $i$’th place this season (so $a_1$ will be the winning team). Among all such permutations, you should pick one with the minimum number of pairs of indices $1 \leq i < j \leq N$ such that team $a_i$ lost to team $a_j$ during the regular season.
If there are multiple permutations having the minimum number of disagreements with the games played in the regular season, you should pick the lexicographically smallest one (i.e. the one with minimum value $a_1$, breaking ties by the minimum value $a_2$, and so on).
Oh, one last thing. This is very important! If it is not possible to find a ranking having at most $8$ disagreements with the games played in the regular season then you should just abandon the task entirely.
Input
The first line of input contains a number $N$ ($3 \leq N \leq 1000$) indicating the number of teams in the XHL. The next $N$ lines each contain $N$ integers. If we let $w_{i,j}$ denote the $j$’th integer on the $i$’th line, then $w_{i,j}$ will either be $0$ or $1$ for each $1 \leq i, j \leq N$.
For $i \neq j$, we have $w_{i,j} = 1$ if team $i$ beat team $j$ during the regular season and, otherwise, $w_{i,j} = 0$. You are guaranteed $w_{i,i} = 0$ for each team $i$ and also that $w_{i,j} + w_{j,i} = 1$ for each pair of distinct teams $i,j$.
Output
Say $K$ is the smallest integer such that there is a permutation $a_1, a_2, \ldots , a_N$ of teams that disagrees with at most $K$ games played during the regular season.
If $K \leq 8$, you should output two lines. The first line contains just the value $K$ and the second is the lexicographically-minimum permutation $a_1, a_2, \ldots , a_N$ having $K$ disagreements with games played in the regular season.
If $K > 8$ then simply output a single line containing $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 |
1 1 2 3 4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 |
2 1 4 2 3 5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 |
-1 |
