Всем привет! Скоро состоится Codeforces Round #220 (Div. 2), автором которого являюсь я, Дмитрий Березин. Это мой третий раунд, и Сережа все еще верит, что последний :)
Со времен прошлого раунда многое изменилось, Дима и Инна подумали над своим поведением, извинились перед Сережей, и все теперь живут дружно. Вам предстоит еще больше укрепить семейное счастье!
Большое спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда, Марии Беловой (Delinur) за перевод задач, Михаилу Мирзаянову (MikeMirzayanov) за превосходную систему, и Сереже Нагину (Sereja) за то, что любезно (не выложил тут очередное фото) согласился помочь в тестировании.
Разбалловка будет. 500-1000-1500-2000-2500. Я же сказал, что будет :) Прошу прощения за задержку.
По всей видимости задача B имеет ошибки в авторском решении, приношу свои глубочайшие извинения. Сейчас мы исправляем ошибку и тесты. Раунд будет не рейтинговый. Большая часть решений, которые прошли претесты — неправильные. Вы можете исправить ваше решение и послать его в систему, как только все будет исправлено, все решения будут перетестированы.
Спасибо Вам за потраченное время, постараюсь в будущем исключить подобные ошибки.
В правке — мудрость
Больше похоже на серую мудрость :)
Та ладно, сам иногда пользуюсь :)
На CFе только ей и руководствуюсь — работает почти всегда.
А я уже ожидал там увидеть чьё-нибудь фото...
Disvoit me, please.
доминируй, властвуй, унижай :)
:)
why people ask this kind of stuff?
I think, thay like decreasing their contribution.
nope.. i don't think that is the reason.. i think that they (by mistake) left their account logged in somewhere and someone else posts this to cause their contribution to drop...
however, i may be wrong...
It is a kind of online fetish :)
You're absolutely right:)
because they're troll :D
What the hell does "disvoit" mean?
means clicking on the arrow pointing down
No. That's "downvote". "Disvoit" is not even a word.
Give me a reason, please @@
Раунд обещает быть интересным! Точнее условия :)
Пикчу не показывает? Эх, печаль-обида..
Используй правильные файло-помойки!
translate statements via Delinur not Google translate!
Hope that the translation of problem statements will be good so that we can understand the problems. :)
plzzzzzzzzz make the statement clear enough to understand
Hope understanding the problem will not take too much time then solving.
Waiting for the interesting problems:)
There is a little mistype : рфму→have :)
The last ?..It's time to say "good bye"??? Best wishes...This round no div1.maybe it is a difficult round,I think...and I hope every one will get a high rate...
wish everybody will the best
.... Разбалловка будет.
Хорошо что будет...!!! :)
This is gonna be my first round here!! hope it's gonna be fun, and I'll be at least "green" after it xD
Points distribution will be.
Oh, good! I was worried that it would not.
Well, sometimes it isn't. Not before the contest, at least :D
I remembered there was one Codeforces round they wrote
Points distribution will be 500-1000-1500-2000-2500-3000
or something like that, to indicate that there are 6 problems (instead of usual 5).
Which means there will be no problem on today's round :p
Good Luck!!
2 minutes remaining and still "Points distribution will be."
I think it will not be
5 sec. to start
Do you want to say there won't be any distribution?
Вот давно назревал этот вопрос к администрации, может стоит дать возможность регистрироваться вне конкурсе во время раунда? Я что то не понимаю и есть какие-то технические проблемы реализовать это?
p.s. Просто опоздал на 15 минут и обидно не поучаствовать.
Есть одна большая техническая проблема: распределение по комнатам осуществляется с помощью весьма ресурсоемкого алгоритма, именно поэтому регистрация закрывается за 5 минут до начала.
Если запретить таким внеконкурсным участникам делать взломы — Ваше предложение уже становится реализуемым. В целом, неплохая идея, если не забывать про некоторые подводные камни, связанные с подобным внеконкурсным участием.
Чего там разбивать то? Вот пусть размер комнаты k, сортим участников по рейтингу, берем первых k штук, кидаем всех в разные комнаты, берем вторых k штук, кидаем всех в разные комнаты, повторять, пока участники не кончатся.
Вполне возможно, что на CF как раз и используется что-то похожее, не буду спорить, т.к. не знаю.
На том же Топкодере все несколько сложнее, проще объяснить фактом: есть комнаты с кучей таргетов и красных, а есть сине-желтые комнаты. Причем, все это делается умышленно. Вот этот алгоритм распределения точно ресурсоемкий.
Да ладно, это реализуется без особых ресурсов, я конечно не знаю какой глубокий смысл этого распределения, но почему бы просто не добавлять к рейтингу просто случайно нормально распределенное число скажем с EX = 0, и VAR = 1000, дальше сортировать и первых к в первую комнату вторых во вторую и т.д.
Ну как вариант, запретить взломы. А что там за алгоритм такой, аж интересно стало?
Спасибо за эволюцию легенд! :)
Is this contest actually intended for "Div 1 only?"
Ridicule contest... I really hate it! Problems could be for div1 !
At least first two problems are very easy and can be solved by everybody.
What do you mean by "very easy and can be solved by everybody"? If you mean that there are sumbissions from all colors/divisions, then yes, but to qualify them as being "very easy" when a lot of red/orange div 1 guys fails pretests, I think it's not the good expression. Just by comparing with statistics from previous contests, it seems obvious that this one is one of the hardest div 2 contest. ( yes, I'm vexed to not solve B and C :D )
Thanks God! Contest is unrated!!
The standings prove you wrong. Problems 1 and 2 have a lot of WA and hacks, even among high-ranked contestants. Problems 3 and 4 seem much better in that regard, and 5, once again, contains a lot of tricky situations that could lead to WA. The optimal strategy here seems to be "just pass pretests and farm hacks"...
They just said that author's solution for problem B is wrong. That's the reason of so many WA.
BTW, my statement is correct, problems can be solved by everybody, but pretests cannot be passed :)
I guess it is true in that sense :D
Still, A was also far beyond the expected level of difficulty.
Yeah, A is easy, but I didn't think carefully. After I saw "pretest past" I moved to the next problem. When the test was about to end, I was hacked and I instantly found the bug, but that was too late...
Oh, sorry, I know why I found the second problem harder than it was really: I was thinking we could do such operations: 243 -> 63 -> 9 :/
This round should have been Division 1 only.1 hour and 22 minutes passed and problems:
A) Инна и розовое пони x489
B) Инна и девять x202
C) Инна и Дима x112
D) Инна и последовательность x37
E) Инна и пупсики x2
Is this contest?
Is this contest?
I think the problems are much harder for Div 2 contestants:(
A great round I will remember forever!
is it too hard for div 2 contestant?
there is less than 1000 that solve problem A...hahahah
I thought problem A was not so much hard as it was very easy to make a minor mistake. For example my code was failing things like "1 5 1 3 1 1" for a long time because I forgot to account for when there is no move available from the first position. After I "fixed" that it failed things such as "1 5 1 1 1 1" because I was saying there is no move available from the first position, thus we should output "Poor.." :) Probably explains why many fast solutions are being hacked.
edit: and apparently my solution failed systests regardless :) Another silly error.
А за взлом авторского решения дадут +100 :)
I realised that author's solution to problem B is wrong when I tried to hack someone with the test case "18181". It should print 3, but author's answer is 2.
Thanks for the spoi1er!
The round is unrated. You can ignore the comments if you want.
contest is unrited now (i don't know it is good or not) .
Is the round going to be UNRATED???
Yes !
Oh my god!!!!
Unrate...What a pity, even I was zero AC.But thanks for the problem writer :)
Какая же двусмысленная фраза: "... Сереже Нагину (Sereja) за то, что любезно (не выложил тут очередное фото) согласился помочь в тестировании"
месть!:)
Я очередное фото нашел, пацаны! Вот:
Это было неожидаемо. Просто, я прорешивал все поздним вечером, много чего не заметил.
N-смысленная
nimab!
In problem D i keep a deque and just delete an upper_bound() ammount of elements from the front of the queue. Will anybody PLEASE tell me where i'm wrong i've been trying to find a bug for the past 40mins. I mean the source code is only like 30 lines long. Or perhaps that task also has an error?
Here's my submission (won't be available until after the contest) http://mirror.codeforces.com/contest/374/submission/5465516
i did same thing... after that, i realized that it was a mistake...
the question should be more clear... it is not deleting first k elements but is deleting the a1'th, a2'th, a3'th .. ak'th...
i realized this only at end of contest and didn't have time to code in the answer..
THANK YOU!!!
it did seem a bit easy for D problem.
You're welcome...
However, IF, for instance the problem really was on the basis of removing first K elements, i'd not use deque since its still too time consuming (in worst case) since deque removes only 1 element at a time...
Instead, keep a normal (statically declared) array, a start pointer and an end pointer...
that'd be more efficient for handling such a case... however, the problem was different so even this wouldn't apply...
:)
When I first read problem D I knew I can do it, but unfortunately it also tricked me into thinking about a deque. I didn't implement that because there were parts of the statement which didn't make sense to me (eg. "If number a1 is larger than the current length of w, then nothing falls out of the sequence.") in this interpretation. Now that I know what the problem is all about, I think something like a Fenwick Tree might do the job. Maybe is even simpler, but that is the first thing that came to my mind when I saw jaybosamiya's above comment.
Oh my god!
I wonder what are the codes that actually got accepted for problem B under the bad judge doing ......
I think they multiply the result by 2 for every block like "181" or "18181".
Should we multiply by (LENGTH + 1) / 2?
yep... for all the length's which are odd, multiply by (length+1)/2...
not sure what the author did......
when i say odd or even, i am talking about 18 having length 2 which is even and 181 having length 3 which is odd and so on... some others are using a slightly different notation... do not get confused...
Yes, we can prove this by induction/recursion (though probably an easier way). When length is odd, clearly there is just one way. When length is even, we need choose (length)/2 dots from a list of (length) dots such that no two are consecutive. Say there are a_n ways to do this for string of length n. If we choose the first dot, we cannot choose the second dot, so we must now choose (length-2)/2 dots from a list of (length-2) dots. Thus a_n=a_(n-2)+1. Easy to see that a_2=2=2/2+1, so a_n=n/2+1 for n even.
Ignore. (Previous one is wrong...)
i didn't understand why they says "Most of the solutions that have passed the pretests are not correct",when there is easy testcase :(
This is not the case; I submitted such a flawed solution but failed pretest 12.
Did you make int64?
Hats off to author..you really succeed to make the worst contest ever.
I know the contest was hard, but still, no need to be so harsh against the authors. At least the contest was interesting. I am sure they worked really hard to create these problems. I hope the authors will host contest again, and hopefully an easier one.
i hope so too... i hope they will host it again and (preferably) easier with no mistakes...
however, i'd like it if the wording of the contests was improved a little (for example in problem D, it took me forever to understand even though I am actually very good at English)
Turns out that indeed it is not.
На чем ломали А?
1 5 1 3 1 1
I think the be worst thing is the author's mood...The last round,but without give us a good impression...
Зачем такую А давать для див2? Очень же сложно для новичков.
Сложно по меркам Div2-A, именно так и не иначе!
Плохо это только с той стороны, что ухудшает возможности ранжирования участников из Div2.
Подробное объяснение моей позиции читайте тут.
only 400 accepted codes for problem A! (before system test)
It seems that it was a Div 1 contest!
В авторском решении был неправильный ответ на тест 6?
Скорее всего.
I'm disappointed in the writer :,-(
this contest was very baaaddd!!!!!! shit............I hate that
the first round I did well and it's unrated @@, poor me
LOL
It was an extremely difficult contest for division 2 in my opinion, though A and B were certainly doable given enough time. I wonder what author's flawed solution to B was — it seemed like a relatively simple problem (my method was to find blocks of consecutive numbers that could be 9s [e.g. 818 is a block of 2, 7272727 is a block of 6, etc.]. If this block is odd length obivously there is only one way to get the maximal 9s, but if it is even you can select any length/2 numbers that are not adjacent. So for example 81818 is block of 4 so there are 3 ways, 818183333381818 is two blocks of 4 so there are 3*3=9 ways — unfortunately I spent too much time on D and didn't finish implementing this), though still hard for a div2B.
I tried using dp. But got WA. Then I switched to exactly what you said. Finding blocks and multiplying to get result. Well, that got WA too. Let see if it passes after rejudge.
Passed. :)
LOOOL I did exactly the same thing, however my first dp solution passed after rejudging! :D
.
Зашибись, после реджаджа баллы посчитали по последней удачной попытке. :)
Все равно не рейтинговый контест.
Ну всё равно это непоправимый удар по чувству собственного величия участников, я считаю.
If test 6 be in system test, it were be all right.
Mistakes happen... Let's try to be a little more forgiving :)
http://tinyurl.com/worstdiv2ever
Seriously?!? In A it was easy to make small mistakes, and definitely not a division 2 500 points problem; B was buggy (but it was interesting); C took at least 150 lines to code; D and E were out of the book problems. How is this supposed to be an 'have fun' contest?
out of the book problems? which book?
You are right, I was annoyed about solving 0 problems.
I'm sorry for my previous comment. It was an good contest, but it was too hard for div 2.
nope... i don't mean that... i actually mean "which book?"... i want to learn from this book...
i have found only a few good books till now and none of them have had these kinda problems, so if you can tell, it would be helpful...
thanks...
oh ok. For learning the basic stuff, I would recommend some college book, such as: http://mitpress.mit.edu/books/introduction-algorithms or http://www.goodreads.com/book/show/10803540-algorithms. Then, for getting better at programming contests, I would recommend https://sites.google.com/site/stevenhalim/ (AWESOME for programming contests, has lots of problems for every topic) and http://www.amazon.com/exec/obidos/ASIN/0387001638/ref=ase_thealgorithmrepo/ (steve halin's book is more awesome, but this one covers some different topics). (You can probably find them on piratebay)
please dont write worst contest because everyone know
Let's all calm down a bit. The authors work very hard to bring you these problems for no cost whatsoever, something is hardly an easy task (try writing 5 quality problems with solutions and pretests yourself, ensuring no possible errors, and see how it goes ;)). Simply because one problem happened to be flawed this time around (out of many many contests that went perfectly smoothly) hardly means that we all need to form a lynch mob. Life goes on — wait another week or so for the next one. If you are truly deserving of gaining rating, you should be able to do so over the next contests anyway, so if you would have otherwise gained rating take solace in the fact that you'll be gaining it again soon.
(This is not to say that rolling out a bugged contest is acceptable, but once in a while something is going to slip through the cracks. It's not worth getting too upset about — you just try to minimize it and move on)
"With no cost whatsoever" is a common mistake — actually, you get paid for making a round, on every serious contest site.
By my statement I meant no cost to the participant (except perhaps ad revenue generated or something, though I've never seen an ad on Codeforces). I am aware that the problem writers are generally paid for the round problems. But thanks for pointing it out, it is an important thing to know.
I totally agree that this is a very hard contest for Div 2. But I'm also disappointing to see all of those words you used to offend the author. Perhaps less people will be interested in making new rounds after such things happened.
Seeing how div 1 coders did ( or even red coders ) this is not even a usual div 1 contest. Is not to disappoint the authors, but they have to have some kind of sense of what difficult is and what is the suitable one.
I think they always try to choose the most suitable ones but mistakes sometimes just happen. And it's not "have to" but "should". Do you pay something for these contests? If you do then you have the right to ask for what you expect. Otherwise, accept it and give positive feedbacks to make it better.
I agree with flashmt, guys you should be really more considerate than this! Don't you ever make mistakes?!
What a fabulous solution of your task D !!!
I've learnt a lot from your code, thank you !!!
Okey, so you say that we should just accept everything and say: Wow, what a great contest!.. I don't pay for these contests, but they(authors) are paid to write the contest, if they are not able to produce good tasks,no one forces them to write them. And remember that 'we' (everyone) make the contests possible, the crowd that is present makes everything realizable, interesting, fashionable.What you say, to tolerate small mistakes, is of course correct observation, but how many times has a similar thing happened before? Look at the scoreboard of today's contest and see how many people solved A, B and so on, respectively, and tell me if it makes sense to you.
"How many times has a similar thing happened before?" Alright, I have been on Codeforces since its first days and I think I know this better than you do. There was worse time when 2 consecutive contests went unrated.
If you find the problems not suitable for you, no one forces you to join. And if you are not clear about what I said, I didn't mean to support this kind of contest but to tell you guys to be more considerate in your comments. Using that harsh attitude doesn't make the problems solved faster.
How unfortunately it is one bad Div.2 round and how fortunately it is one unrated round!
What is solution of D. I think it is balanced binary tree.
I think it's solvable using a BIT or a segment tree. A Balanced Binary Search Tree might also be an option but the code might get long.
ONLY 150 accepts for A...
900 Participants with zero score....
UNRATED contest...
=))))))))))
That explains a lot..
My final rank is 40th , and the contest is unrated !! How pathetic.. :(
same here, with 22th place :(
poor me!! rank 1 :'(
if someone is looking for a tricky case on A, try this; 5 1 3 1 1 1
my AC code (5465232), get wrong answer on this test case:
input: 3 3 1 -1 3 -1 2 2 1 1 3 1 2 -2
my output: 1
correct output: 2
when your submission status is "accepted" this is not mean that your solution is 100% correct,but you can say that with high probability your solution correct, so this is not mean that there was some mistake about authors work.
I'm quite sure the grandmaster knows this :) He's simply pointing out an error in the strength of the testcases.
The comments are really harsh! Guys you should calm a bit! The contest was really interesting and I really liked the problems (and just so you know this is not my normal attitude!), despite the problem B, the contest was perfect!
Ufff. A very tough round...
For Problem D,
I preproccesed the M integers and then trying to remove elements from deque.
From amortized analysis this algo should take O(N) time.
But i am getting WA. Here is my submission: 5469909
What am i missing ??
The round was quite hard, but I guess it still was fun for me.
Thanks author!
Round statistics,
93 of 2690 successful attempts for A (500)
75 of 494 for C (1500)
24 of 165 for D (2000)
да нормальный контест) не за баллы ж рубимся, а за знания.
Nice challenge round ! I love it!!! When I had submitted problem A , I locked my solution ASAP . And I even challenge the whole room! What a success!!I was very happy.
Well , it's really a pity that the round is unrated. I believe that the naive mistakes of B can be prevented. Please pay more attention to check the problem-set and solutions next time.
Whatever , it's a really nice Div 2 round ! I am wondering if I can set a nice question as problem A and D.
Thanks.
I thought in 374C - Inna and Dima recursion will cause stack overflow and I used my own stack. However, after the contest I found solutions on the top of standings simply use recursion. I copied those code and tested. Those code did RE on my windows 7, but they didn't in the "Custom test" in Codeforces. Why? This is my input generator:
On Codeforces I think the stack size is increased to 256 mb. You can read the compile flags of the various programming languages here: About the programming languages
В правке — мудрость
Well, the round was unrated (however, nothing unusual for Div. 1 coders). I have wasted a plenty of time thinking where my B solution can be wrong... Mistakes happen and contest authors have to be very cautious about their tasks. However, I don't agree with people here who are complaining about the contest. I am not sure if everybody is aware how much work you have to put to prepare the contest. So only Berezin can be really sad, that this round was unrated. We just had some interesting tasks we haven't seen before (and we have them in problemset). I hope that Berezin won't give up making contests here :) I would really like to see your contests (maybe more Div. 1 contests because they are so rare). Thanks for the contest, Berezin.
Yes. Had Problem B been correctly judged, this would have been a very interesting and involved Div 2. Even the simpler problems were tricky for high-rated coders to falter. I was happy to be a part of it and am not too worried that it went unrated although I would have loved it to be otherwise
I agree with you.
Why Codefoces system stack is so huge 268435456b (256 MB), unlike Topcoder 8 MB ? http://mirror.codeforces.com/blog/entry/79 http://community.topcoder.com/tc?module=Static&d1=help&d2=generalFaq
8MB stack size is default on many systems, so it's just left that way often. 256MB (limited only by memlimit) is a good choice in contests, and it's usually set that way when the people in charge realize that it should be done.
tutorial maybe ? i'm interested in A and B
btw, even if the problems are hard (that's what most people says), no need to get mad, just laugh it off, do yo want to stuck in div 2 forever ? always solve easy problem ? I want someday, i can solve problem that as hard or harder than these :)
http://mirror.codeforces.com/blog/entry/10018
round220 problemA I think the test 37 is error , because (1 + 1,3 + 1) = (2,4) ,then (2 -1 , 4 + 1) = (1, 5)
!
Why such a hula-boo ? The author/writer have given many good contests in the past, why to forget that? It is unfortunate that problem B had some mistakes and the round went unrated. By the way the problems were nice, but were little difficult for div2 coders. Div 2 coders must understand that though difficult,we must have to solve it someday to become a better coder. So please stop cursing and lets work around to solve these problems in practice.
when will the tutorial come for this contest?
link
I think next contest — simple contest. :)
guys help me , what's wrong in my solution ? 5474891
can somebody help with my tle verdict in problem c http://mirror.codeforces.com/contest/374/submission/5475238
i am following the way given in editorial using dfs with memoised tables
how can i find complete test cases of problems?(exp: problem D, test 63!:D)
This contest is bad ,but the problems are really good.
Is there any way we can get editorial of GYM problems because it will help us a lot in solving the problem?