Всем привет!
В ближайшую субботу, 24 мая 2014 года, в 19-00 по московскому времени, состоится третий квалификационный раунд Russian Code Cup 2014.
Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru
Участвовать могут все, кроме 401 участника, которые уже квалифицировались в первом и втором раундах.
200 лучших проходят в отборочный раунд, а остальные смогут попробовать свои силы в четвертом квалификационном раунде 1 июня.
И немного приятных новостей: мы обновили версии компиляторов почти всех языков, добавили возможность отправлять на C++11 под GNU C++ (а Visual C++ 2013 и так поддерживает C++11) и добавили Java 8 (Java 7 тоже пока остается). Актуальные версии компиляторов и строки компиляции на странице с правилами чемпионата http://www.russiancodecup.ru/rules
Всем удачи!
[UPD] Всем спасибо за участие, раунд завершен. У нас снова 201 прошедший, поздравляем! Разбор будет опубликован в ближайшее время.
надеюсь задачи будут не хуже тех, что были в прошлом квалификационном раунде.
Не будет ли проблем с Java 8, связанных с крашем VM из-за политик безопасности вашей песочницы?
Ну, на наших тестах проблем нет, спасибо, что напомнили, потестирую nextProbablePrime
Протестировал, не падает.
Недавно было ещё сообщение, что источником подобных проблем могут быть вызовы параллельной обработки стримов и прочего параллелизма, который добавили в Java8 (Arrays.parallelPrefix).
Если есть желание, чтобы я запустил какой-то конкретный код, можно его прислать
Возможность скачивать свои посылки так и не появится?
Мы внимательно отслеживаем все пожелания и по мере возможности постараемся добавить разные фичи. На ближайшем квале, к сожалению, возможности просматривать отправленные решения не будет.
Еще не очень удобно, что таблица результатов так часто обновляется, например, при поиске участника
Слишком часто обновляется? Серьёзно?)
Спасибо, ни одна просьба не остается без внимания :)
Как решать D?
Ну и скажите решение C c док-вом, пожалуйста.
Задача С: Для начала нужно понять что два простых нечетных циклах, пересекающиеся по ребру создадут четный цикл ("логическая" сумма циклов) Тогда ясно, что два цикла могут пересекаться только по вершине, а далее рисуем ромашку циклами по три.
У меня в D динамика true/false [position][candies]. Перейдем от массива к частичным суммам на префиксах, и будем раздавать по одной конфете сразу всем участникам каждой из первых х команд. Начнем с всего набора команд и всех конфет, заранее раздадим каждому участнику по конфете. Далее возможные переходы в динамике:
Сложность получается О(d*n), где d-кл-во конфет и n-кл-во команд. Верно? Я подумал, что 10^8 может не хватить=(
Да, именно. O(d*n) по времени и по памяти. Хватает с запасом. Там целых 2 секунды, а такое решение, подозреваю, и в 0.5с зайдет.
То же самое, только динамика одномерная. Можно действия, которые у вас в динамике, провернуть в начале, перейдя к задаче, аналогичной из условия, но где все ai могут быть любыми неотрицательными числами. И такая задача уже решается простым рюкзаком. upd. Не утверждаю, что так лучше, просто поделился.
Так однозначно лучше, потому что по памяти стало О(d) вместо О(n*d).
C. понятно что граф реберный кактус, если нет тогда один из простых циклов четный.
Отсюда следует что цикл из трех вершин выгодно, и они должны пересекаться по вершине.
Сначала говорим, что первая команда получает по N конфет, вторая — по N - 1, ...
Если после такой раздачи конфеты ещё остались, то считаем префиксную сумму по количеству человек в команде (т.е. для третьей команды эта сумма будет равна x[1] + x[2] + x[3]).
Потом раскладываем оставшееся число конфет на слагаемые, а слагаемые — это префиксные суммы, посчитанные на предыдущем шаге.
Ответ восстанавливается по посчитанной динамике стандартным образом, если вдруг кому-то нужно, могу расписать.
В задаче D, из условия на неравенства, если s = n * a1 + ... + an > d, то NO. Далее задача сводится к такой: получить из s путем прибавления к х-ксам на префиксе число d. Заведем массив p[d] и будем считать для каждого d >= i > s — p[i] = j, где j — конец какого-то префикса, изначально делаем p[i] = -1 (что получить пока нельзя). Если p[d] = -1, то NO. Иначе легко восстановить ответ по массиву p. Могу дать общие соображения по С. Явно, что если есть нечетный цикл, то в нем ребер других нет. Поэтому лучше брать совокупность циклов, пересекающихся по вершинам. Для максимальности количества ребер надо использовать циклы длины 3 и сцеплять их по одной вершине. И да, если вершин четно, то нужно еще ребро добавить.
D. Перейдем в другие координаты, x → y, a → b, где
, 
. Для понимания картинка:
Тогда там надо решить
, где bi > 0. Уменьшим d на 
и перейдем к 
, где b'i ≥ 0. b'i ищутся тупым рюкзаком, потом из них восстанавливаются bi и ai.
Как решать E?
По кд прыгает страница с задачами. Поправьте, пожалуйста. Firefox 25.0.
Купи линку))
Добавил контест в тренировки: 2014 Russian Code Cup, квалификация 3
А куда пропал питон 2.7??? Набрал первую задачу и только потом с ужасом обнаружил, что питон 2.7 в принципе отсутствует в списке. Предупреждать же хотя бы надо! Опять же, на втором десятке 21-го века не иметь питона 2.x в списке языков... Это за гранью добра и зла.