Привет, Codeforces! Мы рады сообщить, что собираемся провести новый раунд на csacademy.com. Наш бета раунд #6 состоится во вторник, 31.05.2016 в 19:00 (Мск). Если вы хотите принять участие в этом раунде, вам необходимо зарегистрироваться перед началом соревнования. Как и в двух предыдущих турах, мы сделали две дивизии ( Div1 + Div2), с 6 заданиями различной сложности.
Что изменилось на сайте с бета раунда #5:
- Мы добавили возможность виртуально пройти раунд. Теперь вы можете легко пройти прошедший тур в режиме онлайн, с таймером и смоделированными результатами других участников, просто кликнув на странице с контестами.
- Написанные коды участников стали общедоступными. Вы можете посмотреть на результат, перейдя к участнику через табло результатов и нажав флажок .
- Теперь онлайн-редактор поддерживает функцию "открыть файл". Больше никаких "copy-paste" во время решения.
- Мы добавили некоторые полезные сочетания клавиш для редактора. Наведите курсор на кнопку, чтобы увидеть соответствующую комбинацию клавиш.
Формат конкурса:
- Вам предлагается решить 6 задач за 2 часа.
- Мы обеспечиваем обратную связь на протяжении всего конкурса.
- Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-ICPC-style);
- Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000;
- Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.
О системе пенальти:
- Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
- Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
- После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.
Мы по-прежнему рекомендуем использовать обновленную версию Google Chome. Если вы обнаружите какие-либо ошибки, пожалуйста напишите нам по адресу [email protected] или в комментариях Вы так же можете найти нас на Facebook, Vkontakte и [Twitter](https://twitter.com/realCSAcademy.
Are the problems sorted by difficulty?
Yes, but sometimes we can mess up, like in Beta Rounds #4 or #2
In the last Codeforces round i had an exam next day, but still didn't study it.
This time i have an exam at the same round time, Should I stay home to participate in the round, or go do the stupid exam ??? :D :D :D
When is this exams thing ending
take my advice and don't attend the university, join the army :3
Can anyone please provide a case where my solution for Perm Matrix fails?
My idea is as follows:
It seems it fails in a lot of cases, but I can't find what's wrong in that logic. Here's my code just in case -> C++ Code
No, that one doesn't fail. I assign 1->2, 2->3, 3->1, 3->2.
But I already found one that does fail:
First element bigger than one is 2, so next I assign 3 to 3. I still don't know how to greedily assign elements without repetition (and without using max flow, of course). I suck at greedy.
I think on my example you'll assign 1->2, then 2->3
Now you have 2 and 3 used from 2nd row, left with 1 and 3.
So you can't match both 3's :) Anyway, your example is even simpler.
Editorial has been published already; I also sucked on this one — I implemented some overcomplicated trash with idea : move from left to right, prefer picking element for which remaning valid ways to place minus remaining entries is smallest.
You're right. It fails on your case too. Now you can see why I suck on greedy :P
Can someone explain me the detailed solution of this problem: https://csacademy.com/contest/beta-round-6/#task/exponential_game . I didn't understand the editorial. Thank you!
If all the heaps' values have even frequencies, then whatever move the first player makes, the second player copies his move and wins. Now, if there is at least a heap value with odd frequency we can split the biggest of them to make all of the other odd frequency values become even.
Can anyone explain how the greedy solution in the editorial works for Perm Matrix? I have no clue.
The greedy is: pick the most frequent element and match it with a different element on the opposite line and update the frequencies. In order for this to work, at any step there must be no element with a frequency of at least n + 1, considering we have 2 * n unmatched elements (according to Dirichlet, we couldn't make a matching if an element appears more than n times). Now, if the most frequent element has frequency of at most n — 1, then at the next step our condition remains viable as the maximum frequency won't be n. Now, if the most frequent element has frequency exactly n, at the next step this element will have frequency n — 1 which is ok. Now, if there would be 2 elements with frequency n, our only matching would be between them so there still wouldn't be an element with frequency n after the matching, so there is guaranteed that our condition remains viable during our greedy.