[C/C++] BOJ #1057 - Tournament

A tournament match is a competition where two teams or players face off, and the winner advances to the next round. It fundamentally follows a binary tree structure.

---

Problem Description

The problem is to determine when two players, A and B, will meet in a tournament, assuming players are lined up from 1 to N in order. Once you recognize that this is essentially a binary tree, the problem becomes quite straightforward.

Although this is classified as a Silver II level problem, it’s arguably simpler than that.

Let’s say there’s a tournament bracket as shown in a diagram, with players numbered from 1 to 8 from left to right. Suppose South Korea is player 5, and we want to know when they might face Canada, who is player 2. In this case, the match can only happen in the finals.

tounament

Now, if it’s South Korea vs. Australia instead (with Australia being player 8), they could potentially meet in the semifinals.

---

Core Idea

While this might seem similar to finding a Lowest Common Ancestor (LCA) in a tree, it’s actually much simpler. For LCA problems, you generally need to traverse the tree, but because this tournament follows a strict binary tree structure, you can determine node positions directly without traversal.

---

Algorithm Insight

You can find when two players meet by removing the least significant bits (LSBs) of their binary representations until the values match—indicating they’ll meet in that round.

However, since tournament brackets often start from index 0 (in binary logic), subtract 1 from each player number to align them correctly.

For example:
• South Korea (5) and Canada (2) become 4 and 1 (0-indexed).
• Binary: 100 and 001. No common bits until the highest level → finals.
• South Korea (5) and Australia (8) become 4 and 7.
• Binary: 100 and 111. They match at a higher level sooner → semifinals.

 

//----------------------------------------------------------
//    baekjoon #1057 - Tournament
//        - by Aubrey Choi
//        - created at 2019-07-03
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, a, b, c = 0;
    scanf("%d%d%d", &n, &a, &b);
    for(a--,b--;a != b;a>>=1,b>>=1,c++);
    printf("%d\n", c);
}

FIFA World Cup Tournament