Approach #1: Simulation [Accepted]
Intuition
Let team[i]
be the correct team string of the i
th strongest team for that round. We will maintain these correctly as the rounds progress.
Algorithm
In each round, the i
th team becomes "(" + team[i] + "," + team[n1i] + ")"
, and then there are half as many teams.
Complexity Analysis

Time Complexity: . Each of rounds performs work.

Space Complexity: .
Approach #2: Linear Write [Accepted]
Intuition
Let's try to solve the problem in linear time. We can treat this problem as two separate problems: outputting the correct sequence of parentheses and commas, and outputting the correct team number. With a little effort, one can be convinced that a linear time solution probably exists.
Algorithm
Let's focus on the parentheses first. We can use recursion to find the answer. For example, when N = 8
, let R = log_2(N) = 3
be the number of rounds. The parentheses and commas look like this:
(((x,x),(x,x)),((x,x),(x,x)))
But this is just recursively
"(" + (sequence for R = 2) + "," + (sequence for R = 2) + ")" = "(" + "((x,x),(x,x))" + "," + "((x,x),(x,x))" + ")"
Now let's look at the team numbers. For N = 16
, the team numbers are:
team = [1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11]
One thing we might notice is that adjacent numbers sum to 17
. More specifically, indices that are 0 and 1 (mod 2) sum to 17
. Also, indices 0 and 2 (mod 4) sum to 9
, indices 0 and 4 (mod 8) sum to 5
, and so on.
The pattern in general is: indices 0
and 2**r
(mod 2**(r+1)
) sum to N * 2**r + 1
.
If we want to find the next team[i]
, then the lowest bit of i
will help determine it's lower neighbor. For example, team[12] = team[0b1100]
has lower bit w = 4 = 0b100
, so 12
has lower neighbor 12  w = 8
, and also those team numbers sum to N / w + 1
.
Complexity Analysis

Time Complexity: . We print each of characters in order.

Space Complexity: .
Analysis written by: @awice.