Всем привет!
Уже завтра, 18 сентября 2016 года, в 12-00 состоится финал RCC-2016. Лучшие 50 участников отборочного раунда сразятся за ценные призы. Продолжительность финала в этом году — 2 часа, финал проходит в режиме онлайн. За ходом финала можно наблюдать на сайте http://russiancodecup.ru
А мы рады объявить, что команда Russian Code Cup совместно с проектом Codeforces приготовили небольшой сюрприз всем тем, кто не прошел на финальный раунд RCC-2016. Сразу после окончания финала, в 14-05 на платформе Codeforces пройдет онлайн-контест по задачам финала.
Контест пройдет по правилам ACM ICPC и будет нерейтинговым. Задачи буду предложены на русском и английском языках. Задачи были подготовлены для финала Russian Code Cup, и поэтому они довольно сложные, контест будет интересен, скорее, участникам из Div1. Разумеется, мы просим всех финалистов не использовать онлайн-контест для дорешивания задач, а, дождавшись окончания, дорешивать в архиве.
Итак, приглашаем всех поболеть за финалистов, а потом ждем всех желающих на онлайн-контесте! Всем удачи!
What's the point of making it for div1 only if it's unrated for everyone?
I think div2 participants can also participate (but not recommended to do so)
It will be much difficult for div2
Registration opened before Round 372's rating changes, therefore, there are some colors that are wrong in the registrants' list, which is very weird because the ratings are correct.
Some blue people have a better rating that some purple people, for example...
Do you know the meaning of "Recommended" ?
Yes, but you probably didn't get the meaning of my comment...
Тех, кто пока далек от критериев отбора в финал RCC (топ-50 по миру) приглашаю поучаствовать в тренировке 2016 (IV) олимпиада МИСиС по программированию, очный тур, которая начнется в воскресенье 18-го сентября в 12:00 (московское время). Для участия следует перейти на страницу Тренировок.
Anyone knows if the tasks will be sorted in the order of their expected difficulty?
(y)
You are wrong. Even few finalists (!) didn't solve any problem.
I saw many people div2 maybe they want to try
have the problems been sorted by difficulty ?
Кароче. Хватит безумствовать. Поигрались со своей платформой, здорово. Пожалуйста, воспользуйтесь чем-то адекватным. Яндекс.контестом, например. Яндекс конкуренты, нельзя? Окей. Codeforces. Они же не конкуренты? Боже, да даже e-judge и PCMS в своей простоте куда лучше.
Кароче. Хватит безумствовать. Поигрались со своим мнением, здорово. Пожалуйста, воспользуйтесь кем-то адекватным. tourist, например. tourist конкурент, нельзя? Окей. Petr. Он же не конкурент? Боже, да даже Bredor и Huyum_nik в своей простоте куда лучше.
Хм. Забавно вообще. После каждого раунда куча комментариев о том, что всё медленное, вырвиглазный дизайн, неудобное отображение задач, неудобный монитор и так далее. А сейчас все молчат. Всех все устраивает?
Я понимаю, что меня многие не любят. Я вертел политкорректность и так далее. Если вы продолжите минусовать верхний комментарий, то его скроют. Если вы считаете, что комментарий слишком грубый, но суть верна, пожалуйста, потратьте 3 минуты на написание вежливой версии комментария, а потом можете агитировать за проставление минусов всем моим комментариям и постам.
К RCC: Если вы считаете, что я своим комментарием оскорбляю вашу компанию и божественную платформу для проведения контестов, можете оставить себе те 30К, которые я сегодня якобы выиграл. Еще лучше, если меня просто исключат из результатов.
К авторам задач: Никаких претензий.
Ну это в любом случае худший финал за все годы RCC, но вовсе не из-за системы. Я вот сейчас редко контесты пишу и мне больше за время на контест обидно.
30К можешь раздать тем из двузадачников кому не досталось :)
Не могу понять, это недовольство финалом или просто системой вцелом? Потому что финал прошел дольно гладко. В прошлых раундах были жутчайшие очереди проверок, поэтому люди сильно возмущались. В этот раз их не было, потому что писало 50 человек, да и засылать что-то почти нечего было. Старая проблема с тем, что трудно выискивать знакомых участников по одному в этот раз тоже никак не влияла, таблица занимала всего лишь две страницы. Задачки читались и отправлялись вроде нормально.
А так да, система требует доработки напильником...
Системой в целом.
Конкретно на финале проявились только такие проблемы:
- отсутствие внятной системы кларов
- не самая удобная система отправки решения (меня избаловали тем, что большинство других джаджей запоминает язык, на котором я сабмичу)
- странный интерфейс (все на одной странице, после сабмита кидает куда-то наверх)
Не особо удобно отображение штрафа в формате h:mm.
Еще меня поразило требование выводить пустую строку в задаче C. Еще есть чекеры, которые не игнорируют пробельные символы (кроме специализированных)?
Ну, да, с этим я в основном согласен. Правда задачи подготовлены довольно хорошо, обычно желания заслать клар не возникает :)
Задачи по одной можно, конечно, открывать. Только система перехода между ними сильно хромает. Чтобы открыть одну конкретную задачу нужно или переходить на отображение одной задачи и прощелкиваться до нужной. Ну, или еще в общих результатах буквы кликабельные. Нет, чтобы в таблице наверху страницы хотя бы ссылки сделать...
Требование выводить пустую строку между тестами вполне обычное в задачах с подобным выводом. Тем более так нагляднее.
Еще можно букву задачи в урле менять
Задачи хорошие, но время на контест это просто эпик фейл. 2 часа на эти задачи это конечно полный пипец, это не яндекс-контест же. Я по традиции первый час протупил, и если бы хотя бы 2:30 было я бы мог разогнаться и сдать третью, но по-хорошему для финала такого соревнования надо хотя бы 3:00. 3 из 6 у победителя это ни в какие ворота.
Как В решать?
Циклы найти можно простым DFS. Дальше, нас не интересуют цвета которые не в циклах, они у нас всегда будут. Создадим новый граф, слева будут цвета а справа циклы, по одному ребру на каждое старое ребро в данном цикле данного цвета. Пустим поток, слева пропускная способность 1 из истока в каждый цвет, справа по (длина_цикла-1) из цикла в сток. Результат — сколько цветов нам удастся оставить дополнительно.
Nobody solved more than 3 problems out of 6. Nobody in this unofficial round solved more than 2 problems. (I didn't solve anything — I started 1 hour late, read the problems, looked at the scoreboard and decided not to bother.) Seems like the contest would have benefited from more time or keeping backup problems e.g. for next year.
lol
It seems that N * M <= 10000 was chosen instead of the usual N, M <= 100 such that solutions based on Hall's Theorem fail.
My solution is based on Hall's theorem and passed (are there any other solutions?). In the worst case you can handle cases with N = 1 separately, and when N > = 2 it should pass easily.
I overlooked the fact that O(n2·m2) passes. Simple implementation for anyone interested — 20743833.
Editorial is here http://www.russiancodecup.ru/en/press/razbor-zadach-finalnogo-raunda-rcc-2016/
Do anyone know the O(n) algorithm of problem B described in the solution?
http://pastebin.com/r3L9cqGY
O(nα(n))
Can be reduced to O(n) with another DFS instead of DSU.