By riadwaw, history, 5 years ago, translation,

Round 1 starts in 10 hours

Note, that rules were changed:
To advance to Round 2 you need to score 30 points or more.

• +98

 » 5 years ago, # | ← Rev. 2 →   +16 Is it possible to go to arbitrary place in standings? Wanna solve problems like "find number of participants who got more than x points" faster than in O(answer)
•  » » 5 years ago, # ^ |   0 Lack of possibility to go back is unfortunate to after you accidentally click "go to first/last page" :(
 » 5 years ago, # |   +3 How do you code D fast? I had a solution but it took me hours to code it.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +3 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
•  » » 5 years ago, # ^ |   +11 I solved with dp for every i with state: set(mask) of 2j players, winner of this set, score distribution on this set, score of ith player. We should merge such states and update values. My solution was a bit slow, so I needed to do parallelization.
•  » » 5 years ago, # ^ |   +23 I computed, for each set of size 2j, 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 2j - 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).
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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<
•  » » 5 years ago, # ^ |   0 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
•  » » 5 years ago, # ^ |   0 2n * poly(n)
 » 5 years ago, # |   +27 I've just watched last-competitor-with-100-points's (she's called "Tanya") submissions. All of her submissions have the same code not related to any of the problems...Here comes the question: what for are the source submissions then?
•  » » 5 years ago, # ^ |   +8 I guess its a rules violation and she will be kicked out.
 » 5 years ago, # |   +21 I find it a bit disappointing that the score distribution did not satisfy the constraints described in Problem A :(
 » 5 years ago, # | ← Rev. 2 →   0 Feeling awkward having failed only Problem A. What can possible go wrong there? I solved it (almost) using DP (maybe an overkill but I wanted to be sure). Idea is going backward from the end for every item check if it can be start of 1, 2, 3, 4 sequence. Each time take minimal amount of 4 options. Number for head is the answer. Sumbission`
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Yes, I assumed that it is always first. Still not sure why is it a mistake? Do you mean that I'm missing some opportunity to insert more elements before the first element?
•  » » » » 5 years ago, # ^ |   0 muguerlionut, thank for pointing me in right direction.I found my mistake — I don't really make any checks between quadruples of numbers, so based on problem description they also must be different by no more that 10. Studip mistake. Funny part of it is that thousands random test I used to check and recheck my solution also did not take this into account :). At least I have another chance in Round 2 (and would still have it even if they didn't change rules)
•  » » » » » 5 years ago, # ^ |   0 Do you mean "b — a ≤ 10, c — b ≤ 10, d — c ≤ 10" this one? If so, how could you skip that if its checked in the sample tests? (15 20 25 40)
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I was creating my test cases in the following way: Create quadruples of numbers in accordance with the rules (b-a <= 10 as well). Put them together. Remove x random items from the list. Correct answers is most likely x or sometimes less then x.Condition I didn't enforce in my tests — and the reason for failure — is that while going from one quadruple of numbers to another there should be no difference of more then 10.UPDATE — Very wrong logic above. My only mistake was putting '=' instead of '+=' in the following line: needtoadd = (diff - 1) / 10; And my tests didn't catch it because I didn't see a problem in my program producing result smaller then expected...