csacademy's blog

Round #81 (Div. 2)
By csacademy, history, 7 years ago, In English

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.

About the penalty system:

  • 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.

Don't forget to like us on Facebook, VK and follow us on Twitter.

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The contest starts in less than an hour!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the problem D "Gerrymandering" I dont completely understand the editorial! , Thanks!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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_next

    More 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^2

    Now, 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 majority

    Another 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 map

    It can be done with unordered_map as well, with some more coding.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the editorialist's solution for D ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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..

    → Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

No announcement for round #82 yet csacademy ?

→ Reply