Привет, Codeforces!
Мы рады сообщить, что готовы провести новый раунд на csacademy.com. Раунд #14 состоится в понедельник, 14/11/2016 в 20:00 (Мск). Раунд создан для Div2, это означает что изменение рейтинга коснётся только пользователей с рейтингом ниже 1550, а также пользователей без рейтинга. Юзеры с высоким рейтингом могут принять участие неофициально.
Огромное спасибо Yury_Bandarchuk за перевод заданий на русский язык!
Если вы хотите принять участие в этом раунде, Вам необходимо зарегистрироваться перед началом соревнования. Так как раунд создан для Div2., он будет состоять из 5 задач средней сложности.
Формат конкурса:
- Вам предлагается решить 5 задач за 2 часа.
- Мы обеспечиваем обратную связь на протяжении всего конкурса.
- Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-ICPC-style);
- Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000;
- Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.
О системе пенальти:
- Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
- Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
- После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.
Мы по-прежнему рекомендуем использовать обновленную версию Google Chrome. Если вы обнаружите какие-либо ошибки, пожалуйста напишите нам по адресу contact@csacademy.com или в комментариях
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 :)
Here is the editorial. This is the best thing I like about cs-academy. Instant editorials.
How did you solve D? I couldn't understand the editorial completely.
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
I asked for D's solution, it seems you explained C ;)
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
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.
Thanks both of you. I finally got it :)