Привет, Codeforces! Мы рады сообщить, что собираемся провести новый раунд на csacademy.com. Раунд #24 состоится во вторник, 11 апреля 2017 в 18:00 (Мск). Если вы хотите принять участие в этом раунде, Вам необходимо зарегистрироваться перед началом соревнования. Раунд разработан с учётом участия обоих дивизионов ( Div1 + Div2), с 7 заданиями различной сложности, которые Вам предлагается решить за 2 часа.
Мы рады представить Arterm как одного из создателей задач.
Формат конкурса:
- Вам предлагается решить 7 задач за 2 часа.
- Как обычно, мы обеспечиваем обратную связь на протяжении всего конкурса.
- Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-ICPC-style);
- Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000;
- Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.
О системе пенальти:
- Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
- Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
- После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.
Если вы обнаружите ошибки или баги, пожалуйста напишите нам по адресу [email protected] или в комментариях ниже.
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.