Your text to link here... есть Request Clarification / Give Feedback. Можно задать вопрос)

Lack of possibility to go back is unfortunate to after you accidentally click "go to first/last page" :(

First of all forget about queue and understand that it's normal playoff tree, after that get all pairs (player, mask_of_player_of_size_2^i) so that player can win in some subtree. Then iterate over pairs of all such pairs and get answer for 2^{i+1}.

It'll give you how big subtree one can win, it gives one of places (1,2,3,5 or 9) for best. The worst place is always 1 if can win all players or "lose in first round"

It worked 3min for me, because I didn't bother to optimize

I solved with dp for every i with state: set(mask) of 2^j players, winner of this set, score distribution on this set, score of i_th player. We should merge such states and update values. My solution was a bit slow, so I needed to do parallelization.

I computed, for each set of size 2^j, the set of possible winners if only players in this set participate. To compute this, I iterated over all the ways to split it into two subsets of size 2^j - 1. Player's best place can be determined by the size of the largest set where he can still win. To find the worst place: if there is a player who beats everyone, his worst place is 1, and everyone else's worst place is n / 2 + 1. Otherwise, everyone's worst place is n / 2 + 1 (because each player could possibly lose the first match).

My approach is a little bit simpler and fast enough.

As riadwaw said, forget about the queue, is easy to see than the problem can be modeled as a game tree where each player will fight at least 1 time and upto logN times, in each tree level half players are deleted.

for each player p we can find what is the max possible number of matches he can win, this allow us to compute the maximum rank.

So the idea is canWin[p][sz] = the list of sets of having sz players (p included) where p-th player can get in the top place, sz is 2, 4, 8, 16.

canWin[p][2] = (1<<p)|(1<<q) if p can beat q for every pair (p, q), the set is represented using bitmasks.

At this point you know all possible sets of size 2 where p can win, this allows us to compute sets of size 4, a set of 4 players is divided in two sets of 2, so we can find all pairs (p, q) p beating q, and find all success outcomes for p (r, s) where r is in canWin[p][2] and s in canWin[q][2], (r, s) is good if they doesn't share any value (disjoint players), in this case p beats in his tournament of size 2, q beats in his tournament of size 2 and p beats q, so p can win one match more.

The same idea applies for tournaments of size 8 and 16.

The list of canWin[p][16] can be huge, there is a trick to optimize this, finding only one possible set where p can win is enough, this speed up my solution 10x.

An approximation for the complexity is O(log(N) * N^2 * (15C7)^2), the above trick avoids to perform worst case scenario.

My code solved the input in less than 10s, here is my code: http://ideone.com/9bkbmw

My solution was practically brute-force, it works under 10 seconds.

Idea is that with 16 participants (largest possible input) there is only:

16! / 8! / 2^8 = 2,027,025 possible pairings. So brute force all of them. Result of these pairings is at most 16! / 8! / 8! = 12,870 different answers, in most cases it will be less then that. For each of these answers you have to check only 105 potential pairing, which is even faster.

So I end up with bitmasks showing all possible passing candidates for every level of the tournament pyramid. After that I scan through that pyramid k times and calculate highest pyramid level and lowest pyramid level for each contestant.

Submission

2ⁿ * poly(n)

I guess its a rules violation and she will be kicked out.

I did something similar and it worked without problems. Did you assume that the "head" must always be the 4th element in its set (or the 1st, whatever, it's not clear to me how you're counting them) ? If yes, then this is probably the mistake.