Problem Description

The "Output Contest Matches" problem asks you to simulate the pairing of teams in a single-elimination tournament. Given an integer n (where n is a power of two), you must output a string representing the contest matches in the following recursive format:

• In the first round, the strongest team (1) is paired with the weakest (n), the second strongest (2) with the second weakest (n-1), and so on.
• Each subsequent round, the winners are paired in the same way, until only one match remains.
• The output should be a single string, where each pair is represented as (A,B), and pairs are recursively nested to reflect the pairing process.

Constraints:

• There is only one valid solution for a given n.
• Each team number from 1 to n must be used exactly once and not reused.

Input: n = 4
Output: "((1,4),(2,3))"
    

Thought Process

At first glance, this problem might seem to require simulating the entire tournament, keeping track of which teams win and how pairs are formed at each round. However, since the problem only asks for the pairing structure (not the actual winners), we can focus on how to recursively build the string representation of the contest matches.

A brute-force approach would be to generate all possible pairings and manually simulate each round, but this is unnecessary because the pairings are deterministic based on the input n. Recognizing that the pairing at each round always matches the outermost teams (first with last, second with second-to-last, etc.) allows us to optimize the process.

The key realization is that this is a recursive string-building problem: at each round, we can pair up the current list of teams, then treat each pair as a new "team" for the next round, and repeat until only one match remains.

Solution Approach

We can solve this problem using a simple iterative or recursive approach:

1. Initialization: Start by creating a list of strings, each representing a team number from 1 to n.
2. Pairing: While there is more than one team in the list:
   • Pair the first team with the last, the second with the second-to-last, and so on.
   • For each pair, create a new string in the format (A,B) and add it to a new list.
   • Replace the original list with this new list of pairs.
3. Termination: When only one string remains, that is the final contest match representation.

This process can be implemented either recursively or iteratively. The iterative approach is often easier to follow for beginners, as it simply loops until the list is reduced to one element.

We use a list (or array) to store the current round's matches, because lists provide fast access and modification, and the pairing operation is straightforward.

Example Walkthrough

Let's walk through the process with n = 8:

1. Initial teams: ["1", "2", "3", "4", "5", "6", "7", "8"]
2. First round pairs:
   • Pair 1 and 8: (1,8)
   • Pair 2 and 7: (2,7)
   • Pair 3 and 6: (3,6)
   • Pair 4 and 5: (4,5)
   New list: ["(1,8)", "(2,7)", "(3,6)", "(4,5)"]
3. Second round pairs:
   • Pair (1,8) and (4,5): ((1,8),(4,5))
   • Pair (2,7) and (3,6): ((2,7),(3,6))
   New list: ["((1,8),(4,5))", "((2,7),(3,6))"]
4. Final round pair:
   • Pair ((1,8),(4,5)) and ((2,7),(3,6)): (((1,8),(4,5)),((2,7),(3,6)))
   Final result: "(((1,8),(4,5)),((2,7),(3,6)))"

At each step, we pair the current matches from the outermost inward, and build up the string recursively.

Code Implementation

class Solution:
    def findContestMatch(self, n: int) -> str:
        teams = [str(i) for i in range(1, n+1)]
        while len(teams) > 1:
            new_round = []
            for i in range(len(teams)//2):
                pair = f"({teams[i]},{teams[-1-i]})"
                new_round.append(pair)
            teams = new_round
        return teams[0]
      

class Solution {
public:
    string findContestMatch(int n) {
        vector<string> teams;
        for (int i = 1; i <= n; ++i) {
            teams.push_back(to_string(i));
        }
        while (teams.size() > 1) {
            vector<string> next;
            int sz = teams.size();
            for (int i = 0; i < sz / 2; ++i) {
                next.push_back("(" + teams[i] + "," + teams[sz - 1 - i] + ")");
            }
            teams = next;
        }
        return teams[0];
    }
};
      

class Solution {
    public String findContestMatch(int n) {
        List<String> teams = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            teams.add(Integer.toString(i));
        }
        while (teams.size() > 1) {
            List<String> next = new ArrayList<>();
            int sz = teams.size();
            for (int i = 0; i < sz / 2; i++) {
                next.add("(" + teams.get(i) + "," + teams.get(sz - 1 - i) + ")");
            }
            teams = next;
        }
        return teams.get(0);
    }
}
      

var findContestMatch = function(n) {
    let teams = [];
    for (let i = 1; i <= n; i++) {
        teams.push(i.toString());
    }
    while (teams.length > 1) {
        let next = [];
        let sz = teams.length;
        for (let i = 0; i < sz / 2; i++) {
            next.push("(" + teams[i] + "," + teams[sz - 1 - i] + ")");
        }
        teams = next;
    }
    return teams[0];
};
      

Time and Space Complexity

Brute-force approach: If we tried to simulate every possible pairing, the time and space would be exponential, but that's unnecessary due to the deterministic structure.

Optimized approach:

• Time Complexity: At each round, we process all current teams by pairing them up. Since the number of rounds is log₂n and the total number of pairings across all rounds is O(n), the overall time complexity is O(n) (not counting string concatenation costs).
• Space Complexity: We store intermediate strings for each round. The total space used is O(n) for the list, but the final string's length is also O(n log n) due to nested parentheses.

The solution is efficient because it never generates unnecessary pairings or simulates outcomes—it simply builds the required string representation.

Summary

The "Output Contest Matches" problem can be solved elegantly by recognizing its recursive pairing structure. Instead of simulating matches, we iteratively or recursively pair teams from the outside in, building up the tournament match string round by round. This approach leverages the deterministic nature of the pairings and avoids unnecessary computation, resulting in a clean and efficient solution.