Всем привет!
Надеюсь, вы уже закончили отмечать Новый год или готовы сделать небольшой перерыв, чтобы принять участие в юбилейном Codeforces Round #100. Раунд состоится 4-го января в 19:00 (Московское время). Это будет общее соревнование для участников обоих дивизионов на одном и том же комплекте из 6 задач. Первые 100 участников по результатам соревнования получат призовые футболки.
Разбалловка: 500-1000-1500-2000-2500-3000
Как вы уже догадались, в качестве автора задач выступаю я. Неоценимую помощь в подготовке (и даже немного в придумывании) задач оказал Артем Рахов (RAD) и в переводе условий на английский язык - Мария Белова (Delinur).
Под воздействием праздничного настроения условия задач получились про то, как различные персонажи встречали Новый год. Все персонажи и события вымышленные, любые совпадения имен прошу считать случайными :)
Соревнование завершено. От лица команды Codeforces и от себя лично хочу поблагодарить всех, кто принял участие в крупнейшем раунде в истории Codeforces! К нашему удивлению, 100-е место поделили два участника: pooya_ и Timur_Sitdikov. Конечно же, призовые футболки получат они оба, а также все те, кто оказался выше. Призерам будут разосланы специальные письма по email.
Поздравляем победителей:
1. Egor
3. tourist
4. Petr
5. RAVEman
6. e-maxx
7. hos.lyric
8. dzhulgakov
9. Coder
10. SergeyRogulenko
В каждой задачке по своему JKeeJ1e30. JKeeJ1e3O, JKeeJle30, JKeJ1e30... Извиняюсь, если уже неактуально.
4е января, имейте совесть... =)
Ух ты!..
Тогда я, так как всё равно решать не буду, в продолжение новогодней эпопеи постараюсь (но не обещаю) к каждой задачке в процессе контеста написать краткое стихотворное сопровождение, если Вы, natalia, конечно, против этого не будете возражать... :)
Раньше большинство раундов начиналось в 6 вечера (по местному), и я успевал. Теперь с Россией еще +1 час разницы, в итоге теперь в 5, и нужно уже думать
P.s. это не нытье, просто мысли в слух
Медведев... Хе-хе... ;-)
Он конечно отличился, оставив часы переведёнными "не в ту сторону", но если задуматься об истоках, то можно обнаружить, что одним из идеологов "декретного времени" в России (благодаря которому разница с астрономическим временем аж 2 часа теперь, а не 1) был не кто иной, как знакомый (и горячо уважаемый) всем нам Яков Перельман. Упоминание об этом можно найти в биографических статьях, в т.ч. в википедии...
You are so sure. We will know it after contest.
twothree accounts,winning awaytwothree t-shirts."-piyush006
Of course, Codeforces cannot make a decision that makes everybody happy. So let's just forget the debate and enjoy the contest!
I don't think this is legal !
>> Добрый день, alexei1998.
>> Приносим извинения за повторную рассылку ...
Я немного озадачен...
upd; первое письмо было правильно адресовано, это только в повторной рассылке
интересно, остальные 5000 тоже получили письмо на имя alexei1998? :)
Хм, сервер тоже шутит)
Попробуй пробел в конце имени убрать.Опоздал.
Недосмотрел... Я верю, что 100-й контест побьет и вторую квалификацию, остается только ждать)
UPD: Уже и досматривать ничего не надо)
Упс. проглядел в теме.
А тут ЗАПИСИ, которые, к сожалению в данном случае, сохраняются.
З.Ы. 2821!
Пацаны, а D жадно решается?
Да, по крайней мере проходит систесты
For A, I set EPSILON as 1e-10 and I keep failining. After I changed to 1e-8 I passed the pretest ...
Argh why D=
Какова вероятность, что используя число π взятое как
решение пройдет систесты? Может, кто сможет завалить такое решение? Я долго пытался...не получилось =(
UPD: Действительно...не прошло систесты)
Там ~107 вариантов входных данных: такое решение несложно сравнить с правильным
10 72 17
Уважаемые разработчики сайта, очень прошу сделать перенаправление на дальнейшую регистрацию в контесте после того, как регистрация на контест отправляет тебя логиниться, второй раз уже с контестом из-за этого пролетаю, забыв повторно нажать на регистрацию (
Это, конечно, моя ошибка, но все же...
открытокзадач 2 4 3 1 6 5мой 4 3 2 1 6 5 =)
Задача меня задела (в хорошем смысле слове) окончательно, поэтому впервые сделал отправку на этой платформе.
Но пишу не поэтому, а по той причине, что можно сдать и без eps.
Вот полное решение без использования eps.
Автору задачи - отдельный респект!
Обидно только то что только в ней.
Ээээ, я лох года!
(122 место на NEERC, если что)
еще по своей глупости у меня упала С, и в итоге меня сейчас в скайпе всякие троллят кто выше с простыми задачами))
У кого рука поднялась на такое действие?!
Вы считаете, что Д была легкая? И что?
"Ой, див2 сдали Д(". И что?
У них там 700+ место (с одной-то Д), вам-то что?!
Все верно, задача Д. Специально на нервишки.
Все, кому надо, написали ее сразу и даже не заикнулись о ней.
Если бы задача D была первой, то скорее всего людей пославших хоть какое-то решение было бы больше (а так на 1000 меньше зарегестрированных). Все-таки А и B новичков ставят в тупик. А с D ведь по сути, почти каждый участник знает, что выгоднее сдавать сначала задачи, которые быстрее решишь (причем там даже сортировку за квадрат можно писать).
Даже за куб. И даже больше :) Тот факт, что N = 100 заставил меня подумать лишние 5 минут, а ощущение подвоха не покидало меня до конца контеста :) D ж все-таки... Поддерживаю ораторов свыше.
Я отвечу, так как частично знаком с задачами и считаю большую часть заявлений необоснованными. Автор может расстроиться, а это ни к чему. Итак, проделана большая работа по подготовке раунда. Предложены интересные задачи, которые отлично соответствовали задумке — сделать раунд интересным для всех. На том же самом TopCoder регулярно оказывается, то участник довольно быстро решает 250 и не может придумать 500, таким образом контест для него состоит из 1.25 задачи и идет минут 20. Задачи этого раунда оказались такими, что практически каждый нашел задачки по зубам, было из чего выбрать и над чем задуматься. Кажется, только задача А могла бы оказаться чуть проще, было бы повеселее участникам Div.2. Раунд был подготовлен высококлассно. Малое количество вопросов, отсутствие кларификейшнов, каких-либо правок и реджаджей — существенный показатель. Например, последние сборы в Петрозаводске, где я был, содержали ровно 1 такой контест. Бывалые авторы задач могут оценить сложность подготовки некоторых задач, например, тестов к задаче F (кроме того по этой задаче было написано 14 вариантов различных правильных и неправильных решений). Во многих задачах были нетривиальные чекеры.
Касательно сложности задач — да, здесь не все гладко. В самом деле, задачи B-D оказались примерно равными по сложности. Замечу, что все участвующие в подготовке раунда придумали динамическое решение в D. Да, Наташа указывала на решение с сортировкой, но мы были уверены, что большая часть участников напишет именно ДП и некоторые участники напишут сортировку. В задаче С надо было что-то сообразить, в то время как в В просто реализовать. Кстати, по С довольно многие не справились с решением (включая вас, Павел). Отсюда такая расстановка. Кстати отмечу, что все время контеста B и C шли довольно близко по количеству решений и, вероятно, правильная стратегия в таком случае была ознакомиться с обеими задачами (или даже начать с C). Задачи E и F тоже по факту оказались близки по сложности, у авторов по F основным решением было более сложное, чем то, что предложили авторы (если не прав, Наташа поправит).
Отмечу, что оценка сложности задач дело нетривиальное. В среднем у нас получается расставлять задачи по сложности, однако иногда это не так. В любом случае, это не повод обвинять авторов в том, что им на что-то наплевать и т.п. Это был пример интересного, хорошо соответствующего случаю, качественно подготовленного контеста с проблемами в оценках сложности задач. Я считаю, что Наташа хорошо справилась с подготовкой, побольше бы нам таких авторов.
В качестве способа избежать таких ситуаций в будущем есть два направления. Первое — мы всегда рады опытным участникам, кто берется тестировать раунды. Иногда они есть, иногда их нет. Если у вас или кого-то еще есть такое желание и возможность, пишите RAD-у. Второй вариант — можно попробовать провести раунд с одинаковой стоимостью задач, в котором задачи расположены случайным образом (или по возрастанию предполагаемой сложности, но с равными стоимостями).
И да, конечно отмечу, что критика обычно бывает от людей, кто не делал раундов сам.
Плюс у нас есть немало легких задач для div-2-контестов, но они все свеченные локально, а поэтому раунды на них, наверное, провести не получится.
По моим наблюдениям, ваши реплики о том, как плохо был составлен/проведен раунд, практически всегда соответствуют тем раундам, которые изменили ваш рейтинг не в лучшую сторону.
Вообще, все были на контесте в равных условиях. Позднее решение D - это проблема участников, которые читают задачи только в порядке азбуки
Ну, большинство так и решает. Но это не отменяет того, что никто никому не мешал читать условия в оптимальном порядке ( так же, как и смотреть, что все сдают D).
Сложность-вещь субъективная, как уже выяснили выше, и в правилах контеста нигде не обещается выстраивание задач в "порядке возрастания сложности"(в отличие от выстраивания по баллам)
Прикольный пример, спасибо. Тем не менее, такое случается редко => можно считать, что вероятность мала.
Успел пройти претесты, заблокировать и взломать другое решение, прежде чем дошло.
I liked the problems, but the points didn't seem right to me. E is harder than F and D is the easiest in the set.
Если на всех - все об этом буду знать почти сразу - профита никакого.
Любопытно, что на TC нечто похожее есть - контесты начинаются не в :00 , а в :02
Это единственная комната, где количество Accepted куда меньше кол-ва реальных участников?
Возможно, распределение по комнатам с учётом рейтинга помогло бы выровнять.
Можно куда-нибудь выгрузить 12-й тест по С?
UPD: сказали, что rand тест из 10^k чисел не больше 5.
Можно попробовать ловить на тесте
15
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4
А мне 10.
About task E:
What to do with C(N,K)? It seems I only precomputed until N <= 5000, K <= 5000.
But you need N <= 10^6, K <= 5000. Precomputing them all shouldn't pass, while the modulo isn't always prime number.
Which you can calculate as:
(N-K+1)*(N-K+2)*...*(N-1)*N
Maximum of K numbers will be there, and K is small.
In one place you need:
((N! / (K! * (N-K)!)) - 1) * K!
You can still transform it to neccesary form:
(N! / (N-K)!) - K!
I understood why the system test was SO FAST!
I think, admin did the final tests just after the submission and not after the contest.
(ctrl + click to see the system test timing)(Give me plus now!)
Why did Alex. send card 1 to 2 and to 3 and not to 4?
"In other words, so that as a result of applying two Alexander's rules, each friend receives the card that is preferred for him as much as possible."
does the "him" there refer to "Alexander" or to "each friend?"
I see nowhere in the problem description where the friends' preferences are considered. The only use of preference in the rules is "Alexander always chooses one that Alexander himself likes most."
1) Alexander receives the first card.
Можно деревом отрезков.
В листьях - степени простых чисел.
В узлах - произведение по модулю.
Для умножения или деления раскладываем множитель/делитель на простые и делаем запросы на изменение дерева отрезков.
Ответ всегда в корне.
Чуть не забыл: сначала придумаем формулу пересчёта Cnk + 1, если известно Cnk.
На самом деле в нашем случае всё просто: m фиксировано, а k не бывает больше 5000, так что всё считается например за 50002 (пересчитываем последовательно для k = 1, ..., 5000, например, см. решение RAVEman).
Firefox/9.0 build x86_64-unknown-linux-gnu;
Shockwave Flash 11.1 r102 (nswrapper_32_64.libflashplayer.so);
Linux 3.1.6-1.fc16.x86_64.
Я конечно понимаю, что flash под линукс - набор костылей, а под 64-битный линукс - набор костылей в квадрате, так что никаких жалоб/перетензий у меня нет :) Ну раз уж хочется разобраться - можно попробовать. А есть какой-нибудь способ открывать решения флешовым просмотрщиком не во время контеста?
Все можно было делать деревом отрезков, например (вообще без stl, кроме sort)
=========расширим============
to: , возможно вам будет полезно знать, что set на 106 элементов падает (ну то есть если в него пихнуть 106, а если еще и лонги или пары, вообще застрелится), по крайней мере, сколько я не пытался его использовать при таких ограничения, никогда не проходило
P.S. упс, почему то ты фиолетовый...
========================
ну если ты как раз тот, "другой", то тебе вдвойне полезно будет знать)
Я понимаю, когда какой-нибудь красный так делает, но синие-зеленые... они наверняка даже не знают, как ту же кучу или sort без stl написать
Ну дык, на контесте цель - не знания показать, а занять место выше, для чего нужно делать все быстро, используя структуры из коробки.
Буэ, капитанить приходится.
Я кстати без понятия, как кучу писать)
Многие потом привыкают к map и set, и валятся по TL (стандартный аргумент)
Я опознал всех людей, которые фигурировали в легендах.Rank 102...
Feel a little sad...
I would appreciate it very much if you can send one more T-shirt!
http://codeforces.me/profile/MEGAKILLER
+349 рекорд?
И решение прошло финальные тесты!
Даже ошибка в 1 символ в первой задаче после этого выглядит не таким эпичным фейлом.
how did you guys got hint of using float instead of double ?
It is useful to remember this while doing double comparison.
блин, в А такой глупый фэйл: думал без эпсилона сравнение будет норм... хренушки(
я наверное один такой
Смотря как делали. В некоторых решениях не нужно использовать eps.
У одного чела решение в задаче А реагировало на точность пи...
Как бы то ни было, я занял тут 308 место, а если взять сортированный список участников, я там 363-й. А некоторые из тех, что выше меня в этом списке, еще и не участвовали.
И я получил +67 рейтинга. Как то многовато, я ожидал +eps или минус.
1) из Д-1 больше народу
2) из Д-2 много народу и они хоть и незначительно, но это самое место понижают.
1) из Д-1 больше народу
не смешите меня, в Д-1 почти всегда раза в 2-3 меньше чем в Д-2
I used it, too. Be careful with eps and n=1.
Ты умеешь по-японски? Тогда уговаривай hos.lyric. dzhulgakov'а, так и быть, беру на себя,
так какоскiльки говорити украiнською мовою я умiюя просто забыл про смену хэндлов)
забавно,что в задаче Д что там говориться про того кто сначала читает задачи и сортирует по времени за которое сделает, и тут в выгрыше оказались иммено такие люди?
две посылки отличаются только эпсилоном.
http://codeforces.me/contest/140/submission/1000128 10^-7
http://codeforces.me/contest/140/submission/1011735 10^-9
На будущие какой надо выбирать эпсилон чтобы не было проблем?
Можно ли например брать всегда 10^-15?
Ну представьте две модификации Вашей программы, исходную:
и другую:
Мы не изменяя само eps, изменяем его влияние в 100 раз... Поэтому если вы считаете что для значений порядка 1 нормальный eps это 1e-7, то для значений порядка 0.01 нормальный eps должен быть на два порядка меньше, естественно... %)
Более подробно разбираться не готов, т.к. тут нужно обмозговывать крутизну изменения арксинуса вблизи 1, я думаю... ;-)
Может в ближайшем будущем напишу пост почему не 1e-9, а меньше.
В двух словах при операциях с около maxint 1e-9 is not enough.
Если заменить 1e-9 на 1e-11, то все старые задачи, вроде бы, проходят, а ещё добавляются новые, т.е. он как бы более универсальный.
Но вообще, по-хорошему, всегда надо думать, какая погрешность нужна, как говорит Egor. Осталость научиться так думать)
То ли на тимусе, то ли к комментам к задачам из ПТЗ как-то писали, что проходил только некий диапазон eps, что-то между 1e-10 - 1e-13. Большие или меньшие значения вызывали WA.
привет, Вань! да вообще для каждой задачи нужно выбирать свой эпсилон... зависит от того насколько много геометрии, тригонометрических ф-й, корней...
ну я обычно беру 1e-9, пока не обжёгся... по мойму, 1e-15 брать не стоит, это все равно что без эпсилона-настолько он мал
P.S. хотя судя по тому, что я даже не подумал использовать eps в этой задаче, я вообще не умею его использовать
Please give me '+' , I don't know why my Contribution is -12 !
Когда примерно призерам вышлют специальные письма по email?
UPD: Пришло.