Problem

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 ith player from the front of the row competes against the ith 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 1 competes against player 7.
  • Player 2 competes against player 6.
  • Player 4 automatically advances to the next round.

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, theearliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3
4

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 <= 28
  • 1 <= firstPlayer < secondPlayer <= n

Solution

Method 1 - DP with Memoization

We use recursion with memoization to simulate all possible ways the two players can meet, tracking the earliest and latest round.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
pair<int,int> dfs(int n, int a, int b, vector<vector<vector<pair<int,int>>>>& memo) {
    if (a > b) swap(a, b);
    if (memo[n][a][b].first != -1) return memo[n][a][b];
    if (a + 1 == n - b) return memo[n][a][b] = {1, 1};
    int minr = 100, maxr = 0;
    for (int la = 0; la <= a; ++la) {
        for (int lb = 0; lb <= n - 1 - b; ++lb) {
            int na = la + lb;
            int nb = na + (b - a - 1);
            int nn = (n + 1) / 2;
            auto [ear, lat] = dfs(nn, na, nb, memo);
            minr = min(minr, ear + 1);
            maxr = max(maxr, lat + 1);
        }
    }
    return memo[n][a][b] = {minr, maxr};
}
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    vector<vector<vector<pair<int,int>>>> memo(n+1, vector<vector<pair<int,int>>>(n, vector<pair<int,int>>(n, {-1,-1})));
    auto [ear, lat] = dfs(n, firstPlayer-1, secondPlayer-1, memo);
    return {ear, lat};
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.*;
class Solution {
    private int[][][] minMemo, maxMemo;
    public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        minMemo = new int[n+1][n][n];
        maxMemo = new int[n+1][n][n];
        for (int[][] mm : minMemo) for (int[] m : mm) Arrays.fill(m, -1);
        for (int[][] mm : maxMemo) for (int[] m : mm) Arrays.fill(m, -1);
        return dfs(n, firstPlayer-1, secondPlayer-1);
    }
    private int[] dfs(int n, int a, int b) {
        if (a > b) return dfs(n, b, a);
        if (minMemo[n][a][b] != -1) return new int[]{minMemo[n][a][b], maxMemo[n][a][b]};
        if (a + 1 == n - b) return new int[]{1, 1};
        int minr = 100, maxr = 0;
        for (int la = 0; la <= a; ++la) {
            for (int lb = 0; lb <= n - 1 - b; ++lb) {
                int na = la + lb;
                int nb = na + (b - a - 1);
                int nn = (n + 1) / 2;
                int[] res = dfs(nn, na, nb);
                minr = Math.min(minr, res[0] + 1);
                maxr = Math.max(maxr, res[1] + 1);
            }
        }
        minMemo[n][a][b] = minr;
        maxMemo[n][a][b] = maxr;
        return new int[]{minr, maxr};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from functools import lru_cache
def earliestAndLatest(n: int, firstPlayer: int, secondPlayer: int) -> [int, int]:
    @lru_cache(None)
    def dfs(n, a, b):
        if a > b: a, b = b, a
        if a + 1 == n - b:
            return 1, 1
        minr, maxr = 100, 0
        for la in range(a+1):
            for lb in range(n-b):
                na = la + lb
                nb = na + (b - a - 1)
                nn = (n + 1) // 2
                ear, lat = dfs(nn, na, nb)
                minr = min(minr, ear + 1)
                maxr = max(maxr, lat + 1)
        return minr, maxr
    return list(dfs(n, firstPlayer-1, secondPlayer-1))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::HashMap;
pub fn earliest_and_latest(n: i32, first_player: i32, second_player: i32) -> Vec<i32> {
    fn dfs(n: i32, a: i32, b: i32, memo: &mut HashMap<(i32,i32,i32), (i32,i32)>) -> (i32,i32) {
        let (a, b) = if a > b { (b, a) } else { (a, b) };
        if let Some(&res) = memo.get(&(n,a,b)) { return res; }
        if a + 1 == n - b { return (1, 1); }
        let mut minr = 100; let mut maxr = 0;
        for la in 0..=a {
            for lb in 0..=(n-1-b) {
                let na = la + lb;
                let nb = na + (b - a - 1);
                let nn = (n + 1) / 2;
                let (ear, lat) = dfs(nn, na, nb, memo);
                minr = minr.min(ear + 1);
                maxr = maxr.max(lat + 1);
            }
        }
        memo.insert((n,a,b), (minr, maxr));
        (minr, maxr)
    }
    let mut memo = HashMap::new();
    let (ear, lat) = dfs(n, first_player-1, second_player-1, &mut memo);
    vec![ear, lat]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function earliestAndLatest(n: number, firstPlayer: number, secondPlayer: number): number[] {
    const memo = new Map<string, [number, number]>();
    function dfs(n: number, a: number, b: number): [number, number] {
        if (a > b) [a, b] = [b, a];
        const key = `${n},${a},${b}`;
        if (memo.has(key)) return memo.get(key)!;
        if (a + 1 === n - b) return [1, 1];
        let minr = 100, maxr = 0;
        for (let la = 0; la <= a; ++la) {
            for (let lb = 0; lb <= n - 1 - b; ++lb) {
                const na = la + lb;
                const nb = na + (b - a - 1);
                const nn = Math.floor((n + 1) / 2);
                const [ear, lat] = dfs(nn, na, nb);
                minr = Math.min(minr, ear + 1);
                maxr = Math.max(maxr, lat + 1);
            }
        }
        memo.set(key, [minr, maxr]);
        return [minr, maxr];
    }
    return dfs(n, firstPlayer-1, secondPlayer-1);
}

Complexity

  • ⏰ Time complexity: O(n^3) (with memoization, n ≤ 28).
  • 🧺 Space complexity: O(n^3) for the memoization table.