Tennis Contest

Find the names of players defeated by the tournament winner, from final round back to first round

Understand the Problem

Problem Statement

A Tennis contest was scheduled in a college. N number of players registered to participate in this contest. (A player is the winner if he wins in all the rounds of the contest. Every round has elimination. Thus, one-half of the players are eliminated in each round. For example, If P number of players were in a specific round, then P/2 players win and move to the next round). The number of players N and the players details (ID and Name) are given as input. The program should print the names of the players who were defeated by the winner of the contest from final round to the first round.

Note : Total number of players N will always be a power of 2 and N >= 2.

Constraints

Number of players N is always a power of 2 and N >= 2
Player IDs are positive integers
Player names contain only alphabetic characters
Match results are provided in format "WinnerIDvsRunnerID"
Total matches = N - 1
Input contains exactly N player entries followed by N-1 match results

Examples

Example 1

Input

4
101 Ram
102 Sri
103 Sheik
104 Vel
101vs102
103vs104
101vs103

Output

Sheik
Sri

Explanation

Ram (101) wins the tournament. The final match was 101vs103, so Sheik was defeated in the final. Working backwards, Ram defeated Sri (102) in the first round. Therefore, the players defeated by the winner from final to first round are Sheik and Sri.

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Declare variables
    int n, i, j, k, l = 0, m, b[100], c[100], d[100];
    char a[100][10];

    // Read the number of teams as input
    scanf("%d", &n);

    // Read team numbers and names and store them in arrays b and a
    for (i = 0; i < n; i++) {
        scanf("%d%s", &b[i], a[i]);
    }

    // Read the matches and store the first and second teams in arrays c and d
    for (i = 0; i < n - 1; i++) {
        scanf("%dvs%d", &c[i], &d[i]);
    }

    // Find the winner of the final match (c[n-2]) and print their name
    for (i = n - 2; i >= 0; i--) {
        if (c[i] == c[n - 2]) {
            l = d[i];
            for (j = 0; j < n; j++) {
                if (l == b[j]) {
                    printf("%s\n", a[j]);
                    break;
                }
            }
        }
    }

    return 0;
}

Time:O(N²) - We have nested loops: outer loop runs N times, inner loop runs up to N times for name lookup

Space:O(N) - We store N player records and N-1 match results

Approach:

Step-by-step explanation:

Input Reading: Read N (number of players), then N lines of player data (ID and name), then N-1 match results
Data Storage: Store player IDs in array b and names in 2D array a. Store match winners in array c and losers in array d
Trace Winner's Path: Start from the final match (index n-2) and work backwards to find all opponents defeated by the tournament winner
Output Results: For each defeated opponent, look up their name and print it

Key Logic: The winner of the final match is the tournament champion. By scanning backwards through match results, we find all matches where this player was the winner, which gives us their path through the tournament.

Visual Explanation

Loading diagram...

All Problems