Всем привет!
Мы рады представить окончательную версию правил Russian Code Cup 2016! Важнейшее нововведение этого года — чемпионат становится международным, теперь задачи предлагаются на русском и английском языках. Все могут принять участие, для этого необходимо зарегистрироваться на сайте http://russiancodecup.ru, участникам прошлых чемпионатов необходимо подтвердить участие в этом году в личном кабинете.
В этом году участники вновь сразятся за звание лучшего программиста и призовой фонд в размере 750 000 рублей. Мы изменили структуру призового фонда, чтобы дать еще больше денежных призов, теперь участники, занявшие места с 11 по 25 также получат призы. Победитель чемпионата получит 150 тыс. рублей, обладатели второго и третьего места — 100 тыс. и 65 тыс. рублей, соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 тыс. рублей, с 11 по 25 место – 15 тыс. рублей. 200 лучших участников отборочного раунда получат футболки с символикой чемпионата.
Основная программа чемпионата состоит из трех этапов: квалификационных раундов (8 мая, 29 мая и 5 июня), отборочного тура (19 июня) и финала (18 сентября). На каждом этапе участники олимпиады должны решить от четырех до восьми разноплановых задач. Программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур пройдут по 200 лучших участников из каждого квалификационного раунда, а в финале будут сражаться 50 лучших программистов.
Приглашаем всех на первый квалификационный раунд в воскресенье 8 мая, в 19-00 по московскому времени и желаем удачи всем участникам!
Привет всем. Довольно много в последнее время проводится спонсорских турниров на Кодфорсес (что супер). Но не покидает ощущение, что такие соревнования на практике затрагивают слишком маленький процент участников Codeforces (в призовой зоне оказываются одни и те же), хотя с легкостью могли бы стать соревнованиями, касающимися едва ли не всех.
В качестве примера можно вспомнить турнир от Wunder Fund зимой. Ребята придумали интересную идею — давать футболки случайно с 50 по 500 место, многие впервые получили какие то призы (пусть, символические) на Codeforces, а шанс имели как минимум все синие. Соревнование за призы компании получилось для нескольких тысяч человек. Очень позитивный пример.
Просьба не воспринимать сообщение как совет компаниям, как надо делать и как не надо делать :) Просто способ, как сделать ваше соревнование чуть менее справедливым, но чуть более массовым.
Всем удачи на предстоящем контесте!
What if I have no middle name?
You can fill in your handle.
The question is rather: do you have to fill in your handle? And the answer to it is: no, any visible string, even an almost invisible one like ".", is enough.
Fill in the name of your father with suffix "ovich".
Example: John Smith, the son of Adam Smith -> John Adamovich Smith.
mail.ru еще даже не прислали мне футболку с прошлого контеста (Russian AI Cup).
буквально вчера получил ее, до Бреста уже успела дойти
Значит нужно скоро ждать. Спасибо!
До сих пор не получил футболку RCC с прошлого года.
Это вы конечно правильно сделали, что не стали напоминать о том, что через час будет первый раунд.
Рассылка за полтора часа была отправлена.
В которой вы рассказали о начале
1-ого раундаразогревочного раундаВ самом письме написано про первый.
Да, вот только что сообщение пришло. Но было бы лучше анонс на главной CF. Не знаю как другие, но я почту редко проверяю.
У меня на один e-mail пришло за 65 минут, на другой за 55. Думаю, у кого-то и после старта может прийти.
На какой платформе будет контест?
http://www.russiancodecup.ru/ru/
Wow that thing is SLOW...
How to solve D?
Precompute the ans for each value of k<=5*10^5 in O(maxn*log(maxn)), where maxn = 500000.
For query of type 1: find all factors of t[v] and add 1 to those.Update value of t[v].
For query of type 2: find all factors of t[v]-1 sub 1 from those.Update value of t[v].
For query of type 3: Output the answer in O(1).
Overall complexity. O(m*(sqrt(max(t[i]))).I had to use fast I/O and other optimizations to get this AC.
Ужааасно дооооолгое тестирование
What's the intended complexity in D? If it's O((N + Q) * sqrt(max_number)) the constraints look way too high.
I have O((N + Q) * f(max_number)), where f(x) is number of divisors.
Let K = 500000. Complexity of my solution is: Preprocessing O(N + K log K) and O(max_divisor_count(K)) per query.
I got AC with
, where C = max_number.
I have a complexity O((N + Q) * sqrt(MAX_NUMBER)) and it's ok :)
Ждать по 10 минут вердикта очень печально. Хотелось бы какую-то более быструю проверку.
Ага, я ждал 10 минут А и получил compilation error =\
Я под конец послал 5 решений по D с разными константами.
До сих пор не могу увидеть результата.
Весь контест не мог пробить C и D на джаве по времени. Это какой-то адец. И 502 в конце раунда это просто замечательно
Choose your favourite C++ compiler:
- slow
- very slow
- as slow as RCC testing system
Compiler is ok, except stdio. I saw such trouble on ROI and NEERC, and it's common trouble for all new enough mingw builds.
Fix is one of following:
1. use -D__MINGW_USE_ANSI_STDIO=0 in command line (i'm not sure if it's enough in code)
2. use -std=gnu++11, instead of -std=c++11.
как решать C быстрее, чем за
?
можно предрасчитать gcd-шки среди тех элементов a[i] у которых GCD(a[i], a[0])=K (один из делителей) и потом будет numdivisors^2 с константной gcd-шной. Но даже это на джаве не зашло.
я в итоге оставил различные числа, делил все на общий gcd и брал a[rand]
Я сделал бин поиск по делителям, но че-т не заходит, хотя я все еще жду вердикты на свои посылки.
Искал наибольший из делителей, чтобы второй gcd был больше этого делителя и после проверял еще рядом лежащие делители.
Это неверно:
1
3
6 7 9
Для делителя 2 получаем gcd(7,9) = 1 Для делителя 3 получаем gcd(7) = 7
Я от нечего делать написал рандом:
Рандомно выбираем число. Находим для него число, НОД с которым минимален. Предполагаем, что эти два числа будут в разных множествах. Жадно раскладываем остальные числа между множествами. Повторяем несколько раз (мне хватило 20).
20 * O( n log( max A ) ).
Тут второе слагаемое в худшем случае намного больше, чем первое. Поэтому нужно было факторизировать не за
, а за 
хотя бы.
там же тестов 1000, 10^7.5 это же вообще мало
Хм. Я думал что 10000. Во всяком случае, ускорение нахождения всех делителей позволило мне получить AC после TL, без каких-либо других отсечений и оптимизаций.
У меня зашло после замены a_0 на min(a) (и добавления отсечения по ответу)
Как решалась С? У меня решение O(n * f(ai)) не проходило по ТЛ, где f(n) — количество делителей числа n.
Если добавить перебор делителей с самого большого, отсечение если мы уже не улучшим ответ и случайный выбор начального числа — проходит
А какой компилятор был выбран? Просто или у них компы медленные, или дело в компиляторе. Я вот отправил на VS 2013 и получил TL на 6 тесте, хотя у меня на компе в VS 2010 он работает 0.9 с.
под gcc я тоже получал TL6 (локально под слангом, что мое, что авторское работают 0.7)
The website is unresponsive. Luckily after the contest!
Несколько замечаний после раунда:
Поиск — он ужасен. Он учитывает регистр, он требует полного слова с учётом регистра всех букв, иначе не находит. Я почему-то там Sergej. Я себя там с трудом нашел, когда хотел узнать на каком я месте, потому что нигде это не написано (или я не нашел?). Друзей даже искать не стал, звёзды явно были не в фазе Юпитера
Жууууутко доооолго тестируеееееет. 3 посылки ждал 7-8 минут, каждую.
Английский перевод так себе, задачу с поездом я понял только переключившись на русский интерфейс. И то, переключения не нашел, слава Богу замена языка в ссылке сработала
Система так и не научилась запоминать мой компилятор
Переодически появляется ошибка “Неверно заполнена форма” — почему, я так и не понял. Обновил страницу, указал тоже самое — приняли
Вы правда 6-ой год уже проводите это соревнование? Такой вопрос — почему на своей платформе, а не на Codeforces? Здесь проблем 1-5 уже решены
За соревнование спасибо, задачи интересные, хоть я сегодня и плохой танцор. Но будет ещё приятнее, если можно будет решать задачи не воюя с системой
В замечания еще можно кинуть качество задач. Первые две задачи — простые, на реализацию, с разбором частных случаев. А учитывая то, как проходило тестирование, такие задачи вообще давать нельзя.
Ну и конечно же стоит упомянуть про несколько тестов в одном тесте. Вам лень сделать несколько файлов? Или хотя бы проверить размер ввода (у меня B упала из-за TL).
А теперь представим сколько бы работало тестирование, если бы мультитесты были в отдельных файлах
FYI: нынче никто не делает мультитест "от лени". Обычно его делают, чтобы протестировать решение не на ~100 тестах, что за разумное время позволяют тестирующие системы, а на стольки, сколько душа пожелает.
И да, это полезное умение — чистить глобальные массивы.
Magical solution for C. Divide all numbers by their common GCD. Now it's easy to see that the answer is no less than 1 and we should check if it's at least 2, and if yes, find it. Let's calculate the following "DP": iterate over numbers, when passing the i-th number keep set of pairs (a, b) where a and b is the pair of gcd values we can achieve by splitting first i numbers into two sets. When passing the number x, we take each pair (a, b) and form two new pairs (gcd(a, x), b) and (a, gcd(b, x)).
It is now working in
, but we make a super-observation that we are not interested in pairs where one of the numbers is equal to 1 since we already know that the answer is not less than 1, they provide no information for us. Do not add such pairs and it gets AC. I have no single idea WTH it works. Maybe because I sorted all numbers in increasing order and uniqued them?
Why does it work for in O(n*n*logn)? It looks like there are O(n*logn) pairs (a,b) in the set. How did you estimate this?
Why are there less than 50 participants on some of the standings pages? 50 on page 1, 49 on page 2, 50 on page 3, 48 on page 4, etc.
Две просьбы-предложения организаторам:
1) Сделать задачи в блоке "Your results" кликабельными.
2) Запретить посылать одинаковый код дважды. (Сайт тупил, несколько раз нажал на кнопку "отправить" -> получил лишний штраф).
До сих пор стоит баг, который сбивал меня с толку весь контест (на самом деле у меня АС по обеим задачам).
What is the correct date and time of the Final Round?
It's written "September 18" here and "September 11" on the website.
The date on the site is corrected. The final round will take place on September 18.
Will there be an onsite round in Moscow for those who wish to come?
EDIT. Let me phrase the question differently: could you organize an onsite in Moscow like last year? I've already came to Moscow for this :)