Всем привет!
Напоминаю, что 9 марта в 12:00 начнется второй квалификационный раунд чемпионата VK Cup 2012.
Это последний шанс пройти в Раунд 1. В Раунд 1 проходят все участники, набравшие не меньше баллов, чем участник на 800-ом месте. Вас ждет несколько несложных задач, примерно расположенных по возрастанию сложности. Во время квалификации задачи тестируются системой только на претестах, а системное тестирование состоится после окончания квалификации (которая идет сутки). Претесты не покрывают все возможные случаи входных данных, так что тщательно тестируйте свои программы! Взломов, падения стоимости задач во время квалификации нет.
Раунд продлится 24 часа, но это не значит, что мы призываем вас все это время провести за решением задач. Мы надеемся, что большинство участников справятся с задачами (или с большинством задач) за более короткий срок. Такая длительность раунда выбрана для того, чтобы каждый нашел удобное время для участия.
До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 1 пройдут сильнейшие. Когда квалификация будет завершена, можно будет обсуждать задачи и решения.
Зарегистрироваться на раунд можно в любое время вплоть до его окончания. Результаты раунда не будут влиять на рейтинг, внеконкурсное участие в раунде не разрешается. Впрочем, все задачи попадут в архив после окончания раунда.
Желаем удачи и удовольствия от решения задач!
UPD: Тестирование завершено, проходной балл равен 3500 3450. Поздравляем всех, кто прошел в Раунд 1!
UPD 2: Мы удалили явных читеров и проходной балл уменьшился до 3450!
Насколько я понял, те 1000+ человек, которые прошли Квал1, они сейчас не участвуют?
Все верно.
А как организовано это ограничение? Невозможно зарегистрироваться или просто их результаты не будут учитываться?
Невозможно зарегистрироваться
Я правильно понимаю, что из первой квалификации прошло больше 800 человек? Т.е. у 800 места было 4000 баллов, а людей набравших 4000 и больше было более 800.
Да. Прошло чуть больше 1000 людей.
А будет ли администрация бороться с теми, кто пройдя Квал.1(и попав в раунд 1), зарегистрировал новый аккаунт для того, чтобы пройти и Квал.2(и попасть в раунд 1), т.е. один человек с двух аккаунтов прошел в первый раунд(по результатам Квал. 1 и 2), или все эти проблемы на совести самих участников?
Это почти невозможно проконтролировать.
И в чём смысл таких действий?
Самое простое поучаствовать и во второй квале, может просто потроллить(т.е. зарегать 10-20 акков, и на каждом сделать решенных к примеру по 5 задач, но с разным кол-вом баллов за счет неверных посылок, если таких человек 5-6 найдется, то это уже может часть мест просто слить в унитаз) и т.д. и т.п
Мне кажется таких весельчаков всё-таки поменьше...
Но, к сожалению, они есть. Например, обратите внимание на аккаунт I_want_solve_E
И решил ведь! =)
Уже разобрались с нарушителем http://mirror.codeforces.com/submissions/I_want_solve_E
Уже были прецеденты множественной регистрации аккаунтов, ничем хорошим они не кончились, так что не думайте о плохом, и решайте :)
Будьте проще. Если человек не сможет выйти из 600-800, то какой ему смысл дальше участвовать, если бороться придётся за бублики из 200 и 50?
скажите в графе мои посылки. Прога прошла претесты но в графе время написано 340 мс. и в графе память написано 67000 Кб. Это сколько затрачено в сумме на все претесты?
Это максимум по претестам.
спасибо за ответ
Если на претесте в задаче D 2670мс, то все плохо?
У вас же все ресурсы для проверки есть: "запуск", куча времени. Потестируйте :)
Не знал про вкладку запуск, спасибо
Полистайте посылки других участников, посмотрите их время и сделайте соответствующий вывод! Все просто:-)
Вторая квала, по сравнению с первой — халва по ходу.
Сколько времени от начала прошло, а еще даже 800 проходящих участников не набралось.
Не спешите делать выводы, пока не настал вечер, многие просто не хотят решать днем, скорее всего основная масса придет вечером. Хотя вторая квалификация должна быть легче, т.к. 1000+ участников прошли в первой квале и не будут участвовать сегодня.
задачи по моему сложнее.
Думаю устроители это сделали чтобы получить по итогам второго тура более разрозненную палитру результатов в сравнении с первым. Чтобы прошла не ~1000, а число более похожее на 800
может быть
Скорее всего, многие скажут, что я не прав и ничего не понимаю, но на мой взгляд, первая же задача, то есть А, здесь, по сложности, на уровне задачи Е в первой квалификации.
Да не, вот в первой квалификации я E не знал вообще как решать, а тут все (надеюсь) решил.
Хотя в среднем они посложнее, да
Я в первой (уже после, на дорешивании) решил 4 задачи и они оказались, по сути, довольно таки простыми. А здесь только на первую ушло полтора часа, да и неизвестно, правильно ли ее решил.
Не согласен, придумал А не задумываясь, в то время как прошлую Е решил только на следущий день
Хотя, как говорится на вкус и цвет
Ну, может и правда так, тем более у меня не слишком большой опыт. Но все же на мой взгляд, в этот раз задачи намного сложнее.
В целом, как сет, видимо да, сложнее.
Зато в этот раз E решаемая
В тот раз — тоже вполне.
Ну не буду спорить с оранжевым — просто тогда даже идей не было, а здесь за 10 минут придумал
На то он и оранжевый, что для него обе Е решаемые =)
Хотелось поспойлерить, рассуждая о сложности, а потом понял что контест не завершен еще. Но все-таки да, сет выглядит сложнее, и как-то непривычно (относительно первого) получать 420мс максимального времени. Даже возникает дилемма — оптимизировать алгоритм еще, или забить, надеясь, что запас времени еще большой :)
и да, все-таки не прошли они из-за таймлимита. но вообще удивлен насколько медленная проверяющая машина, а ее конфигурация (пусть даже виртуальная) не дана. в общем-то, три секунды в требованиях к задаче — довольно бессмысленная величина. обломно — "упавшие" задачи на локальной конфигурации проходят те же тесты за время в десятки раз меньшее лимита.
юзайте запуск, там написано сколько работает
Не надо винить серверы, надо писать правильные алгоритмы. Серверы тут очень быстрые, 10^9 сложений за 2 секунды только так заходят, как помню из прошлых раундов. Вон в четвертой задаче куб зашел.
Как думаешь за какое время будет работать это?
Можно узнать почему так?
Мгновенно. Компиляторы нынче умные :)
То есть оптимизация?
UPD
До сих пор удивляюсь
В первом случае сработает оптимизация, которая называется dead code elimination. Во втором чуть поумнее, не помню, как называется.
Вы хотите предложить мне серию каверзных вопросов, чтобы, когда я неправильно отвечу на один из них, высмеять меня? Это похвально.
Этот код, думаю, выполнится за ~ 0 мс — оптимизатор должен почуять, что циклы пустые и выкинуть их.
Просто столкнулся с этим на контесте. И жутко хотелось узнать, что это за магия.
P.S. Сплю и вижу как вас высмеиваю =)
Тогда немного странно, почему такой вопрос задается именно в эту ветку.
Похоже, вынужденное общение с анонимусом заставляет во всем видеть троллинг...
Я ещё слишком синий, чтобы троллить оранжевых =)
UPD В эту ветку написал так как вы напомнили о мощности сервера =)
в 4 задаче скорее в тестах дело
Не могу отослать задачу, выводится сообщение: "Вы должны быть зарегистрированы на соревнование для просмотра страницы". В списке участников есть, зарегистрироваться, естественно, не получается.
Есть две регистрации: на весь VK Cup и собственно на квалификационный раунд. Уже, наверное, третий десяток подобных вопросов пошел.
Imho. It Would have been nice if people that are old, obsolete and maybe at the gates of death were allowed to participate unofficially like in those division2 sets. Oh well.
You are in the top 800 in the Qualification Round 1. Congratulations, Round 1 is already waiting for you!
I am too old for this cup so I didn't participate in it. You probably saw my virtual contest result.
Oh, I guessed you must have qualified to next round.
Извините, можно вопрос, в прошлый раз я писал код с методами Readln/Writeln, и они нормально проходили. Сейчас попробовал сделать через input.txt/output.txt, но решение не прошло, ошибка времени исполнения. Разве нельзя входные/выходные данные задавать в текстовых файлах? Я искал в FAQ но ответа не нашел. Среда — Delphi.
ввод: standard input
вывод: standard output
Это я видел, но я и спрашиваю input.txt/output.txt относятся к standard input/output?
нет.
Нет, не относятся
Подскажите как получить задачи? Я слепой наверное на сайте в первый раз, на соревнование зарегистрировался — ссылку на задачи 10 мин найти не могу!
http://mirror.codeforces.com/contest/159
интересно какой проходной балл будет в этот раз
Пока 3800...
такой и остался :)
UPD: все-таки стал несколько ниже.
3500, не?
Какая скорость у тестирующей машины? К примеру, сможет ли сервер сделать 200 * 106 умножений с плавающей запятой за 3 секунды?
Добро пожаловать: http://mirror.codeforces.com/contest/159/customtest
Печаль :( Эти конкурсы помогают осознать насколько ты туповат :( Решил задачу С — 4мя способами, и все не проходят 4 претест по времени :( Про первую вообще молчу, не пойму почему ответ неверен...
прочитайте внимательно условие раз 5 и тогда поймёте почему ответ неверен.
Эти конкурсы, скорее, помогают осознать, что при желании можно многого достичь... Если приложить к этому много усилий.
If someone has the chance to advance to the Round 1 in the qualification round 1, if he join the second qualification contest, whether he can affect others ranking?
Your question has been already answered in Russian in the 1st comment :) If someone has passed qual 1, he can't even register for the qual 2 ))
Thank you:)
Так как соревнование уже закончилось, можно обсуждать задачи. Кто-нибудь может рассказать решение Е?
Я разбивал сначала на группы по цветам (использовал хеши). Затем для каждой группы перебирал все группы, в которых количство кубиков меньше или равно количеству данной и вычислял максимальную длину для этих пар. Быстро вычислить длину можно, построив массив, где x[n] — длина первых n кубиков, отсортированных по убыванию. Претесты по крайней мере прошло :)
Если перебирать для каждой группы группы с весом меньшим, или равным данной, то получается сложность около O(M*M), где M — количество различных цветов. Как вы оптимизировали её, чтобы пройти тест, где все 100 тысяч цветов различны?
P.S. Если я неправильно оценил сложность, напишите пожалуйста и её.
Да, верно, сори, забыл упомянуть про то, что для начала я считал для групп из N кубиков группу с максимальной длиной. И проверял только этот максимум.
То есть в качестве одного из цвета в зебробашне вы брали цвет с максимальным количеством кубиков в нем, а потом перебирали оставшиеся цвета и выбирали из них лучший? Но это же не всегда выгодно.
Не совсем так. Я перебирал все группы по цветам (количество кубиков текущей — n). И для каждой перебирал группы с количеством кубиков m <= n. Тут уже перебирал не все группы, а только одну — с максимальной длиной (высотой) для количества кубиков m.
Таки не прошло такое решение — превышено время на 12 тесте.
Очень простое решение, состоит из некоторых очевидных фактов:
пусть в ответе есть num кубиков цвета c (ну и еще какой-нибудь цвет). Утверждение: эти самые num кубиков максимальные из всех с цветом c.
выпишем тройки следующего вида (sum, num, c), означающие, что если мы возьмем num кубиков цвета c, то максимальная сумма равна sum. Утверждение: количество таких троек равно O(n), а даже ровно n.
Сгруппируем все эти тройки по величине num. Утверждение: для фиксированного num из всего множества троек с этим num нам нужно лишь не более двух троек с максимальными sum, то есть два максимума, все остальные бесполезны и мы их выкинем.
Переберем k — сколько мы возьмем кубиков некоторого цвета, тогда другого цвета (не теряя общности) мы должны взять или k или k - 1 штук. Утверждение: раз мы для каждого k оставили не более двух максимумов, то можно перебирать втупую.
Очень простое и короткое решение, реализовать можно за O(n·log(n)).
http://mirror.codeforces.com/contest/159/submission/1337673
А почему обязательно меньше или равно? Можно ведь взять не обязательно все кубики одного цвета, а только n наибольшего размера. Поэтому для каждой группы надо перебирать все остальные.
Я так решал. Допустим C1 — количество кубиков цвета c1, C2 — количество кубиков цвета с2. Если С1<C2, то максимальное высота из цветов c1 и c2 будет получатся если в начале положить самый большой кубик из c2, а потом чередовать c1 и c2, пока не закончятся кубики в c1. Брать кубики надо в порядке убывания их размера. Если C1=C2, то максимальная высота из цветов c1 и c2 — сумма всех кубиков в c1 и c2. Единственное, что т.к. числа большие в задаче — в начале подсчитать возможные высоты кубиков из одного цвета для каждого цвета для первых i(1<=i<=Cn) кубиков и отсортировать кубики в порядке убывания. Не забываем сохранять ссылки на оригинальные данные, т.к. выводить надо в том порядке, в котором дано.
У вас тоже сложность O(M*M), где M — количество различных цветов? Контрпример я привел выше. Все кубики разных цветов, n=100 000, N^2 не влезает в ограничения.
Не прошёл по времени 15 тест. У меня на компьютере при 100000 различных цветов программа работала 10 сек. Я понимал что это долго, но умнее ничего придумать не мог. 4 задачи решены. 5 — провал. Пойду чертежи чертить. Работа не ждёт. Всем успехов!
Я написал тупое ДП.
Для каждого веса отсортируем кубики по убыванию весов. Затем посчитаем максимальный размер башни, который мы получим, если сложим i кубиков данного цвета.
А затем идем по количеству кубиков в половине башни и смотрим, какой максимальный размер мы можем получить. Для этого используем ДП, посчитанное в предыдущем пункте.
Опечатка, наверное вместо "Для каждого веса" надо "Для каждого цвета". А можно поподробнее насчет идем по количеству кубиков в половине башни?
P.S у меня тоже была опечатка) А у вас вроде, второй абзац, первое предложение.
Не нашел, где у меня написано "ка**дж**ого цвета".
Идем по i, где i — количество кубиков одного цвета, составляющих половину нашей башни (условно половину). Тогда, чтобы получить целую башню, нам нужно добавить еще [(i — 1) || i || (i + 1)] кубиков. Среди всех таких значений выбираем максимальное.
Если непонятно, могу еще подробнее объяснить.
Понял, меня смутило слово половина( сразу подумал про бинарку). Я тоже хотел писать такое решение, но оно получалось слишком громоздким. Надо будет выровнять руки на выходных.
Да, решение получилось неэстетичным :)
Главное, чтобы прошло.
Интересно будет посмотреть решение жюри, должно же быть что-то красивое и изящное. Конечно же, если наше высокоуважаемое жюри соизволит опубликовать разбор.
я чуть выше написал свое решение, которое сдал в дорешку. тынц
я не жюри, но мне кажется мое эстетичным
Не знаю, пройдет ли мое решение, но вроде должно.
Сначала группируем кубики по цвету, потом каждую группу сортируем по убыванию размера. Затем просто перебираем пары цветов, и ищем максимальную высоту.
Для башни мы всегда берем все кубики того цвета, кубиков которого меньше, и столько-же, или на единицу больше(если есть) кубиков другого цвета.
Чтобы быстро посчитать суммарную высоту — сохраним в массивах частичные суммы для каждого цвета.
А если все кубики различного цвета? По времени же не пройдёт
Наверное не пройдет, сложность O(M*M), где M -количество различных цветов. Если все цвета будут различны, то вы получите ТЛ. Похоже много кто писал именно так.
Я для каждого кол-ва кубиков считал максимальный и предмаксимальный набор кубиков какого-то цвета и потом смотрел для кол-ва i разные варианты из кубиков другого цвета по i и i+1 кубику( предмаксимальный набор нужен для того чтобы не попасть на один цвет кубиков. В итоге сложность тратится только на сортировку — N*log(N)
Тоже как-то так делала :)
M always will be less than sqrt((10^5)*2)!
E довольно просто решается. Сгруппируем все кубики по цветам, для каждого цвета посортируем кубики по размеру по убыванию. Сами группы посортируем по убыванию размера групп. Заведём глобальный массив MaxSize[] где i-тый элемент это максимальный размер группы (изначально установим все элементы в минус бесконечность. Теперь пройдемся по всем группам по порядку. Пусть мы дошли до группы i. выполним два действия для нее
1) Идём по массиву кубиков в группе и нарасчиваем сумму размеров кубиков в префиксе curSum, пусть сейчас в префиксе j элементов,
2) снова пройдемся по массиву кубиков считая сумму на префиксе и обновляя значения в MaxSize,
MaxSize[j] = max(MaxSize[j], curSum)Вместе с обновлением ответа можно запоминать номера групп для вывода в конце всех использованных кубиков.И решение D пожалуйста
D я решал так: Динамикой для каждой подстроки узнаем, является ли она палиндромом (сохраним это в матрице)
Теперь нужно для каждого палиндрома узнать, сколько палиндромов начинаются позже, чем он кончается, и эти количества просуммировать — это и будет ответ.
Обойдём всю матрицу. Для каждой единичке в матрице нужно к ответу добавить количество единичек строго ниже неё. Это легко сделать, проходя по строкам снизу вверх, на ходу увеличивая количество единичек.
Делал почти также. Только я динамикой считал так: C[i,j] — количество палиндромов между в подстроке [i,j]. Ответом будет сумма всех C[j+1,l] для каждого 1<=i<=l-1; i<=j<=l-1, и чтобы C[i,j] — было палиндромом.
Тут близко к динамическому программированию. x[n] — количество полиндромов левее n (включая), y[n] — правее. Тогда ответом будет Sum((x[i] — x[i — 1]) * y[i + 1]).
За O(N^2) я нашел все палиндромы. Пусть l[i] — количество палиндромов, начинающихся с символа i, а r[i] — количество палиндромов, заканчивающихся символом i.
Тогда для каждого i пройдем по всем j, лежащим правее, к ответу каждый раз прибавляем r[i] * l[j].
Сорри, не прочитал внимательно.
Аналогичное решение
Я не заметил, что размер строки до 2000, поэтому моё решение имеет сложность N Log N и слишком длинное и запутанное чтобы поместиться в этом комментарии.
Решение в лоб за N^3 тоже заходило. :D 1317753
Ну это значит, что тесты плохие... Потому что, например, за строчке из 2000 букв 'a' это решение должно получать TL...
UPD. Хотя TL 3 секунды, может такое решение и проходит... Но вообще, конечно, это странно. Мне кажется, что авторы подразумевали другое решение :)
А разбор квалификаций будет?
GREAT PROBLEMS...
When will system testing start?
Started already :)
мне одному кажется,что слишком много решений A упало?
ага, настораживает. моё пока не протестило
Если кто знает, скажите, на чем она падает.
Возможно что там пользователи могут писать более 1 сообщения одному и тому же пользователю(ибо в условии не написано что так нельзя делать), и поэтому у некоторых они выводяться несколько раз... Но это только предположение.
package.zaic предложил заваливающий тест:
хмм и какой тут ответ предполагается, пользователь b ответил на 1е или на 2е сообщение??
ответ 1 a b
Пользователь b ответил на первое сообщение.
Может, не все учли, что если t2 — t1 == 0, то это не считается ответом на сообщение?
Не учли, что надо смотреть не только последнее сообщение.
Я вообще перебирал все сообщения, которые входили в данный отрезок времени.
Я вообще перебирал все сообщения, и для каждого условие проверял. Когда ограничения маленькие, лучше не выпендриваться.
Я всё вышесказанное учитывал, но выпендрился в другом: использовал
res.resize(unique(res.begin(),res.end())-res.begin);не отсортировав массив. И прошёл только с С и D. :)UPD: в А,B,E исправил 1 строчку и прошли все. facepalm\
Это явно не из разряда мелких подвохов ;)
К счастью, это было в претестах :)
Значит, не угадала :)
А как в задаче С можна использовать следующий факт "изначально некий пользователь зарегистрировался под именем t, где t представляет собой строку s, записанную k раз подряд"? Это упрощает решение? Я придумал решение только для произвольной строки.
Да, можно посчитать включения всех символов в исходной строке и продублировать на все отрезки (завести массив), а потом в процессе поиска отрезка, в котором нужно исключить символ, проходить по этому массиву, а не по всей строке.
То же самое можно сделать и с обычной строкой, только не дублируя.
Я наверное не так выразился, у меня такое же решение, как и у lama
Конечно, упрощает.
Храним K строк, для каждой строки храним колличество каждого символа в ней. Теперь мы можем удалять и искать символ за O(K+Base_len).
Можно не удалять, быстрее получается. я просто затирал решеткой
Данное решение проходит в любом случае
Ну как, удаление асимптотику не ухудшит, плюс то же самое время вы потратите на выводе, чтобы фильтровать несуществующие символы.
Я сделал вставку и удаление за log(K*Base_len). Наверное усложнил задачу)
Еще посмотрим, моё решение еще не зашло :)
UPD: зашло, 140 мс, видимо, действительно не стоило :)
Хм.. а можно вопрос, как? А то я написал за я log^2. Оно, конечно, зашло, но что-то стыдно :)
log^2 — это бинпоиск индекса по дереву отрезков (RSQ)?
Он самый, да.
Небольшая модификация RSQ. Только не нужен бинпоиск, RSQ может вернуть индекс i, для которого сумма на промежутке 0..i равна искомой.
был более чем уверен что поиск каждого символа за О(K+|s|) не пройдет по времени при максимальном N. В итоге пока дошла идея с бинпоиском по дереву отрезков контест уже закончился:).
Ничего подобного, заходит. 1326798
Пугал тест вида
где О(38*1e6)>3с
Но произвольную строку можна разбить на отрезки и поступать также. Или нет?
В данном случае нужно посчитать включения только один раз и только для одного отрезка (причем маленького), а в произвольной строке нужно их считать для каждого отдельно.
Не вижу никаких причин, почему нельзя :)
Просто тут авторы задачи как бы намекают нам на такое решение.
Можно ли будет писать Vk Cup 1 вне конкурса, если не прошел в него?
Да, это будет засчитано как обычный рейтинговый раунд.
Есть вопрос. Если так делать будет можно, то будут ли те кто пишут как обычный рейтинговый раунд отдельным списком? Потому что если видеть всех вместе, будет невозможно оценить своё место во время соревнования — если какая-то часть просто пропадёт из официальной таблицы.
Обычно те, кто пишут вне конкурса:
Why I can't see other participants' submissions?
Системное тестирование закончилось. Проходной балл заметно понизился.
Когда откроется дорешивание? UPD: Открылось.
Буду стараться больше не решать в ночью :\
Это нормально, что по D зашло решение за куб? http://mirror.codeforces.com/contest/159/submission/1335129
Нормально, ТЛ ведь 3 секунды. Вот был бы 2 секунды, как обычно, не прошло бы это решение.
Спасибо, я понял) Я имею в виду то, что авторы видимо лажанули. Решение за куб вряд ли по их задумке должно было проходить, поскольку, во-первых, оно совсем не тянет на задачу D, а во-вторых, есть решение за квадрат. Могли бы ограничение сделать, например, 5000 вместо 2000. Тогда даже при аккуратной реализации куб не пропихивался бы. А еще, в задаче D первой квалификации мое решение, в котором была очень существенная ошибка, упало лишь на самом последнем тесте. Как-то все это несерьезно, по-моему.
Какая разница на каком тесте упало? Большинство тестов — это рандом, поэтому решение, если оно неправильное, практически равновероятно может упасть на любом из них, хоть на первом после претестов, хоть на самом последнем.
Странно то, что совсем лажовое решение упало только на одном тесте из 39. Еще немного — и оно бы прошло, тесты-то рандомные
Вы уверены, что тест последний? Если где-то упало — дальше не проверяется
Да. Вот неправильное решение http://mirror.codeforces.com/contest/158/submission/1283119 вот правильное http://mirror.codeforces.com/contest/158/submission/1291862
ОК, просто некоторые путают:)
Из мыслей по C. Есть тест:
2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
20000
200000 a
199999 a
199998 a
...
но нет теста:
2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
20000
1 a
1 a
1 a
...
или я его не видел. Думаю некоторые бы на этом тесте свалились бы. Например, это.
Кто-нибудь может выложить тест 4 к задаче С ? Спасибо.
Выкладываются ли полные тесты? интересен А-10 и С-4.
Просто посмотрите в свои отправки — там будет полный лог тестирования и собственно, тесты.
Как нужно было решать A? B, C и D прошли, а A свалилась с WA 14
Я решал с очередью, хотя это не обязательно. Берем сообщение и перебираем уже готовый список друзей, если этих двоих (отправителя и получателя сообщения) в списке нет, то проверяем все сообщения в диапазоне t(сообщения)+1...t(сообщения)+d (сообщения отсортированы), каждое новое сообщение проверяем, является ли оно ответом. Если не нашли, то не нашли, а если нашли, то добавляем друзей в список и идем дальше. Поскольку я использовал очередь, я просто вырезал два сообщения, если одно из них являлось ответом на другое.
С такими смешными ограничениями перебор за квадрат выглядел прикольно)
Быстро придумывается, легко пишется, вероятность ошибки — минимальная, почему бы и не написать.
Абсолютно солидарен :)
Переберем все пары. Если одно из них от a к b, другое от b к a и разница во времени ровно 1 по модулю — добавляем пару в ответ. Вроде должно заходить.
И так заходит, правда уточнение : разница <=d и Accepted =)
В условии указано: Входные данные ... Гарантируется, что строки журнала заданы в порядке неубывания ti, и никакой пользователь не присылал сообщения самому себе.
Никто не знает, можно ли апеллировать? 1)WA 14 возникает, если брать только последнюю беседу, которая по условию задачи должна быть с самым большим ti. 2)Полное решение, которое смотрит все переписки и все предыдущие ti (и стреди них находятся ti, которые ближе за последний)
Я дорешивал задачу с учетом 2) на Полное решение, и снова завалился если 1) на 14 с WA.
Если не апелляция, то хоть посмотреть на тест да исправить условие, если нужно. Хотелось бы взглянуть на 14 тест.
3 1
a b 1
a b 2
b a 2
Спасибо большое!!!)
Раунд рейтинговый?
Нет
Почему он должен быть рейтинговым, с учетом того, что можно было тестировать свои решения целые сутки? Нет, конечно, нерейтинговый.
А разве я утверждал, что он должен быть рейтинговым?
Нет, но вопрос и правда странный.
The testcases of Problem C is very weak. Some solutions (just like this) with time complexity O(2000 * 100 * 20000) passed. It could be easily hacked to TLE by the "reversed" test#29.
Codeforce conspiracy =)
So that means I wasted time implementing Segment Trees. Nice!
Now the round has ended and the rules can't be changed, but for the next time it would be nice to see how can contestants create test cases (as we can't hack solutions we can find a way to add contestant-created test cases), of course it's impossible to have one test case per contestant per problem because there are lots of contestants and testing will never end if that happens but you can try to figure out how to do it so you prevent weak tests. Of course I don't think that problem setters want to create weak test cases, but it's better if instead of a few people, everyone creates test cases. I don't know how it works here in Codeforces but in TopCoder I think that successful challenges are added as system tests.
AFAIK, some successful hacks are added as system tests on Codeforces.
Очень хотел бы поучаствовать, как зарегистрироваться?
Раунд закончился 6 часов назад. Ты опоздал.
Ааа, точно. Спасибо. А когда еще поучаствовать можно, мне очень нравится.
В следующем году, возможно.
Вне конкурса можно в этом году в раундах участвовать.
Еще, нескоро. Обидно. Мне интернет только в этом году подключили, ну ничего — подожду :)
А я вижу ты хорошо решаешь :) Умный? :)
Умный — tourist , он и решает хорошо. А мне как повезет.
И вообще все такие вопросы лучше в личке обсуждать, чтобы пост не засирать комментами.
В личку? А это как? И что за минусы в углу?
Минусы за то, что ты всех задолбал своими комментами не к месту.
Зайди в профиль любого человека, там есть "Переписка" == личные сообщения == личка.
Ты всегда такой грубый? :(
По настроению :)
Извини за грубость, я просто констатировал факт.
Поучаствовать можно достаточно часто,несколько раз в месяц, но только фофан(и для рейтинга)
This competition was better than the previous, thanks to problem-setter.
is that correct, it is better!!!
Thanks to all who maintain this excellent site.
Do we have to register for Round 1 or the advancers are automatically registered?
Okay, 50 minutes until registrations begin.
Мы удалили явных читеров. Это как? как тут можно читерить?
Например, пройти претесты с одного аккаунта, а сдать с другого, чтобы не было штрафных попыток. Или списать решение с другого человека.
Первое понял, про аккаунты, а вот второе, как можно списать?
Какой-то вредный комментарий
Охренеть, понятно.
Can people who didn't make Round 1 or were not eligible because of age still participate unofficially in the real Round 1 (as a rated contest)? It's not letting me register.
It should be possible.
There are some out of competition registrants
I just registered...It will be like a normal rated round for the out — of — competition people...Try again...Maybe the server was not prepared then...
Будет ли Раунд 1 рейтинговым для тех, кто прошел в него?
Думаю, что скорее будет, чем нет — как TopCoder Open. Но хочется услышать официальное мнение.
ЯОпен — пример поближе
Будет. Кроме того он будет рейтинговым и для участников вне чемпионата.
My score in Qualifacation Round 2 is 4950. Why can't I advance to Round 1. Please tell me why?
Answered in personal talks (messages).
А разбор этого раунда будет?
Нет, для большинства задач в комментариях очень подробно написали идеи решений. Для оставшихся идеи понятны из исходных кодов решений, они доступны для просмотра.
How did you find the cheaters? > admin
In the "Go to" box in VK Cup 2012 page, you misspelt "Qualifacation Round 1 Results" and "Qualifacation Round 2 Results", they should be "Qualification".
Для участников в не конкурса места будут показывать со всеми учасниками илиже только с такимиже в не конкурса?
см. выше
Hey, I can't submit for the contest VK Round 1 even though I'm unofficially registered. Are we just not allowed?