Can you rank players without playing every match?

Picture a neighborhood arm-wrestling tournament. Skill follows a strict order, so a stronger player always beats a weaker one. But time ran short, not everyone faced everyone, and only some results were recorded.

Luckily there's a clue: if "A beats B and B beats C", then even if A and C never met, you can be sure A beats C — the skill order is consistent.

Example: 5 players, recorded results P1>P2, P1>P3, P2>P4, P3>P4, P4>P5. 3 players get a fixed rank. (P1·P4·P5 fixed; P2·P3 never met, so undecided.)

The question: using only the recorded matches, how many players have their result against every other player fully decided, fixing their exact rank?

Why Floyd-Warshall? (The core idea)

"A→B→C implies A→C" — seen that before? It's graph reachability. Read each result as an arrow (a→b = a beats b), and "does i beat j?" becomes exactly "is there a path from i to j?"

We need this for every pair, so a tool that fills all source-to-destination relations in one pass — Floyd-Warshall — fits perfectly.

We change just one thing. Normally Floyd-Warshall adds distances and takes a minimum:

•Usual: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
•Here, a logical OR: win[i][j] = win[i][j] OR (win[i][k] AND win[k][j])

In words: *"if i beats k and k beats j, then i beats j"* — precisely the transitive rule we wanted. Swap the distance matrix for a win (reachability) matrix, and Floyd-Warshall becomes a transitive-closure machine.

What does a "fixed" rank mean?

Once the matrix is filled, look at one player i. For each other player j, if either win[i][j] (I win) or win[j][i] (I lose) is 1, then the result against that opponent is known.

•Know the result against all N-1 others → that player's position is uniquely fixed.
•If even one opponent has both directions 0 (never met, and no transitive chain) → those two players' relative order can't be set, so it's undecided.

In the example, that's exactly P2 and P3. Both beat P4·P5 and lose to P1, yet their mutual result is unknown, so neither rank settles.

See it with your own eyes

We built the entire process as a step-by-step visualization: results filling the matrix, the via player k cycling so win[i][k] && win[k][j] flips on new results, and finally the per-player tally of "do I know my result against everyone?" — with k·i·j and the decided count visible throughout.

👉 Tournament Rank Decision — watch the step-by-step visualization

This "fill reachability instead of distance" idea shows up in countless disguises: tracing friendships, precedence (topological) checks, part compatibility, and more. Learn the principle visually once, and you can solve any variant.