csacademy's blog

Round #14 (Div. 2)
By csacademy, 8 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. Round #14 will take place on Monday, November/14/2016 17:00 (UTC). This round will be a Div. 2, meaning that the rating change will only affect users with a rating below 1550. Unrated users will also be affected. High rated coders can participate unofficially.

Many thanks to Yury_Bandarchuk for translating the tasks in Russian.

If you want to take part in this round you need to register before the contest begins. As this is a Div. 2, it will consist of 5 tasks of more accessible difficulty.

Platform changes since Round #13:

  • Navbar redesign
  • Contest scoreboard filter added

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.

We still recommend using an updated version of Google Chrome. 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.

EDIT:

Congratulations to the winners:

  1. dragoon
  2. NikaraBika
  3. hey_boris
  4. the_art_of_war
  5. fanache99

And also to the Div. 1 winners:

  1. vintage_Vlad_Makeev
  2. atatomir
  3. Deemo
  4. Doge
  5. dreamoon_love_AA

We hope you enjoyed the contest!

EDIT2: Check out our new forum.

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Very nice D and E! How to solve E?

UPD1: Nevermind, I didn't know the editorial was here. At least I had an idea to use the same DP state! :D
UPD2: Thanks, rachitiitr, I didn't see the reply before editing my comment :)

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

    Here is the editorial. This is the best thing I like about cs-academy. Instant editorials.

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

    How did you solve D? I couldn't understand the editorial completely.

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

      Eliminated all possible 1s that cannot be a part of answer. From every 1, I go on in all 8 directions as far as I can go. While you do dfs, maintain the minimum values of row and column you encountered (x1, y1). Similarly maintain the largest value of row and column encountered (x2, y2). This will be a rectangle if sum(x1, y1, x2, y2) = (x2 - x1 + 1) * (y2 - y1 + 1). code

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

        I asked for D's solution, it seems you explained C ;)

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

          Oh sorry! In problem D, I found out the contribution of each bit in the sub-array participation. First contruct a 2D table where a[i][j] = ith bit in arr[j]. Then look for the contribution of bit i in subarray participation of sizes  ≤ span. Answer would be sum((contri(i, b) - contri(i, a - 1)) * 2i) for all bits i.

          Contri(i, b) means the contribution of ith bit when considering sub-arrays of size  ≤ b. code

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

      Compute the partial xor for each index, say the partial xor array is P. Now fix some index i and let's solve the problem for each subarray ending at i. We can easily find the upper and lower bound for the beginning of the array — say it can begin from index L to index R. We will separately solve the problem for each bit. Fix some bit j. Now say that H integers with indices in-between [L;R] in P have that bit and D integers don't have that bit. It's easy to see that D = R - L + 1 - H and H can be found using partial sums for each bit. Now, if P[i] has that bit, then add D * 2j to the answer. Otherwise, add H * 2j.

      → Reply