Здравствуйте!
Приглашаю Вас принять участие в сегодняшнем раунде, который кстати, будет последней возможностью на Codeforces потренироваться перед VK Cup, так что не упустите свой шанс =) Надеюсь, каждый найдет интересные для него задачи, у Вас не наступит взаимонепонимание с условиями и Ваши решения будут находится в полной гармонии с нашими тестами =)
Автор сегодняшнего раунда я, Валерий Самойлов, выпускник СПбГУ. Большое спасибо за помощь в подготовке задач Артёму Рахову (RAD) и Геральду Агапову (Gerald) (которому, кстати, был посвещён мой первый раунд: Codeforces Beta Round 79 (Div. 1 Only)) =)
Так же большое спасибо Марии Беловой за перевод условий и Александру Куприну (Alex_KPR) за вычитку условий и картинку =)
Обратите внимание, что в первом дивизионе разбалловка задач сегодня необычная:
500 — 1000 — 1500 — 2500 — 2500
Во втором дивизионе же такая же, как всегда:
500 — 1000 — 1500 — 2000 — 2500
Всем удачи!
По техническим причинам раунд отложен на полчаса. Регистрация закончится в 21:25.
Поздравляем победителей!
Первый дивизион:
Второй дивизион:
Опубликован полный разбор на русском.
раунды вроде уже давно не бета :)
спасибо =)
кто-то накаркал =)
Обратите внимание, что в первом дивизионе разбалловка задач сегодня необычная
Кто может сходу вспомнить раунд, в котором разбалловка была обычной?
прошлый?
Ну просто, если этого не сказано, у участников может быть ощущение, что обычная.
первый раз буду участвовать. что-то не справляется ваш сервер с наплывом народа похоже. а до начала раунда еще 50 минут. Хочу посмотреть страницу О языках программирования и технических аспектах а там сплошное Unable to parse markup [type=CF_HTML]
Это отключено специально, чтобы не было никаких сбоев. Чем меньше нагрузка на сервер, тем лучше — меньше задержек на обработку лишних запросов во время раунда, и т.п.
Вообще удивительно. Почему нельзя кэшировать содержимое хотя бы по минимуму? Тут же очевидно можно что угодно запихать в кэш: содержимое постов по отдельности, страницы целиком. Может я, конечно, не знаю каких тонкостей реализации ресурса, но вроде никаких препятствий к тому быть не должно.
Ну или на крайняк ставить во время контеста какую плашечку, чтобы хотя бы выглядело поприличнее.
Честно говоря, у меня давно крутится мнение в голове, что для администрации CF приоритет — контесты, т.е. чтобы во время них не было сбоев, поэтому они не особо заморачиваются о работе разделов сайта, не относящихся непосредственно к контесту во время соревнования. По сути это правильно.
Но если уж говорим о том, что CodeForces больше, чем просто online judge, т.е. почти социальная сеть, то вот так вот перекрывать кислород во всех разделах ИМХО не правильно.
Можно посмотреть вот так
I'm having problems when viewing task A and D for CF109 div 1 round. (http://codeforces.com/contest/154/problem/A) (http://codeforces.com/contest/154/problem/D) Error is: Unable to parse markup [type=CF_TEX]
Same here too: http://codeforces.com/blog/entry/456 but error is: Unable to parse markup [type=CF_HTML]
Anyone experiencing same problem?
all is not work during raiting contest, now this round almost started.
MGIMO finish :) Sorry, I couldn't resist.
sorrywut?
MGIMO finished
Seems CF_TEX problem is fixed. CF_HTML not yet, but i don't think it affects the problem set.
Перенос на 10 минут вперёд?
я тоже это вижу
Вообще веселуха. Я об этом только узнал, когда меня страница попыталась редиректнуть на контест, но у неё не вышло.
А я вот только приготовился нажать кнопку "OK" :)
перенос =(
10 more minutes to practise !!!
for warm up ;)
It has been delayed for 10 minutes?
Looks like yes.
20 minutes more :( I have to work :'(
All right~ Now I have plenty of time for a cup of coffee~ It is 1:12 in the morning here... Quiet night~ :)
Впервые рад переносу... заговорился по телефону и совсем мог пропустить начало...
У меня 5 минут было Bad gateway nginx.
Any who know ¿? is wrong with Codeforces Round #110 ???
Any who know ¿? is wrong with Codeforces Round #110 ???
ещё 20..
еще на 20 минут(
а почему???
delay += 20 ;
Еще на 20 минут перенос...
Как разрегистрироваться, а то совсем уже поздно
Просто ничего не сабмитьте. Рейтинг не будет пересчитан
Нажать на крестик рядом с собой в списке зарегистрировавшихся.
Это в принципе необязательно — если не будешь участвовать, на рейтинг не повлияет.
Зачем? Можно же просто не отправлять ничего, тогда считается, что в раунде участник не участвовал.
Да уж, это точно.
Если не ошибаюсь, то если ничего не отправишь — на рейтинг не повлияет
Просто не посылайте решения в систему и раунд не будет засчитан Вам как рейтинговый
What's going on?
contest is started at 9:30?? 30 minutes delay?
WHY???????
Из-за того, что кто то с самого начала не очень хорошо подготовил раунд, страдает всё сообщество. Хоть регистрацию откройте минут на десять ещё, может кто то не успел.
да, а у кого-то отбой в "общаге" в 23:00))
Ну, по непостоянной работе сайта в эти 20 минут, я бы предположил, что это технические проблемы, а не доделывание задач в последние -30 минут.
+30 minutes.... WTF??? :|
offf. couldn't you tell this earlier?
I can confirm eudanip is a very busy person.
Откройте регистрацию!! все равно контест перенесли. Я знаю пару людей, которые не успели.
чувствую веселый будет раунд
Ага, если еще будет с такими темпами
I guess that next delay is 30 minutes. (10 -> 20 -> 30)
10 -> 20 -> 40?
no delay sequence is Geometric progression. so: (10 -> 20 -> 40)
Такое чувство что параллельно проходит соревнование вида "кто быстрее отпишется о переносе".
Блин, ребята по мойму это уже троллингом попахивает=)
Ребят, вы че?
Полчаса — это уже перебор.
Конечно перебор, лучше прямо сейчас запустить контест, всё упадет и раунд будет нерейтинговым, нам-то что.
может уж в 22:00 начнем, чего уж там?
может, хотя бы регистрацию откроете? а то когда не зареган и переносят — вдвойне бесит
Нет, поздно это. Лучше на завтра перенести, чего уж там.
И регу открыли, жизнь прекрасна...
смотрите, а то перенесут и не будет нам ночного драйва!
All the Chinese will cry...
we are all going to die :)
Japanese and similar time zones too.
I can't lauch when contest finish... I will cry too :)
So sleepy......It's 1:15 AM in China...
I agree with you!!
=_=
It's a trap!
now is 4:00+ testing do not start???
мы 3 дня ждали, а что теперь и полчаса не можем?!
Sorry for delay, some technical problems around "Unable to parse" forced to move the start.
Seems like it was unable to parse problem statement? :-)
I just thought because it's a Feb 29th round =)
Будет время попить чай)
started a new bbt episode!
Теперь раунд начнется как раз по окончанию SPb IFMO Training...
Как решать C Div1/E Div 2 ?
Ну, если посмотреть, то станет понятно, что на самом деле операции разрешены не только между соседними. к пример, из строки azc легко можно получить строку cza. Тогда, переформулируем задачу: У нас есть какая-то сумма, которую мы можем набрать len(строка) слагаемыми от 0 до 26. Считаем ее, отнимаем 1, выводим как ответ. Чтобы успеть тесты, делаем прекалк dp(sum, count), и за O(len) отвечаем на запрос.
Заменим каждую букву на число — а=1...z=26. Посчитаем сумму строки S и найдем количество способов представить эту сумму в виде слагаемых от 1 до 26, при этом количество слагаемых должно быть равно длине строки. Ну и не забываем отнять 1, ибо искомые строки не должны совпадать с исходной. Такое решение приходит в голову, когда замечаешь, что оба вида изменений не меняют нашу сумму, то есть имеем инвариант.
Блин 5 секунд не хватило=(((Обидно...
Та же фигня :(
Как решалась D div 2?
Я так решал: Пусть c[i] — сколько человек сказали, что убийца i, d[i] — сколько человек сказали, что i не убийца и s — сколько человек сказали, что кто-то не убийца. Сколько человек говорят правду, если убийца i? Это будет c[i] + s — d[i]. Идём и смотрим кто может быть убийцей:
если может быть 1 человек, тогда идём по всем и смотря что сказал человек выводим для него вердикт,
если могли быть больше 1 человека, то тоже идём по людям и по случаям решаем что сказал человек.
Problem D (Suspects) was interesting.I got WA on pretest 2 i.e. 3 2 -1 -2 -3 Can somebody please tell why the answer cannot be Lie Truth Truth
It definitely can, but not necessary. We can't assume for all of them do they tell truth or lie.
Thanks.I had misread the question ....Missed the part "you have to be absolutely sure..."
This is only one possible assignment. For your scenario the following are possible: T T L, T L T, L T T As you can see any suspect could have lied or told the truth, therefore it's undefined for all of them.
Расскажите, пожалуйста, как решалась Д.
В D div 1 верна ли формула n^(c-2)*П{a[i]}, где c — количество компонент связности, а a[i] — размер компоненты связности?
И надо не забыть про случай 1 компоненты, тогда ответ это 1 % MOD =)
О нет. Ну, мне не обидно, что мое решение не пройдет, учитывая как я получил эту формулу. Сначала я час преобразовывал матрицы и ничего не получил. Потом я за 10 минут до конца стал подгонять формулу под пример и получил совершенно рандомную и никак не обоснованную формулу, которая подходила под частный случай пустого графа (где формула n^(n-2) известна) :)
Самое забавное, что я также упустил этот случай, потом меня взломал RAVEman. Я исправил багу, а затем взломал его тем же самым тестом=)
да =)
Как некоторые так быстро вывели формулу в D(div 1)? Я вот долго долбался с определителем и в итоге получил нужную формулу, а некоторые за 9 минут это сделали, видимо я просто плохо умею преобразовывать матрицы...
Я её просто знал — это классическая олимпиадная задачка по математике.
Я почему-то не сомневался, что ты так скажешь=)
Или среди десятка тысяч задач, которые когда-то где-то кем-то использовались, эта тоже есть, и нашлись люди, которые потратили время на нахождение решения когда-то и теперь, со второй попытки, делают это, скажем так, быстрее)
Я просто оставлю это здесь.
https://www.google.com/search?q=количество+способов+сделать+граф+связным
Ну нельзя же такие бояны давать. Ещё от меня. "Улики A и B считаются связанными, если есть прямая связь между ними или есть прямая связь между уликой A и некой уликой C, которая связана с B." Не знаю, может меня одного, но такое определение ввело в заблуждение. Я сначала прочитал как "если существует вершина C, смежная с A и B", продолбал кучу времени.
А вообще контест интересный. Как последнюю делать?
Ну это читы, гуглить формулы это не спортивно!
Если ты про меня, то нет, в моём случае, можешь мне поверить, я её нашёл уже под самый конец контеста в целях проверить — не одному ли мне эта задача показалась боянистой.
Ну ты сказал, что знал, так что к тебе претензий нет.
Я формулы не знал, но знал про коды Прюфера, но про крайний случай с 1 вершиной забыл так что зачеленджили(
Ну или если уж не проверять задачи на боянистость, то хотя бы на неформулируемость запроса проверять не сложно.
Разбор по-русски будет сегодня вечером, по-английски — наверное, завтра вечером.
несмотря на несовсем удачно написанный контест, раунд очень порадовал, я даже не огорчусь, если обе задачи упадут
Is system testing going to start soon? Or we can go sleep?
What about watching foorball this night?:)
I'd prefer going sleep than watching football match between our national team and another one:)
I do not mind!
D1P1
I just mistake it for only in the end of string...
I mistake it for insert or deleto any pos of the string...T T
Да как так?? в претестах Б нет теста 1 0 -1?????? я открыл рандомное решение в моей комнате, и оно упало((( facepalm
В задаче довольно несложный код — вы хотите, чтобы ещё и претесты были сильные? Вот в Е — да, там были сильные претесты.
сильные? да это первый тест, который приходит в голову после претестов
Ответ на него: Lie ?
ну конечно
Не понимаю тогда что такого примечательного в этом тесте:)
Это Вам он первым в голову приходит. Кому-то первым в голову приходит что-то иное, это ведь далеко не единственный крайний тест. Все крайние случаи в претестах бывают разобраны, когда задача по сути простая, но сложная в написании. Здесь же всё наборот: надо немного подумать перед тем, как написать очень просто код.
я накодил задачу достаточно быстро, но опечатался в места, где надо выводить Truth. Как такого теста не было в претестах :( Поспешил — людей насмешил :)
Каким тестом ломали C div 2?
Теми, где лучший вариант вылазит за строку, например:
abcdaabя таким ломал
d
abcdef
5 взломов тестом
aabcd
aadc
тестом aab caa взломал 10 человек
abcbcbcbc и dabcbcbcbcd Я так понял у всех на етом тесте программа слетает.Жаль что я пока в С++ не розбираюсь, так бы взломов было намного больше:)
11 взломов у меня тестом abc ea
Чтобы пройти такие тесты нужно было проверять придется ли нам в строку добавить дополнительные символы или просто добавить в начало и конец строки фиктивные символы
я просто сдвигал вторую строку отностиельно первая на -2000..2000 символов. и считал символы равными, если они существуют и равны
может как-то приблизить момент тестирования, а то уж спать охота?
Спасибо за интересные задачи. Единственный минус наверно в том, что первые три оказались слишком простыми.
По-чему же ты тогда так плохо написал???
тема сис
ек-тестов не раскрыта:(Долго не мог отослать задачу div1-B, валилась на первом же тесте. При замене Integer.parseInt(s) на Integer.parseInt(s.substring(1)) начало проходить. Кто знает, на каком числе вида +x он может валиться?
The characters in the string must all be decimal digits, except that the first character may be an ASCII minus sign '-' ('\u002D') to indicate a negative value.
http://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Integer.html#parseInt(java.lang.String)
Ё-маё, у меня же седьмая Java! Ребята, я нашёл КАРДИНАЛЬНОЕ отличие шестёрки от семёрки, знак "+" парсится в Integer.parseInt() http://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#parseInt(java.lang.String)
k = 1 in Div1-D......... well this is just mean.
When will the system testing start? It's already 4 o'clock in China...I'm very sleepy >_<...
System Testing is on Div 1 now .
after that testing for Div 2 will be started ...
;)
=.=不开rating虐了petr睡不着是不是...
whaaaaaaat ?? 8D
ух ты, див1 сначала начали тестить! администрация codeforces прислушивается к просьбам потребителей!
У меня вот С сломается на abababababababa abababacdbababa =(
Я, конечно, не знаток психоанализа, но, по-моему давать задачу с модулем 1, и не давать теста с 1ой компонентой и к = 1 в претестах — это говорит о серьезной ненависти ко всему человечеству:(
Точно! Значит задача некорректна и контест должен быть не рейтинговым!
Мне кажется они не распознали злободневную иронию.
Задача 2500, код предельно простой, можно хотя бы один случай разобрать? ;)
Это сугубо мое мнение, но по-моему "возьмем математически не простую задачу, которая легко гуглится, и в которой 10 строк кода, добавим немного искуственный частный случай, получим некоторое количество упавших и малое количество сдавших" — это не лучший рецепт для 2500. Если бы не было гуглимости и частного случая — была бы отличная 2500. А так — извините, мне не понравилось:(
Да, сорри, плохо получилось, что она легко гуглится. Я задачу придумал сам и не подумал, что она может оказаться известной, хотя следовало. А случай это не частный, а просто крайний. Они везде есть. На это, как мне кажется, глупо сетовать.
Да я не особо и сетую, просто сказал, как мне показалось было бы лучше. Хотя, наверное, задним умом все крепки)
Для меня русский язык вроде бы почти родной, но я поставлен в тупик:) В чем разница между частным и крайним случаем?
"Частный случай" — это случай, для которого логика решения отлична от логики решения в общем случае или в других частных случаях. В "крайним случае" логика решения так же (например, работает та же формула), но часто его приходится обрабатывать отдельно из-за того, что формула вырождается (здесь, например, n-2 степень становилась -1. Можно было напистаь так, чтобы работало и в этом случае, реализовав деление по модулю, но проще было разобрать этот случай отделно), или из-за того, что это как раз база динамики/рекурсии, или ещё по каким-то причинам.
Я тоже задумался, как четко сформулировать разницу. Но ответ автора контеста очень понравился: "“Частный случай” — это случай, для которого логика решения отлична от логики решения в общем случае или в других частных случаях. В “крайнем случае” логика решения так же (например, работает та же формула), но часто его приходится обрабатывать отдельно из-за того, что формула вырождается"
Ну, хоть в энциклопедию...
По-моему, частный случай — это любой случай, подходящий под общее правило. А такой случай следует называть, например, "особым", чтобы не путаться.
А почему див. 1 тестируется раньше див. 2 ведь до этого контеста все было наоборот?
Гена настолько суров, что ему для победы в матче даже не обязательно решать самую простую задачу.
Гена на первой задаче набрал 1500 баллов, зачем её ещё и решать)
Спасибо авторам за контест=)
Увы, во второй задаче поставил случайно 10000 вместо 100000 и упал на последних тестах, тем не менее задачи интересные, а тур как всегда хороший. Спасибо!
Задачи доставили, спасибо авторам.
Еще бы руки чуть попрямее:)
О, я покраснел:) В первый раз в новой системе цветов.
upd. кстати да, пересчет рейтингов 1го дива произошел до окончания тестирования 2го дива.
Оба победителя выиграли, сдав по задаче на 01:59:08 :)
нееееееееееееееееееееееееееееет
мы потеряли его....
красный...
Большое спасибо за раунд! Задачи очень понравились. Условия составлены чересчур корректно, чтобы не дай бог лишний раз не задуматься :)
По задаче 156C - Шифр планировалось оффлайновое решение, т.е. предпросчет и ответ за O(1)?
Да, именно так.
Онлайн решение выдавало бы другие ответы)
Можете помочь разобраться со странным поведением программы?
1250545 -на тесте 35 странный вывод. Вроде должен всегда выводить n строк, а вывел только одну. В чём может быть причина?
У тебя массивы слишком маленькие. Видимо в процессе вычислений вышел за границы и перезатёр число n единицей.
Точно. Ошибся на один 0. Спасибо.
Можно писать 1e5, так легче считать нули:)
Ух ты. Спасибо!
И кстати решение не заходит в ТЛ даже если увеличить массивы... вывод о том, может ли быть текущий человек преступником нужно делать за O(1) а не O(n). Вот тут рассказано как это быстро делать http://codeforces.com/blog/entry/3994#comment-80790
можно за log:)
Да, я уже успел это проверить. Но тайм лимит — проблема более понятная.
Уряяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяяя
Спасибо авторам за офигенный контест. Все бесконечно круто, за исключением маленькой детали. В задаче про шифр многие выводили d[i][j] - 1, что, теоретически, должно падать, так как d[i][j] может равняться нулю по модулю, но при данных ограничениях в ноль не обращалось. Если бы модуль можно было задавать ...
Офигеть, и правда, забавно. А что, действительно такого теста при данных ограничениях не существует?
Не существует, увы.
А я делал ans=mm-1 и потом к нему прибавлял :)
Всё отлично, но в задаче C div-2 не мешало бы сделать чуть более полные претесты. Я неправильно читал входные данные, а W_A только на 23 тесте. Обидно..
very nice problem set, thanks :)
very nice problem set, thanks :)
Nice problems! 156A is tricky!
I agree with you.I get WA in 156A because I misunderstand it.
1246567
The output of double format in C# code is wrong. There is a comma(','), not a period('.').
I think my solution is correct. but I got "wrong answer". is this a system problem or my fault?
I think you have to set the locale of your program to "en-US", but still looks like you will get Wrong Answer.
juancate is correct (in "but still looks like you will get Wrong Answer") — you are expecting, that the smallest circle is red, but it's not always truth
Скоро разбор?
Наверху писали
У меня одного были ошибки на сэмпл тестах, за которые снимали баллы? Я понимаю, что сам дурак, но из-за ошибки типа "Not Defined" вместо "Not defined" уменьшать баллы не очень гуманно. По-моему, было бы не плохо отменить минусы на всех сэмпл тестах.
За то это поучительно для будущего: если надо выводить текстовый ответ, его следует копировать из текста задачи или набирать ОЧЕНЬ внимательно. Пригодится на любом соревновании.
В этом Вы, безусловно, правы.Но, все-таки, если говорить о гуманности, то я скорее склоняюсь к фиче topcodera, где можно проверить на сэмплах, не потеряв никаких баллов и затратив меньше времени на проверку вручную.
И как же там проверить на всем сете без плагинов?
Я писал TC только 1 раз, но, насколько я помню, проверить на нескольких первых тестах система может.При этом очки за неправильный ответ ты не теряешь.Возможно, я не прав.
В ТС все проверки в клиенте надо делать ручками, а послать можно код, не проходящий экзамплы
Хм, как мне сказали более опытные участники ТС: "Если у тебя стоит Kawigi Edit, то там есть кнопочка "Run...", запускающая сразу на всех тестах из условия твоё решение. Если нет, там всё равно есть кнопка test, позволяющая запускать решение на тестах из условия и своих по одному."
Ну, тут тоже есть кнопка "Запуск" и скрипты/аддоны, парсящие ввод
А разве там где-то можно проверить на сэмплах без их копипаста ручками?
Вообще, я уже тему куда-то в другую сторону увел.Вопрос-то в том, что гуманнее за плохие вердикты на сэмлы прощать :)
На самом деле, я тоже считаю, что не нужно засчитыать решения, которые упали на тестах из условия, более того, я думал, что на Codeforces сейчас и есть.
Есть только для первого теста
Непонятно, почему не на всех тестах из условия.
Ну, особенность системы. Я сам считаю, что было бы хорошо на всех тестах из условия. А так было забавно на первой тренировке — там в 3 задачах из 5 был один мультитест, так что минус получить по ним было невозможно
забодали абсолютно непонятные проблемы с компиляторами.. почему вот это решение 1247302 на делфи выдает рантайм тоже решение на freepascal (c исправлением на ansistring) полное решение 1255021
upd попробовал поэксперементировать с количеством фальшивых символов, добавляемых в начало и конец строки s. получились какие-абсолютно не адекватные результаты. может кто то прокомментировать? 1255037 1255040
Все очень просто — в функции prov вы вылазите за строку s. Отсюда непредсказуемое поведение.
Долбаный MAXSTACKSIZE. Поставь я его вручную побольше, D бы прошла :(
Когда будет опубликованн разбор задач?
Как я уже писал, сегодня вечером.
Looking for the editorial... When will it be available?
Today in the evening or night.
When do you offer the editorial of the contest??
Russian editoral of your division have publicated already, you can use google translate. But it is better to wait to English version.
Could you please provide direct link to the editorial?
Does anybody know if the english version of the editorial is avaliable?
No editorial yet now !!! is it published in any other blog ??? one helper has said about russian version... but I've not found any link so that I can use google translator ...
please provide the tutorial for this contest...!!
Russian version only: http://codeforces.com/blog/entry/4005