Hi community,
Recently I came across a problem:
There is a chess contest between N players. Each chess player has a distinct rank (positive integer number from 1 to N). We assume that in a chess game between two players, the player ranked higher always wins. The ranks remain constant during the contest. Unfortunately, we don't know the player ranks. But we know the outcome of M games in the following format: Player #1 won #2 Player #2 won #4 .... Given the results of M games above, are there any players whose rank can be precisely determined? If so, find their ranks.
I'll be grateful if someone can help with approach to this problem, given that we can have multiple nodes with indegree 0 and outdegree 0.
So here is the approach.
Make two graphs G and G rev. G has edges from lose to win player.
Obtain a top-sort order on this acyclic graph.
Now start from the beginning of this top sort order. For each vertex (say u is curr) the current number in its component-1 is the number of players it has won from in total. Now add all the edges in G from u with DSU. And continue to next vertex.
You get the total number of players each person has won from.
Now similarly start from the ending of the top sort order. Say the curr vertex is u. The current number of vertices in u's component-1 is the total number of players it has lost to. Add the edges from u in G rev by DSU. And continue to the next vertex.
Now you get the total number of players each players has lost to.
If the sum of both for any vertex is n-1 its rank is its top sort rank. Otherwise his/her rank can't be determined and is -1.
Have you previously used this technique in a problem? My belief is that it is not possible to count reachable nodes for all vertices in linear time due to overcounting nodes which can accessed in multiple ways from the current node
Someone else said something similar here: https://mirror.codeforces.com/blog/entry/80649
+1 to this
Can I just do DSU to maintain a component size, then when I add edges I would not count duplicates and I think DSU works in nlogn? I am not sure about order of edges is it O(n**2). But then also wouldn't our time complexity O(n**2logn) suffice?
Also like in rank calculation if a person's rank can be determined then his position in top sort would be fixed. You can say rank would be N+1-topsort order rank.
I love your creative approach but I would like to clarify one important thing. So, you said "If the sum of both for any vertex is n-1 its rank is its top sort rank..." I personally think thats not correct. According to the question, it should be something like this:
If a player X has lost to Y other players, it means there are Y players ranked who are absolutely higher. So, the rank of player X is Y + 1.
Your approach is fair, but I think the rank calculation is the most important part to focus first. Very good try though!
We can create individual graphs where each player is a node (suppose). An edge from player A to player B means that A won against B, which also means that rank of A is higher than B. Since higher-ranked player always wins and A is so far the highest, A can beat B and C ofcourse (this scenario makes it transitive if I correctly recall from sets).
To find all such win-loss relations, you need to calculate transitive closure of the graph. This can be done either using BFS or DFS from each node to find all reachable nodes. After calculating transitive, for each player, you can count number of players they have won against and the number of players they have lost against. A player's rank can be determined if and only if the total number of players they have won against and lost against is equal to N-1. If this condition holds for a player, it means their position relative to every other player is known. The rank of such a player will be the number of players who have a higher rank + 1.
Although, I would love to see the full question and if any examples included. Hopefully my approach gives a basic idea.
Is there a judge with this problem? I'd like to try "generate ~50 random topo-sorts and return the items in the same position each time"
My reasoning is: for any node x consider the decisions that affect its placement [d1, d2, d3, ...]. The final decision will be between at least 2 different options sampled uniformly so if its position is not fixed, no option will have probability greater than 1/2 so the probability of a false positive is halved with each iteration