Find the earliest and latest possible rounds in which two designated players can meet in a knockout tournament with arbitrary outcomes for other matches.
Problem
In a single-elimination tournament, the players are numbered from 1 to n in the initial order. In each round, the players are paired from the outside inward: the first with the last, the second with the second last, and so on. If the number of remaining players is odd, the middle player advances automatically.
For every match, either player may win, except that the two designated players must both continue winning until they eventually face each other. Your task is to determine the earliest round and the latest round in which these two players can compete against each other, assuming all other match results can be chosen arbitrarily.
Return both values as a pair [earliest, latest].
Notes
- The initial positions of the two players are fixed.
- The ordering of survivors for the next round follows the same left-to-right order as the original bracket after removing eliminated players.
- You may choose outcomes of non-target matches to minimize or maximize the meeting round.
Input Format
The input is described by three integers:
n: the total number of playersfirstPlayer: the label of one designated playersecondPlayer: the label of the other designated player
The players are initially arranged as 1, 2, ..., n.
Output Format
Return two integers [earliest, latest] representing the minimum and maximum possible round numbers in which the two designated players can meet.
Constraints
2 <= n <= 281 <= firstPlayer < secondPlayer <= n- The tournament is single-elimination
- The bracket pairing rule is fixed each round
Example 1
Input
n = 11, firstPlayer = 2, secondPlayer = 4
Output
[3,4]
Explanation
Depending on the outcomes of other matches, the two players can meet as early as round 3 or as late as round 4.
Example 2
Input
n = 5, firstPlayer = 1, secondPlayer = 5
Output
[1,1]
Explanation
They are paired against each other immediately in the first round.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.