csacademy's blog

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

Happy New Year, Codeforces!

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

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

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

Remainder, contest starts soon.!!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +27 Vote: I do not like it

    You know you have been studying too much math when you write remainder instead of reminder

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

How to solve problem D ?

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

    Let DP[i] denote the number of ways to create good arrays using the suffix [i, n]. The answer is DP[1].

    Iterate from right to left. When you are at i, find the max index j such that i <= j <= n and you can place the first zero to the right of i (inclusive) at j. j is invalid if there exists some interval [l, r] such that l>=i && r<j. You can find j using binary search.

    Then add DP[x+1] to DP[i], for i <= x <= j. Also, check the case when there is no zero to the right of i and add 1 to DP[i] accordingly.

    Code

    → Reply