csacademy's blog

Round #67 (Div. 1 + Div. 2) with prizes
By csacademy, 7 years ago, In English

Hello, Codeforces!

We're going to host a new contest at csacademy.com. Round #67 will take place on Wednesday, 31/January/2017 15:35 (UTC). This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

We are glad to have khadaev as a problem setter again.

Facebook event

Recently, Facebook has reintroduced the possibility of recurring events. 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 [email protected]

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 +20 Vote: I do not like it

Could you delay the round by 10-15 mins ?
It would allow people to participate in both CF #460 and CSA #67.

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

    Done, we delayed the round by 30 minutes.

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

Wow, solution to last task is really magical...

I also really liked problem E. My first thoughts were something like "oh no, this is probably yet another problem about this xor convolution with probably some divide and conquer", but then it turned out it is really cute :)

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

    Actually, my solution is sqrt-decomposition + something similar to 'this xor convolution' :)

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

      E appeared with the same approach in International Zhautykov Olympiad 2017

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

    And luckily for me, problem E can be solved with O(N·2M) complexity :-)

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

    My over-complicated solution: Divide array into blocks of size K. For a chunk update, we use dp on bits with complexity O(n+2^m*m*m) and query in O(K+m) by iterating on elements in same block. On optimally choosing k, this gives same complexity as editorial but with larger constant. Code

    → Reply