KNOCKOUT - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given the skill levels of 16 players in a knockout tournament, all of which are distinct. This is represented by an array S.
A person with higher skill always wins over one with lower skill.
If paired optimally, find the number of matches the i-th player can win.

EXPLANATION:

Let’s look at the i-th player and see what we need to make them win.

  • To win even a single match, there should be a player with lower skill level than S_i.
  • To win two matches, there should be (at least) three people with lower skill level than S_i.
    • This is because there are two people who are directly beaten, and also one person who is indirectly beaten: the opponent of person i in round two must win their round 1 match, which requires being paired against someone with smaller skill level than themself (and hence, smaller than S_i too.)
  • To win three matches, by the same logic, there should be (at least) 7 players with lower skill level than S_i.
    Three of these seven players will be defeated directly, the other 4 will be defeated indirectly by the opponents of player i.
  • To win four matches, there must be 15 players with smaller skill level than S_i.

Winning more than four matches is impossible with only 16 players, so this is all the checks that are needed.
So, all that needs to be done is, for every index, to count the number of people whose skill level is smaller than S_i; and casework on that appropriately.
That can be done by either sorting the array, or simply brute-force iterating over the array since its length is small.

TIME COMPLEXITY:

\mathcal{O}(N\log N) or \mathcal{O}(N^2) per testcase, where N = 16.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    s = list(map(int, input().split()))
    indices = list(range(16))
    indices.sort(key = lambda x: s[x])
    ans = [0]*16
    
    nxt, cur = 1, 0
    for i in range(1, 17):
        ans[indices[i-1]] = cur
        if i == nxt:
            cur += 1
            nxt = 2*nxt + 1
    print(*ans)