csacademy's blog

By csacademy, history, 4 weeks ago, In English,

Hello, Codeforces!

We're glad to have koosaga as a problem setter!

We're going to host a new contest at csacademy.com. Round #84 will take place on Wednesday, July 18th, 15:05:00 UTC. This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

Facebook event

We recently created a new Facebook event. If you choose "Interested" here, you will be notified before each round we organise from now on.

Contest format:

  • You will have to solve 7 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.

Prizes

We're going to award the following prizes:

  1. First place: 100$
  2. Second place: 50$

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.

If you find any bugs please email us at contact@csacademy.com

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

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

»
4 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it

Oh my god... it is Koosaga round??????

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    I got a pretty overkill-ish solution.

    Let's iterate over each x from the input and check the answer in point (x, 0). You can show that the minimal answer will always be in some of them.

    Sort points by x.

    Maintain a set of values L points to the left (or equal to x) of the current x add. They add to the answer. Points to the right of x will be stored in some structure that can remove elements and get the sum of the k minimal ones by comparator (x + y) (because the answer for that structure is the sum of these values minus (k - |L|)·x) (I did it with compressing these values and having a segment tree with 1s and 0s and BIT for sums). Now when transitioning to the next x, you remove the corresponding points from the structure and add them to set. Now you remove points from the set (by the greatest value) until its size is k or smaller. Finally, you remove the greatest values from the set if it's making the answer smaller (check for the current answer and for the answer withoit the greatest element of L and with k - |L| + 1 elements from the structure).

    You can just erase from |L| because these points will never be needed anyway.

    Code

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So... did anyone else solve E and then realized the same solution applies to D in O(nlog^2n) with fenwick + binary search?

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Editorial is finally live. Sorry for being very late!

Growing Trees
The Sprawl
Baby Seokhwan

Huge thanks to CSA team for their amazing platform and helps, and tester khsoo01!