Good ranking solution codechef
The tennis tournament you organized has just finished and now you have to decide the ranking of theplayers (indexed by ) who participated. Each pair of players played exactly one game and for each game you know who won (there are no draws in tennis).
A ranking is a permutationof ; where represents the winner of the tournament, is the second in the ranking, etc.
A ranking is good if for anythe player won against . In other words, a ranking is good if, for any two players whose ranking positions differ by at most , the result of their game is consistent with their order in the ranking.
Find, if it exists, a good ranking. Good ranking solution codechef
- The first line contains a single integer , the number of test cases. Then test cases follow.
- The first line of each test case contains one integer , the number of participants.
- Then lines follow. The -th of them contains a string of length whose characters are either 0 or 1. For any with , the -th character of is 0 if lost against and 1 otherwise. It is guaranteed that for any the -th character of is different from the -th character of (so that they are consistent). For any , the -th character of is 0 (notice that this character does not correspond to any game in the tournament).
Output Format Good ranking solution codechef
For each test case, printif a good ranking does not exist.
If a good ranking exists, print on a single line theintegers corresponding to a good ranking ( is the winning player, is the runner-up, is the third in the ranking, etc.).
If there is more than one good ranking, print any of them.
- The sum of over all test cases does not exceed .
Sample Input 1
5 1 0 2 00 10 3 010 001 100 6 001001 101000 000000 111011 111001 011000 7 0101011 0001100 1100011 0010100 1010011 0101000 0101010
Sample Output 1 Good ranking solution codechef
1 2 1 -1 -1 5 3 1 7 6 2 4
Explanation of the first testcase: There is only one participant and the only possible ranking is good.
Explanation of the second testcase: There are two participants and the participantwon against the participant . Thus the ranking (that is, player wins the tournament) is good.
Explanation of the third testcase: One may check that there is not a good ranking. Let us explain why some possible rankings are not good:
- The ranking is not good because for , (notice that since ) the result of the game between and is not consistent with their ranking positions (player lost against player but has a better ranking position).
- The ranking is not good because for , (notice that since ) the result of the game between and is not consistent with their ranking positions.