Всем привет!
В ближайшее воскресенье, 18 мая 2014 года, в 14-00 по московскому времени, состоится второй квалификационный раунд Russian Code Cup 2014.
Зарегистрироваться и участвовать можно на сайте http://russiancodecup.ru
Участвовать могут все, кроме 200 лучших (на самом деле 201, поскольку 200-е место было поделено) в первом квалификационном раунде.
200 лучших проходят в отборочный раунд, а остальные смогут попробовать свои силы в третьем и четвертом квалификационных раундах 24 мая и 1 июня.
Всем удачи!
Можно ли добавить, пожалуйста, строчку, как раньше было, что бы по хендлам(или именам, или еще как) можно было увидеть результаты выбранных людей? (возможно она уже есть, но по таблице результатов первого квала такого рода поиска, вроде, нету...)
Спасибо за ваше предложение. Мы постараемся по возможности реализовать пожелания по улучшению интерфейса, к сожалению обещать этого ко второй квалификации не можем.
Очень тонкий скроллбар, неудобно пользоваться с тачпада. Кнопки вниз-вверх на клавиатуре тоже прокручивают сайт кое-как. Выручает панелька для перехода между задачами, но хотелось бы, чтобы и стандартными средствами можно было прокрутить сайт куда хочется (желательно до того, как юзеры с мышкой уже сдадут одну задачу!)
Добавьте возможность поиска людей по части логина. =) Например, поиск людей в нике которых есть слово lord, pskov и т.д.
Предлагаю убрать штраф за CE. Ибо у всех на С++ разные компиляторы и т.д.
Я понимаю, что на завтра это вряд ли реализуемо, но было бы очень круто, если бы следующие квалификации можно было писать вне конкурса.
очевидный фикс по результатам предыдущей квалификации
В прошлый раз (тот раунд, что лагал), у многих оказалось не поставлена какая-то левая галочка в настройках, из-за которой они не могли отправлять задачи, в том числе и у меня. Теперь не могу найти эту галку (что-то вроде "да, я буду принимать участие"), ее отменили или где она находится?
http://www.russiancodecup.ru/personal/profile/
Правда ли, что должна быть надпись "Вы зарегистрированы на участие в чемпионате", в качестве проверки, что она стоит?
Надеюсь, что нет. Все-таки почти месяц был.
Первые две задачи просто отличные, побольше бы таких, дальше даже не читал
Как по мне то первая сложновата для первой.
Гена на 4-ой минуте сдал.
Лунев на 9-ой с 3-го(!!!) раза.
Это уже перебор господа!
Зеленые поминусовали
Когда страница результатов "автообновляется", сбрасывается результат поиска по нику.
Еще не понравилось что за ошибку компиляции дается штраф. И давали бы лог компиляции в нормальном виде, а не tooltip-ом.
Свое решение вообще можно где-то посмотреть во время контеста?
За ошибку компиляции штраф не даётся.
UPD: сорри, прочитал ниже, и правда штрафное время не изменилось. Хотя странно, что в таблице отображается лишняя попытка.
А вы пробовали? Мне тоже дали минус попытку за ошибку компиляции, и это действительно странно на онлайн-соревнованиях.
Посылка по задаче, по которой уже получил AC добавляет попытку и штрафное время, что за бред? В задаче A, у меня был WA когда использовал long long int, сменил на int все прошло, 8 попытка!! не могу скачать исходники чтобы подтвердить.
Может, вы этот long long int читали/выводили по-кривому?
cin, cout.
Compilation error учитывается как неверная попытка?
Штрафное время не прибавляет.
Больше разбора случаев, хорошего и разного!
Не знаю, у меня лишь один маленький спешл кейс в D, остальное всё без всякого разбора. Наверное, зависит от того, как писать.
Задача E — конечно трололо. Кто бы мог подумать, что там решение за O(n * m) :) Нижние границы >= 1 — это чит.
Но стоит признать, что идея добавлять в рюкзак сразу интервал чисел (step * [0..upper_bound]) за линию — довольно красиво (удивительно, что я её раньше не встречал). Я сначала хотел это сделать двоичным подъёмом, но решил, что java вряд ли успеет ~40 миллионов * log, и подумал ещё немного. У кого-нибудь зашёл двоичный подъём?
http://petr-mitrichev.blogspot.ch/2011/07/integral-bounded-knapsack-problem.html
а что такое двоичный подъём для рюкзака?
Ну в данном случае это следующее. Пусть у нас есть массив рюкзака d, нам надо применить переход для числа step несколько раз (cnt). Т.е. нам надо выполнить d = fstep(d) cnt раз, т.е. посчитать fstepcnt(d). Это можно сделать стандартной техникой за O(log(cnt)) переходов. (более "интуитивное" объяснение: посчитаем, что будет, если мы применим fstep 1, 2, 4, 8, ... раза, а после этого за log(cnt) операций соберём ответ).
таких дерьмовых задач давно не видел, спасибо авторам.
смею предположить, что либо вы заняли дерьмовое место, либо дерьмово программируете, либо это эффект дерьмового интерфейса сайта так сказался. нормальные задачи для квала.
Лол, у аналогичного комментария сверху -40. Наверное, среднему пользователю ЦФа больше нравятся пони, нежели кореянки
Я был искренне убеждён, что в "комментарии сверху", набравшем -40, нет сарказма :) Возможно, не я один, оттуда и минусы
ЦФ не может в сарказм:(
Расскажите, как решать E? Я свёл к рюкзаку примерно из 700 предметов, каждый из который можно брать определённое количество раз. Ну или примерно из 10 000 предметов, каждый из которых можно брать один раз. На сумму до 500 000, разумеется. Но это вроде как в TL не влазит.
На самом деле там 350 предметов, и не 500к, а 250к (потому что каждая пара 2 раза считается). И каждый предмет можно добавить за линию (с частичными суммами/sliding window), в итоге там в худшем случае ~40M операций, и даже на джаве с запасом в ТЛ влезает.
А... К числу
cnt[j + kol[i]]прибавляется то же самое, что и кcnt[j], только сc[j]и безc[j - r[i]*kol[i]], так? Круто, спасибо.Да, ровно так. Имхо, красивая идея.
а почему 350 предметов? например, звездочка из n вершин. вес каждого предмета n-1. n может быть до 501. ((n-1)*(n-1) <= 250K).
Да, но это не худший случай (т.к. m становится слишком мелким). Худший случай — что-то порядка 350.
А правда ведь, что в E все запихнули n*m в том или ином виде, с проверкой на совсем бред?
В принципе, мне даже не сильно пришлось пихать (какой-то очевидной оптимизации в два раза хватило). Но как-то это не похоже на ИТМО.
После if (m<n*(n-1)) { puts("0"); return; } Как-то и пихать не надо.
ОК, ЛДЫБР и жалобы на жизнь удалены. Больше не буду.
У меня одного на условиях "прыгала" страница? Браузер — хром.
А разбор задач будет?
Первые 2 задачи сделали свое дело. +5 и +4, в итоге 204ый (:
201-й же))) самое обидное место я считаю)
Не знаю, что случилось, но у меня точно было 204ое место в момент, когда раунд закончился. Проверка какая-то дополнительная?
Да, выгдядит так, будто буквально человека 4 убрали из окончательной таблицы: я поднялся ровно на 4 места через неоторое время после конца
А будет возможность дорешать?
1 раунд был в тренировки добавлен, наверное и 2 добавят
Спасибо за ответ
скачать тесты
Спасибо за раунд!
Новый интерфейс в раунде 1 не видел, а в раунде 2 всё, что было, вроде как работало. Из того, что хотелось бы видеть исправленным (браузер Firefox 29.0.1, если что):
Есть ещё какие-то мелочи. Вообще, куда слать багрепорты — в связь с жюри, в обратную связь, сюда, кому-то в личку?..
Добавлю ещё — таймер на главной бежит на ~30% медленнее реального времени.
Я, чуть было, на этом не попался.
Люто плюсую!
Хотелось от себя добавить, что после автообновления страницы поиск пользователя в результатах сбрасывается, и показываются общие результаты. Плюс хотелось бы не вводя свое имя в поиск, видеть себя в таблице результатов (как это реализовано на КФ, например)
Спасибо за комментарий.
Все пожелания, которые высказываются здесь, читаются. Также можно написать отзыв или пожелание через обратную связь на сайте.
Пожалуйста, включите C++11 к следующему туру!
Да, без C++11 неприятно. Люто плюсую. Хоть и использую мелочи, не хочется терять время из-за мелочей и переделок.
Как решать D?
Из условия следует, что полученный граф может иметь вершины степеней только 1, 2 и 3. Также, если нам нужно минимальное количество операций, значит операция удаления ребра применима только в том случае, когда на удаляемом конце находится лишь одна вершина. И такими операциями мы получаем все вершины степени 2, за исключением максимум одной — корня.
Отсюда вытекает само решение: Посчитаем степени всех вершины. Если есть степени больше 3, выводим - 1. Если нету вершины со степенью 2, значит применять операцию удаления нужно лишь один раз к корню, и ответ будет
, иначе применять операцию удаления нужно ко всем вершинам степени 2, кроме одной, и ответ 
И ещё не забыть случай
n=1.Если бы он был.
Сорри, опечатался.
Если у какой-то вершины степень >= 4, то выводим IMPOSSIBLE. Далее заметим, что исходная вершина войдет в ответ (иначе неоптимально будет — по факту, все дерево будет сгенерено из другой вершины + операции по появлению это вершины). Далее если есть вершина степени два, то выбираем любую из них, принимаем ее за корень и честно генерим дерево, удаляя лишнее, где это необходимо. Если такой вершины нет, то генерим из листа. На практике достаточно вывести формулу, исходя из количеств вершин нужной степени, причем формула не зависит от того, что приняли за корень.
Ну и, конечно, не забыть об абсолютно отдельном случае n = 1)))
Абсолютно строго доказывать сие я не умею, но сие зашло)))
Спасибо, написал на контесте то же самое, не зашло, думал неправильная идея, сейчас перечитал код, заметил, что после вывода 0 на тесте 1 не написал return 0;
Я считал динамику
d[v][parent]— минимальное количество операций, необходимое для получения поддерева вершиныv, придя в нее из вершиныparent.parent = 0— если текущая вершина корень.Поскольку степени вершин не превосходят 3, то у каждой вершины может быть не более трех предков, поэтому достаточно массива размерности
d[N][4].Ответ на задачу
ans = min(d[v][0]).Напоминание о раунде немного задержалось. В правке скрин.
у Вас вообще почти вовремя пришло, что Вы жалуетесь :)
в правке скрин...
У вас оно вообще пришло ))
Ещё не всё потеряно! Мне пришло всего пару часов назад.
Мне вот сейчас пришло. Но может надо отнестись с пониманием, ведь рассылка почты не самое привычное дело mail'а ;)
Найдётся ли добрый человек, который добавит в тренировку?
Как решать B без стенки из ifов?
Перебрать все расстановки ладей в верхнем левом квадрате 3x3.
Не помню задач за последние полгода, чтобы там не было операторов if. о_О
понять, что ответ mx + ny - xy - 3 где x, y число различных соотвественных координат.
Надо ж ещё проверить что x<=n, y<=m.
UPD. x<=3, y<=3, x+y>=4
ifoв всего 6, небольшая стенка то)
Добавил в Тренировки: 2014 Russian Code Cup, квалификация 2. Отличный архив, всё сразу и без проблем залилось!
Мне только что (6 часов 19 мая) напомнили о втором квалификационном раунде (второй час 18 мая). mail.ru — Почта России в интернете.
http://pasteboard.co/
У меня почтовый ящик тоже на мейл.ру (inbox.ru) такое же письмо и в то же время. Обидно, что я не получал уведомлений вовремя, и уже второй раз пропускаю по этой причине отбор.
Первый раз ты ничего не потерял.