Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By csacademy, history, 6 months ago, ,

Hello, Codeforces!

We are going to host a new contest at csacademy.com. Round #81 will take place on Wednesday, June/06/2018 15:05 (UTC). This round will be a Div. 2, affecting users with a rating below 1800.

#### Contest format:

• You will have to solve 5 tasks in 2 hours.
• There will be full feedback throughout the entire contest.
• Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
• Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
• Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

• Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
• Solutions that don't compile or don't pass the example test cases are ignored.
• Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

•
• +41
•

 » 6 months ago, # |   +8 The contest starts in less than an hour!
•  » » 6 months ago, # ^ |   +10 The contest is starting in 10 minutes :D
 » 6 months ago, # |   0 Can someone explain the problem D "Gerrymandering" I dont completely understand the editorial! , Thanks!
•  » » 6 months ago, # ^ |   +6 My idea was a bit different than the one in the editorial, but here's the general outline. Consider the following DP: DP[big_city][num_taken] = max_number_for_nextMore informally, what's the biggest number of voters that can come from 'big_city + 1's left border if we selected the right-boundary for 'big_city' and up to this point party A has majority in 'num_taken' districts?At first, the recursion for this DP will seem like an N^3 (select big_city, select the right_boundary, select how many you were taken at last step)But it's not like that! First, for the 'select the right_boundary' part, this will be done N times overall, so it doesn't count (it's not O(N) for every iteration)So the DP is N^2Now, you can prove with a greedy algorithm that you only need to consider the best 2 values for for how many districts does party A has a majorityAnother way to see the DP is the following:DP[big_city][0/1] = pair(num_cities with A majority, best numbers of voters for city 'big_city + 1') and 0/1 means that party A has a majority or not over city 'big_city'The first implementation can be found here https://csacademy.com/submission/1605207/I used a map because it's convenient to code, nothing else. At first the complexity may seem wrong, but in fact it's ok. It's O(NlogN) from mapIt can be done with unordered_map as well, with some more coding.
•  » » » 6 months ago, # ^ |   0 Thanks a lot! , the code is very clear and finally get the solution! I was having some troubles with the english written in the editorial! Thanks for CSAcademy and publishing analysis fast!
 » 6 months ago, # |   0 Can anyone explain the editorialist's solution for D ?
•  » » 6 months ago, # ^ |   0 It is kind of the same as alex.velea solution above only differing sort of in how they are interpreting the implementation , in case you dont understand it , I highly recommend you to read the submission above by alex..
•  » » » 6 months ago, # ^ |   0 Okay, I'll try it. Thanks.
 » 6 months ago, # |   +6 No announcement for round #82 yet csacademy ?
•  » » 6 months ago, # ^ |   +1 I was about to make it :( I always forget.