Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1900.html
1900. The Earliest and Latest Rounds Where Players Compete
Level
Hard
Description
There is a tournament where n players are participating. The players are standing in a single row and are numbered from 1 to n based on their initial standing position (player 1 is the first player in the row, player 2 is the second player in the row, etc.).
The tournament consists of multiple rounds (starting from round number 1). In each round, the i-th player from the front of the row competes against the i-th player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.
- For example, if the row consists of players
1, 2, 4, 6, 7- Player
1competes against player7. - Player
2competes against player6. - Player
4automatically advances to the next round.
- Player
After each round is over, the winners are lined back up in the row based on the original ordering assigned to them initially (ascending order).
The players numbered firstPlayer and secondPlayer are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may choose the outcome of this round.
Given the integers n, firstPlayer, and secondPlayer, return an integer array containing two values, the earliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.
Example 1:
Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation:
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4
Example 2:
Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: The players numbered 1 and 5 compete in the first round. There is no way to make them compete in any other round.
Constraints:
2 <= n <= 281 <= firstPlayer < secondPlayer <= n
Solution
Use breadth first search and backtrack. Initially, there are n players, and the numbers of firstPlayer and secondPlayer are given. Each time, use backtrack to obtain all possible results after the current round, where each pair of competitors have two results, except the firstPlayer and the secondPlayer always win, and the player in the middle automatically advanced to the next round. For each of the next states, update n, firstPlayer and secondPlayer accordingly.
When a state such that firstPlayer and secondPlayer compete against each other, calculate the number of rows, and maintain the minimum and the maximum number of rows. Finally, return the array containing the two numbers.
-
class Solution { Set<String> set = new HashSet<String>(); public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) { firstPlayer--; secondPlayer--; Queue<int[]> queue = new LinkedList<int[]>(); queue.offer(new int[]{n, firstPlayer, secondPlayer}); int steps = 0; int minSteps = Integer.MAX_VALUE, maxSteps = Integer.MIN_VALUE; while (!queue.isEmpty()) { steps++; int size = queue.size(); for (int i = 0; i < size; i++) { int[] state = queue.poll(); int curN = state[0], curFirst = state[1], curSecond = state[2]; if (curFirst + curSecond == curN - 1) { minSteps = Math.min(minSteps, steps); maxSteps = Math.max(maxSteps, steps); } else if (curN > 2) { List<int[]> nextStates = getNextStates(state); for (int[] nextState : nextStates) { String stateStr = Arrays.toString(nextState); if (set.add(stateStr)) queue.offer(nextState); } } } } return new int[]{minSteps, maxSteps}; } public List<int[]> getNextStates(int[] state) { List<int[]> nextStates = new ArrayList<int[]>(); int n = state[0], firstPlayer = state[1], secondPlayer = state[2]; int[] nextState = new int[n]; nextState[firstPlayer] = 2; nextState[secondPlayer] = 2; if (n - 1 - firstPlayer != firstPlayer) nextState[n - 1 - firstPlayer] = -2; if (n - 1 - secondPlayer != secondPlayer) nextState[n - 1 - secondPlayer] = -2; if (n % 2 == 1 && nextState[n / 2] == 0) nextState[n / 2] = 1; backtrack(nextStates, nextState, 0); return nextStates; } public void backtrack(List<int[]> nextStates, int[] nextState, int index) { int n = nextState.length; if (index == n / 2) { int[] newState = new int[3]; int nextN = (n + 1) / 2; newState[0] = nextN; int stateIndex = 1, playerIndex = 0; for (int i = 0; i < n; i++) { if (nextState[i] == 2) newState[stateIndex++] = playerIndex; if (nextState[i] > 0) playerIndex++; } nextStates.add(newState); } else { if (nextState[index] == 0) { nextState[index] = 1; nextState[n - 1 - index] = -1; backtrack(nextStates, nextState, index + 1); nextState[index] = -1; nextState[n - 1 - index] = 1; backtrack(nextStates, nextState, index + 1); nextState[index] = 0; nextState[n - 1 - index] = 0; } else backtrack(nextStates, nextState, index + 1); } } } -
class Solution: def earliestAndLatest( self, n: int, firstPlayer: int, secondPlayer: int ) -> List[int]: # dp[i][j][k] := (earliest, latest) pair w/ firstPlayer is i-th player from # Front, secondPlayer is j-th player from end, and there're k people @functools.lru_cache(None) def dp(l: int, r: int, k: int) -> List[int]: if l == r: return [1, 1] if l > r: return dp(r, l, k) a = math.inf b = -math.inf # Enumerate all possible positions for i in range(1, l + 1): for j in range(l - i + 1, r - i + 1): if not l + r - k // 2 <= i + j <= (k + 1) // 2: continue x, y = dp(i, j, (k + 1) // 2) a = min(a, x + 1) b = max(b, y + 1) return [a, b] return dp(firstPlayer, n - secondPlayer + 1, n)