PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given N and W, construct a single-elimination tournament with 2^N players numbered 1 to 2^N such that the winner is W, and the number of upsets is minimized.
An upset occurs when a player with larger index beats a player with smaller index.
EXPLANATION:
First, we need to figure out what the minimum number of upsets can possibly be, if W is to be the winner.
One simple case is when W = 1.
Here, no upsets are needed at all - as long as the person with smaller label wins every time, the winner is guaranteed to be 1.
For W \gt 1, it’s obvious that at least one upset is needed: if the winner is not 1, then clearly somebody has to beat 1; and that’s definitely an upset.
Let’s now try to figure out when exactly one upset will suffice.
Intuitively, this should be the case for “small enough” W, since the larger W is, the more likely it is that W will need to upset smaller values.
Now, observe that the tournament essentially splits into two halves before the final, and the two halves are independent of each other.
One of these halves will contain W; without loss of generality let this be the left half.
Note for to win the left half without any upsets happening, W must be the smallest element in this half.
So, we have two possibilities:
- W can win its half without an upset.
Note that this is only possible when there are at least 2^{N-1}-1 labels larger than W available to us.
That is, W + 2^{N-1} - 1 \le 2^N must hold; which translates to W \le 2^{N-1} + 1.
Here, it can be seen that one upset is enough to make W win: a simple construction is to place W with 2^{N-1}-1 larger elements in one half and all the other elements in the other half, and just run the tournament normally without upsets; at which point the finals will be between 1 and W, and W can upset 1 to win. - W cannot win its half without an upset.
This means W \gt 2^{N-1} + 1 holds.
In this case, it can be proved that W cannot win with only one upset.
This is because, if there’s only one upset (and that upset is in the half containing W), that would mean the half not containing W has no upsets - which in turn makes its winner the smallest element in this half.
Further, the final also cannot have an upset; which is only possible if the winner of the other half is larger than W.
Together, this means there must be at least 2^{N-1} elements strictly larger than W, which we already know is impossible because W \gt 2^{N-1} + 1.
Thus, if 1 \lt W \le 2^{N-1} + 1, one upset suffices.
Next, we need to think about when two upsets will suffice.
Following similar reasoning as above, it can be seen that two upsets will work only when W can win one quarter of the tournament without any upsets (where for answer = 1, W had to be able to win one half of the tournament).
That is, there must be are at least 2^{N-2}-1 other elements larger than W available.
This translates to W \le 1 + 2^{N-1} + 2^{N-2}.
If W satisfies this condition, once again the construction of a tournament with 2 upsets is quite easy: take W along with 2^{N-2}-1 other larger elements into one quarter of the tournament, and then just place all the other elements however you want.
Then, simply simulate the tournament naturally, except you force W to win any of its matches even if they’re upsets.
Since W is able to win its quarter, there will only be two upsets this way: the semi-finals and the finals.
It’s now not hard to see that the above idea can be extended to obtain a more general solution.
That is, let p be the largest integer such that W + 2^p - 1 \le 2^N.
That is, p is the largest integer such that W can win a tournament consisting of 2^p people among [1, 2^N].
Then, the minimum number of upsets needed is (N - p), and the construction for this is to just take W along with some (2^p - 1) larger elements into a single bracket, arrange everyone else however you like (for simplicity, ascending order), and then simulate the tournament normally except with forced wins for W.
This can easily be implemented in \mathcal{O}(2^N) time.
TIME COMPLEXITY:
\mathcal{O}(2^N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, w = map(int, input().split())
N = 2**n
order = []
for pw in range(n+10):
if 2**pw <= N - w + 1: continue
# 2^(pw-1) is largest valid power
# take w and next 2^(pw-1) - 1 elements first, then everything else
L, R = w, w + (2**(pw-1)) - 1
order = list(range(L, R+1)) + list(range(1, L)) + list(range(R+1, N+1))
break
ans = [0]*(N) + order
# simulate tournament without upsets, but force wins for w
for i in reversed(range(1, N+1)):
if ans[i] == 0:
if ans[2*i] == w or ans[2*i+1] == w: ans[i] = w
else: ans[i] = min(ans[2*i], ans[2*i+1])
print(*ans[1:])