csacademy's blog

Round #24
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 #24 will take place on Tuesday, 11/Apr/2017 15:00 (UTC). If you want to take part in this round you need to register before the contest begins. This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

We are honoured to have Arterm as problem setter.

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.

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.

Later Edit:

Congratulations to the winners:

  1. Lewin
  2. rajat1603
  3. Reyna
  4. black_horse2014
  5. uwi

Also, the editorial has been published. Hope you enjoyed the contest!

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

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Just a reminder, the contest starts in 4 hours.

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

When I click on the "Register" button, it doesn't make anything. Am I registered for the contest?

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

    No, you are not registered :(. I just checked the registration process, on Chrome it works for me.

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

    Well, I just tried with Firefox and it worked. Yet it looks like it doesn't work with Safari.

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

      Yes, we have some unresolved issues on Safari.

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

Was unable neither to recover my password, nor to register new account in firefox.

UPD: Managed to login somehow, don't know how..

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

is anyone having issues submitting?

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

I am author of tasks Ball Sampling, Subsequence Queries and Colored Forests. How do you feel about problems?

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

    I think they were nice problems, but they felt very similar to your hackerearth round last month here. I copied the code I wrote from Retroactive Integers and Connected Permutations over to Subsequence Queries and Colored Forests respectively.

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

      Hmm, that's quite surprising =)
      I expected solution with matrices and inverses on the prefix in Subsequence Queries. I didn't manage to apply that solution here.
      For Connected Permutations you need to just divide two polynomials in , and here you need more advanced algorithm.

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

        For Subsequence queries, I think the inverses is a nice idea, so I can see how they are distinct. It is a bit unfortunate that you can solve it the same way as retroactive integers though.

        For connected permutations vs colored forest, I used the same solution divide and conquer for both (maybe I didn't need such a complicated solution for connected permutations though). Here are the diffs between my two submissions to those: https://www.diffchecker.com/M7jXNQIc The biggest difference is I had to compute the number of ways to color n objects using exactly m colors, but that part is not too hard.

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

          Haha, seems you missed much simpler solution when tested Connected Permutations, and I missed that you missed this.

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

    I liked the last two problems (although I couldn't solve them) and spent the last hour happily thinking about them. For Ball Sampling, I feel like this is a way too standard application of a fairly well known technique. I have seen the same things with masks appearing a few times before :)

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

Ain't that suspicious, guys????? #cheaterseverywhere #cheaterreport #csacademypolice #sarcasm

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

I couldn't open a new tab in csaacademy. is that a feature or I couldn't ?

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

If we don't return balls to box in Ball Sampling problem then we get much more interesting problem (but still solvable). It is problem F from here: http://codeforces.me/gym/100497

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

Why are such problems as Vector Size included in Div1 contests? Are there no separate problemsets for Div1 and Div2?

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

    We don't have enough users for a separate Div. 1 contest yet. We'll split the divisions as soon as we reach a critical point.

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

Can someone explain the solution for "Subsequence Queries" more clearly.I'm unable to understand how are we using a matrix for dp transformations.

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

    Consider the O(N) solution first.
    Let the string be A = a1, a2, a3, ..., an
    then
    dp[0] = 1
    dp[i] = dp[i-1] * 2 — dp[last[a[i]]-1]
    where last[a[i]] is the last occurance of a[i]
    Now suppose you are at position i
    Consider the vector <dp[i] , dp[last[0]-1] , dp[last[1]-1] , ... , dp[last[8]-1]>T
    This can be transform to the vector for position i+1 pretty easily by a matrix multiplication.
    So you just need product of matrices from a range and multiply it by the vector <1,0,0...,0>T.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Can someone explicitly explain the solution of task E, Thanks a lot!

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

In problem F, why are those matrices invertible ?

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

    in my solution the matrix for a digit 'd' looks like this:
    A[0][0] = 2
    A[0][d] = -1
    A[d][0] = 1
    A[d][d] = 0
    and the rest of them are the same as identity matrix.
    This matrix can be obtained in a series of elementary operations as follows:
    1. A = identity matrix
    2. Multiply R0 by 2
    3. Subtract Rd from R0
    4. Add R0 to Rd
    5. Divide Rd by 2
    Hence the matrices are invertible.

    → Reply