PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
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 exactly K.
An upset occurs when a player with larger index beats a player with smaller index.
EXPLANATION:
We already know how to solve for minimal K.
To recap, the solution to that is to:
- Find the largest integer p such that W + 2^{p-1} - 1 \le 2^N.
- Place W along with 2^{p-1} - 1 larger elements into one sub-tournament, and every other element arbitrarily.
- Simulate the tournament while only creating upsets involving W whenever needed to make it win.
Now, a natural idea to obtain exactly K upsets would be to start with some solution that achieves the minimum number of upsets; and then repeatedly create one upset at a time till we reach K.
(Of course, if K is smaller than the minimum number needed, no solution can exist.)
This is indeed the crux of the solution, though we need a couple of observations to get there.
First, to make life simple, let’s look at a specific construction for the minimum: we take the values
into a single sub-tournament, making that the prefix of the order.
Then we place the remaining values in increasing order to fill things out, so the final order looks like
Further, with this construction, we only created upsets in matches involving W.
Importantly, observe that the values of stuff other than W don’t quite matter.
Rather, what we’re interested in is only their value relative to W.
That is, to us, all values \lt W can be treated the same; and all values \gt W can be treated the same; since in the end, the only thing that matters is whether W faces a smaller or larger value in some given match (which determines when we need to create an upset or not).
So, suppose we take some match that involves two players that are both smaller than W.
We can then safely create an upset in this match and re-calculate the results of its ancestors appropriately while ensuring that W still faces the exact same relative sequence of values.
That is, take some index i such that A_i = \min(A_{2i}, A_{2i+1}) and either \max(A_{2i}, A_{2i+1}) \lt W or \min(A_{2i}, A_{2i+1}) \gt W, and replace A_i by \max(A_{2i}, A_{2i+1}) instead.
Doing this will require appropriately changing the values of A_j for all j of the form \displaystyle\left\lfloor \frac{i}{2^r} \right\rfloor to keep the tournament, well, a tournament.
However, these changes will not affect the relative winner of any node, which in turn means we’ve created exactly one upset!
We can thus repeatedly perform the above process over and over, till we either reach exactly K upsets or we run out of matches that can be flipped.
Let’s analyze how many upsets we can end up with this way.
First, every match involving W cannot be flipped at all.
There are exactly N such matches.
Second, every match involving elements that compare differently relative to W cannot be flipped either.
Importantly, as part of the above construction (using contiguous values), there can only be at most N such matches too!
This is because it can be proved that such a case, if it happens, occurs only in the right subtree (that doesn’t contain W).
Further, the values being contiguous means that the different relative comparison can happen only along some path from the root, which has length no more than N.
This means that there are at most 2N matches that our algorithm cannot create upsets in.
This can be further improved to 2N-1 by noting that the final is counted twice.
In any case, if m denotes the minimum of upsets possible, our algorithm achieves every possible K in [m, 2^N - 2N].
Observe that this is a really huge range, since 2N is really small compared to 2^N.
However, it’s still not quite everything: there are certainly situations where we might need to create more than 2^N - 2N upsets.
To fix the above issue, we can simply invert what we’re doing!
That is, rather than start with the minimum number of upsets, start with the maximum number, and then “un-upset” matches one-by-one (again, this can only be done with matches that compare the same relative to W).
Obtaining a construction with the maximum number of upsets can be done similarly to how the minimum was obtained; just that this time, we look for the largest p such that 2^p \le W instead.
Similar reasoning as above shows that if the maximum number of upsets is M, then all counts in [2N-1, M] are achievable.
Now, clearly we can only achieve upsets that are in the range [m, M].
We have the two ranges [m, 2^N - 2N] and [2N-1, M] that we can achieve.
Because 2N is so small compared to 2^N, these two ranges will almost always overlap - in general, it can be seen that for N \ge 4, these two ranges will cover all of [m, M] together, so we have a construction for all possible values of K.
For N \le 3, it turns out that the algorithm still works.
This is because, for N = 1 and N = 2, we have M - m \le 1 for any W, which means any winner must attain either the minimum or the maximum possible number of upsets it can; since we check both, we find an answer.
For N = 3, it works out because 2N-1 was a fairly loose bound, and in general there will be less than 2N-1 “forbidden” matches.
(It’s possible to write out a formal proof, but it’s much simpler to just run the code and see that it works, which is proof enough. Alternately, since N \le 3 is small enough, you can just bruteforce all tournaments.)
So, we have a two-phase algorithm:
- Let m be the minimum number of upsets possible, and M be the maximum possible.
If K \not\in [m, M], no solution exists. - Otherwise, try two things:
1. Start with m upsets and repeatedly create one upset at a time involving players who compare similarly relative to W. Repeat this as long as possible.
2. Start with M upsets and repeatedly remove one upset at a time, again involving players who compare similarly relative to W. Repeat this as long as possible. - It can be shown that as long as K \in [m, M], one of the above two approaches will work.
Each new upset we create takes \mathcal{O}(N) time, since all its ancestors need to be updated appropriately.
So, the overall runtime is \mathcal{O}(2^N N), which is more than fast enough for N \le 17.
It’s also possible to implement this to run in \mathcal{O}(2^N), which wasn’t needed to obtain AC.
TIME COMPLEXITY:
\mathcal{O}(2^N N) per testcase.
CODE:
Editorialist's code (PyPy3)
def go_min(n, w):
N = 2**n
order = []
for pw in range(n+10):
if 2**pw <= N - w + 1: continue
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
upsets = 0
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])
if ans[i] == max(ans[2*i], ans[2*i+1]): upsets += 1
return upsets, ans
def go_max(n, w):
N = 2**n
order = []
for pw in range(n+10):
if 2**pw <= w: continue
L, R = w - 2**(pw-1) + 1, w
order = list(range(L, R+1)) + list(range(1, L)) + list(range(R+1, N+1))
break
ans = [0]*(N) + order
upsets = 0
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] = max(ans[2*i], ans[2*i+1])
if ans[i] == max(ans[2*i], ans[2*i+1]): upsets += 1
return upsets, ans
def solve(n, k, w):
# try with min
upsets, ans = go_min(n, w)
if upsets > k: return []
for i in reversed(range(1, 2**n)):
if ans[i] == w: continue
if upsets == k: continue
if (ans[2*i] < w and ans[2*i+1] < w) or (ans[2*i] > w and ans[2*i+1] > w):
upsets += 1
ans[i] = max(ans[2*i], ans[2*i+1])
node = i//2
while node >= 1:
if ans[2*node] == w or ans[2*node+1] == w: ans[node] = w
else: ans[node] = min(ans[2*node], ans[2*node+1])
node //= 2
if upsets == k: return ans
# try with max
upsets, ans = go_max(n, w)
if upsets < k: return []
for i in reversed(range(1, 2**n)):
if ans[i] == w: continue
if upsets == k: continue
if (ans[2*i] < w and ans[2*i+1] < w) or (ans[2*i] > w and ans[2*i+1] > w):
upsets -= 1
ans[i] = min(ans[2*i], ans[2*i+1])
node = i//2
while node >= 1:
if ans[2*node] == w or ans[2*node+1] == w: ans[node] = w
else: ans[node] = max(ans[2*node], ans[2*node+1])
node //= 2
if upsets == k: return ans
return []
for _ in range(int(input())):
n, k, w = map(int, input().split())
ans = solve(n, k, w)
if len(ans) == 0: print(-1)
else: print(*ans[1:])