Round 1 starts in 10 hours

Note, that rules were changed:

To advance to Round 2 you need to score 30 points or more.

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 176 |

6 | maroonrk | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 00:37:10 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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)

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

How do you code D fast? I had a solution but it took me hours to code it.

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

iwith state: set(mask) of 2^{j}players, winner of this set, score distribution on this set, score ofi_{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 isn/ 2 + 1. Otherwise, everyone's worst place isn/ 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

^{n}*poly(n)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?

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

I find it a bit disappointing that the score distribution did not satisfy the constraints described in Problem A :(

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

`

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.

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?

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)

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)

I was creating my test cases in the following way:

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:

And my tests didn't catch it because I didn't see a problem in my program producing result smaller then expected...