csacademy's blog

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

Hello, Codeforces!

We are going to host a new contest at csacademy.com. Round #71 will take place on Wednesday, February/28/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
  • +81
  • Vote: I do not like it

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

Just a reminder, the round starts in 1 hour and 30 minutes.

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

How to solve E Losing Nim ? I didn't understand the editoral.

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

    Ok, So the editorial uses some DP, let me mention my combinatorical solution here. The main observation is that the xor of an array is 0, if all bits are set even number of times. So, the task reduces to finding the number of arrays for each length from 1 to N, such that each bit is set even number of times through the array.

    For each i from 1 to N, perform the following procedure , and let's call the number obtained as res[i] :

    For each bit from 0 to 8 ,create a polynomial of size N, where the co-efficient of xj, is if 2·l·2currbit divides j. This indicates that we set the bit in 2·l items in current series, that contributes 2·l·2currbit to the total sum.

    Now, multiply all these polynomials. Let res[i] = coefficient of xn after this. Now, only problem is that we could still have empty elements in arrays. However, notice that if array has k empty elements out of i, then it should be counted in res[i - k]. Then we can build new array ans[], where

    . Build this in left to right fashion. The meaning of this is that each way we can have i - j zeros in the array of length i, we create array of length j, deleting them

    Note that this is  > O(N3) overall, we can optimize, by noticing that for an i, for any bit j, only N / 2·2j entries are not 0, iterating only over them during polynomial multiplication.

    My Code

    → Reply