Привет, Codeforces!
26 марта 2015 года в 19:30 MSK состоится очередной раунд Codeforces #297 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Это мой уже третий Codeforces раунд, надеюсь, я вам еще не сильно надоел.
Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач, а также моим старинным друзьям Павлу Холкину (HolkinPV), Илье Лось (IlyaLos), Виталию Кудасову (kuviman) и Артуру Свечникову (ikar) за прорешивание задач и вычитывание условий.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Стоимость задач будет плавной динамической с шагом в 250 баллов. Подробнее об этом вы можете прочитать здесь. Задачи будут расположены в порядке предполагаемого возрастания сложности.
UPD2 Соревнование завершено! Спасибо всем кто участвовал!
UPD3 Разбор уже ждет вас здесь.
UPD4 Поздравляем победителей!
hello, i have decided that i'll downvote every comment in this post for fun :)
Sure, then everyone who comments in this post will downvote you for fun :))
downvote Is interesting and helpful for get negative contribution :))
Everybody wants positive contribution as like as positive rating..but?
It' s funny. I wish you get more and more downvote
Blog upvotes: 145. Your comment downvotes: 154. See the diference!
Can moderators add an option to disable people from commenting who troll here? I am pretty sure people are here to learn and not to waste time on attention seekers.
Do not be so serious. If there are no fun over here it will be boring.
I enjoy funny comments as well but let's just agree that this guy's comment is pure crap.
Your last contest had nice problems.
Thank you for creating another contest.
I think you mean "translating into English"? :)
As I see that you are from Russia and the google translate of your blog in Russian gives "translating into English" too
Fixed.
The comment is hidden because of too negative feedback, click here to view it :))
It was good
good
good
good
Why does the registration close in less than 2 hours?
Edit: Fixed :)
Is the registration time correct?? It will finish in the next hour
:D .
Thanks for the contest . Hopefully it will be a great learning expirience for everybody.
to div1 users: please dont create new accounts :||
like you?...you are one of them
Scoring distribution?
Codeforces Round #297 (Div. 2) 297 which is divisible by 9; 2+9+7=18=1+8=9 which is also divisible by 9; 2+7=9 && 9 which is also div by 9; Have any problem of divisible by 9? Best of luck.
I have a doubt. If 2500 people out of 3000 solve A , 2400 solve B , then how many points will be allocated for A and B (lets assume no of Solutions for C,D,E is < B)
Вечером после контеста Илье стало скучно, и он очень захотел помаксимизировать. смотреть бесплатно и без смс
_ Он вспомнил, что у него есть набор из есть n палочек и напильник_ напильник?? что-то я в этой жизни не понимаю
Классный раунд!
Как решать D?
Известная задача, один из вариантов решения — вырезать "уголки". Когда все плохо? Когда есть клетка со стеной, для которой, например, свободны одновременно клетки справа, сверху и сверху-справа (аналогично для других 3 направлений). Забросим все такие клетки в сет. Пока в сете что-то есть — берем оттуда клетку, чистим ее и проверяем, не нужно ли теперь добавить в сет кого-то из ее соседей.
Кто-нибудь сдал что-то не похожее на это?
Можно ли сдать что-то вроде этого: для каждой компоненты-комнаты найдем xmin, xmax, ymin, ymax. Расширим эту компоненту до соответствующего прямоугольника. Потом объединим все эти прямоугольники (соответственно опять расширив до прямоугольников их объединения). То что получится в конце и будет ответом.
У меня такое решение дает WA. Подозреваю, что проблема в том, как я обрабатываю касающиеся прямоугольники (их нужно объединить, если они касаются не уголком).
А не слишком много итераций этого процесса потребуется?
Возможно. Наверное на этом и построен претест 12. Особенно кажется много проблем доставляют именно касающиеся прямоугольники. Я не знаю как их хорошо обрабатывать, без них, кажется, можно просто сканлайном с dsu.
Я и спросил чтобы узнать, может кто-то знает или кто-то сдал :)
У меня такое-же решение, пока что получает WA32. Пытаюсь пофиксить, пока плохо получается
UPD: Нет, это неправда.
Я так начинал. Найти прямоугольник, при заливке прямоугольника проверять, не касается ли он '.'. Если касается — заполнить соседнюю строчку/столбец с такой же проверкой. Потом я понял, что искать прямоугольник необязательно, можно начинать с одной клетки '.'. Сабмишен
Я начинал это писать, но потом понял, что нужно будет много раз объединять на таком тесте:
Клетки площади один сами по себе представляют прямоугольники и их расширять не нужно. Но штуку слева нужно расширить сначала до площади 4 (и тогда она склеится с одиночной клеткой и будет площадь 5), потом до площади 6, ну и так далее. Если делать объединения в стиле "пройдёмся по всему полю и пообъединяем то что можно", то понадобится линейное от длины стороны количество итераций. Возможно, можно объединять более "умно".
А что, если искать эти xmin, xmax, ymin, ymax поиском в ширину, только с условием того, что можно идти по-диагонали?
Так получится за один раз обнаружить всю комнату полностью в вашем примере.
Но ведь не всегда можно идти по диагонали, например:
У меня идейно решение именно такое, но тест типо вашего пройдёт вообще безо всяких трудностей. Я на каждой итерации цикла не расширяю прямоугольники, а удаляю стены, которые мешают какой-либо комнате появиться.
Так и не смог придумать конкретный тест, где это работат медленно.
Работает медленно это тогда, когда в списке wall есть много стен, которые не мешают никому, а в конце есть стены, которые кому-то мешают, и удаление такой стены делает мало других стен удаляемыми. Решение будет работать за O((nm)2) Например:
1998 строк, состоящих из 2000 символов
*2 строки такого вида, как я показал выше.
Обе эти строчки отсекутся на первой же итерации и всё закончится сразу.
Я проходил и заливал комнаты различными цифрами(различными для каждой комнаты) потом для каждой цифры находил x_min, x_max, y_min, y_max и вырезал что внутри.
Получал TL на 12 тесте.(Python)
Это доделывается до TL32, но, наверное, не на питоне.
Thanks fcspartakm
Nice contest :)
The scores of problems was so low that hacking was important than solving problems...
Why????!!!??? :(
What is solution to problem C...it seems like simple task but I cannot pass Pretest 4
Just make right rectangles. The square would be bigger, if the side of rectangle would be bigger. Let's sort them! And after that you can use dinamic programming.
Does dp is really needed here? I've solved without it.
No DP is needed. Sort and then traverse backwards.
I had a strange problem during the contest, two times my default compilator changed from GNU C++ to GNU C (and I get two compilation errors :)). Did someone else noticed such thing too?
I had the same problem.
Yes, compilator changed from PyPy 3 to Python 3, but that change got me AC to problem B :) (It was TLE in PyPy, but same code got AC in Python)
Same here...
So will we have -100 because of two compilation errors?
No, compilation errors do not count.
Ok, thanks :)
Mine changed from GNU C to GNU C++ :)
Great contest! Thank you fcspartakm!
multiple account?
really??? then Sorry_dreamoon is probably duplicate too...
He is, but not dreamoon_love_AA's. And I think that Majid perfectly knows the answer to his question but it seems like he wants to be downvoted...
Could somebody give me a hint of how to approach D and E?
Edit: Nevermind, the editorial was posted surprisingly quick.
I see the most hacks are in problem B.
Can anyone tell us what's the hacking test case ?
It was just a big test(maxtest). Some people used std::reverse and the complexity of their codes was O(N^2).
Just TLE. We must not swap symbols in all substrings, because it gives O(n / 2 * m) orepations
Many people did a slow O(NM) solution, reverse all the segments.
Of course it's not passing for test case like:
aaaaa... 100000 1 1 1 ...Спасибо за оперативный разбор!
Pff, I'm so sad because I didn't figure out E ... :(
Update: Nooo, my C is wrong :( :( :(
Those hacks saved my a*s :D
Same here, my C got pretests wrong, because of integer overflow!
So I make up for it with lots of hacks :)
Why this test generator is wrong ? the only explanation for that is 1 space in the end of file, because this works well.
Why 1 space generates an invalid input?
Because it is an invalid input. Somebody may read using fread with a buffer(sometimes I do so) and when you see the size of the buffer, then you can generate a test with a lot of spaces in order to make his/her buffer overflow and hack him/her.
Подскажите, что нужно было делать в задаче D?
Валится на 12 тесте, и потому даже нет возможности узнать, что конкретно работает не так...
Я здесь косяки отлавливал:
Должно получиться:
Не могу понять, почему тут 10479062 падает на 92 тесте (RE). За границу массива вроде как не должен выходить. Может, кто-нибудь помочь с этим?
Problem C was so ill framed in English :/
791 ACs on C. Then why would this problem have 1000 points? Isn't that the general solve count for problem C in a typical CF round? -___-
Поздравлять людей, зарегавшихся 4 часа назад... Поэтому и читерят.
Мне кажется, что нужны идеи для борьбы с подобными "смурфами".
WA during the contest : 10474140 AC after the contest with the same code : 10476119 Just put a #include in a comment Any explanation ?
"Wrong answer on hack 1"
Doesn't it mean weak cases?
If I was in other room ,the code would have passed system test ! It isn't fair
You mean that the solution didn't even pass the pretests or it passed them and then it was hacked?
Passed the pretests then it was hacked after that I wrote a new code and got Wrong answer on hack 1, after the contest I re-submitted the same code ( which was getting WA on hack 1 ) and got AC
i had the same problem before in another contest, the thing guys told me back then was that limits.h is somehow not supported but i dont know exactly whats wrong...
Problem A got accepted and limits.h was included
its strange... i think it would be more useful if you asked this in stackoverflow.com
Was the round Unrated? if not, when will the ratings be updated??
Soon tm
in problem C in the test case 4: 8 5 3 3 3 3 4 4 4 how correct ans is 25?
decrease 5, then construct (4,4,4,4) and (3,3,3,3)
Yes
4*4 + 3 * 3 = 16 + 9 = 25 ...
I know !
The five becomes a four and then 4-4-4-4 and 3-3-3-3 are correct rectangles :)
On C it wasn't particularly clear that multiple rectangles are being created... "Ilya decided to make a rectangle from the sticks" implies at least initially that there is only one rectangle. (Or maybe I just need to read more carefully)
Agree. Google translate does a better job:
"Ilya decided to make rectangles of the sticks."
I hope that the translators be more careful about the singular/plurals.
D was one of the most interesting problems i have ever seen. Too bad i took wa on #12 :(
Thanks who send to B with O(n^2) complexity
can anyone help me why this solution got WRONG ANSWER http://paste.ubuntu.com/10685457/
UPD : it's okay i got it now!!
Can anyone tell me why my C solution was skipped whereas the same code got accepted after the contest?
You have cheated.
With whom my code has been matched can u tell me??
http://codeforces.com/contest/525/submission/10464753
Guys, did I solve one or two problems?
One
I meant two
How Silly were the pretests on C,,,,, Actually, how silly i am :( Notice the differences between these two solutions- http://codeforces.com/contest/525/submission/10464785 and submission:http://codeforces.com/contest/525/submission/10477043 . Anyway, thanks fcspartakm for nice contest :)
I'm afraid to seem impatient but when ratings will update?
http://codeforces.com/contest/525/standings/page/4 uwi's B is still judging, wtf?
And slycelote's A :D
is the contest unrated??
No. The ratings have been updated!
В Задаче Е у меня код локально проходит претест 1, но в "запуске" здесь (как и на претесте) почему-то неправильно считывает массив a и соответственно выдает WA. Никто не знает, с чем это может быть связано?
P.S.: я понимаю, что решение словило бы TL
Попробуй запустить с MSVSC++
Спасибо большое. А почему такая "магия"?
Скажу честно — понятия не имею. Просто если есть какие-то неожиданные отличия в работе, то сразу меняю компилятор на любой C-шный компилятор попавшийся. Но на MSVSC++ не припомню подобных фэйлов.
Еще раз спасибо
Этот цикл:
Плох тем, что присваивание идёт fact[i], а сравнивается с s уже fact[i + 1]. Соответственно, цикл легко выйдет за границу массива fact и наступит undefined behavior, т.е. результат будет зависеть от компилятора.
Не в данном случае, но идею вашу понял. Спасибо
Would you mind putting " UPDX Contestants' rate changed" in the end of the post, when new rates apply?
I'm waiting for ratings...
Do they come tonight????
I am staying up all night just for looking at the rating update. When will it be updated???
Now :P
I cannot see the problems in the "PROBLEMSET".
Oh, I find them. But it is very strange that they are not listed in top.
nagetive contribution makes me upset Ծ‸Ծ
This is the code used in Winner's C: http://codeforces.com/contest/525/submission/10463905 This is the code used in enesoncu's solution to another problem: http://codeforces.com/contest/436/submission/10422970
Doesn't it look very similar!
Can you tell me what is wrong with hacking using generator? I tried three times during this contest, but i have got Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]
Probably this is connected with the fact that i have used std::endl? How to do it correctly? Should I use "\n" next time? Because I really could have done at least 2 hacks!
Thank you
Can you help me?
http://codeforces.com/contest/525/hacks/143414/test
Judge return this:
Validator 'val.exe' returns exit code 3 [FAIL Token parameter [name=s] equals to "/********...correspond to pattern "[a-z]{2,200000}" (stdin)]
I couldn't find any problems...
It seems you've submitted it as a test, not as a test generator
Thanks for interesting problems and weak pretests. There were nice opportunities to hack.
Чё за бред блин
:)
Could somebody please help me to interpret the following wrong answer on problem D:
Test: #12, time: 717 ms., memory: 4404 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWERexpected: '***..*......*...****.*****.*.....**.*******.******.*..***.***.**', found: '***..*......*...****.*****.*.....**.*******.******.*..***.***.**'Both strings are identical, but still in some way the validation system seems not to like my string. Thanks in advance.
Maybe you print
'\0'at the end of your answer? :Prather not, as the wrong answer is in test 12 in the 6th word. In such situation all preceding tests should also fail.
Thanks anyway. I am really puzzled with this error.
The line is actually 2000 characters long, but Codeforces displays this kind of error like
[some prefix]+"..."+[some suffix]
Thus, in your error, the "..." unfortunately looks like part of the line. The real error is somewhere in the middle :P