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:
Also, the editorial has been published. Hope you enjoyed the contest!
Just a reminder, the contest starts in 4 hours.
When I click on the "Register" button, it doesn't make anything. Am I registered for the contest?
No, you are not registered :(. I just checked the registration process, on Chrome it works for me.
Well, I just tried with Firefox and it worked. Yet it looks like it doesn't work with Safari.
Yes, we have some unresolved issues on Safari.
Was unable neither to recover my password, nor to register new account in firefox.
UPD: Managed to login somehow, don't know how..
is anyone having issues submitting?
I can not submit any solution(
I am author of tasks Ball Sampling, Subsequence Queries and Colored Forests. How do you feel about problems?
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.
Hmm, that's quite surprising =)
, and here you need more advanced
algorithm.
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
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.
Haha, seems you missed much simpler
solution when tested Connected Permutations, and I missed that you missed this.
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 :)
Ain't that suspicious, guys????? #cheaterseverywhere #cheaterreport #csacademypolice #sarcasm
Is this sarcasm because it looks quite normal to me.
Yeah, I added it as a tag :(
Thanks for reporting, we'll proceed to ban these users :P
I couldn't open a new tab in csaacademy. is that a feature or I couldn't ?
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.com/gym/100497
Why are such problems as Vector Size included in Div1 contests? Are there no separate problemsets for Div1 and Div2?
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.
Can someone explain the solution for "Subsequence Queries" more clearly.I'm unable to understand how are we using a matrix for dp transformations.
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.
Thanks for the explanation.
Can someone explicitly explain the solution of task E, Thanks a lot!
In problem F, why are those matrices invertible ?
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.