Hi,
Codeforces Round #282 will be held at 13th of December, 19:30 MSK. Please don't note anything since the time is the usual time of contests.
The round is prepared by FarbodY, Haghani and Me(matrix).
We'd like to thank Zlobober who helped us a LOT for preparing the problems, MikeMirzayanov for the Polygon and Codeforces platforms and Delinur for helping us in preparing statements and translating them.
Our special thanks goes to mruxim for testing the round.
The problems will be sorted according to the estimated order of difficulty according to our opinion but we strongly recommend you to read all of the problems.
As always the update regarding score distribution will be posted just before the round starts. :)
UPD: It was written that contest starts at 20:00 MSK. it was a mistake and is fixed now. The round starts at usual time 19:30 MSK.
UPD2: We also thank niyaznigmatul for testing our round.
UPD3: Score distribution:
Div1: 500-1000-1750-1750-2500
Div2: 500-1000-1500-2000-2750
As you might have noticed, the scores can now be multiples of 250 as well. Let's thank Codeforces team for adding this feature!
Good luck and Have fun!
UPD4: Congratulations to the winners of both divisions:
Div1:
Div2:
The editorial for all problems except D and E Div1 are ready and can be found here. It'll be completed soon.
We thank you all for participating and hope you had a good time.
UPD5: The editorial is now complete and can be found here.
wow :) iranian contest I love them :)
matrix your graph is awesome and very motivated
Maybe there will be problem about matrix/matrices this round!
Its the opposite of the identity matrix :D
I hope that someday my graph becomes like that too!
Our special thanks goes to mruxim for skipping this round just because we needed a tester
"Please don't note anything since the time is the usual time of contests."
Happy coding
I got -14 after smth like that (I was gray too). But also, I got +184 rating)
The most intriguing fact about 282, however, is it is the number of planar partitions of 9.
The more you know ↑
What ? 2+2+2==8? Are you kidding me ?
Yeah, and 282 is permutation of digits in number 228. So awesome.
282 is divisible by two SO AWESOME
282 is also a funny article of russian Criminal Code.
Amazing!!! Did you know that it's divisible by 3... :| what a amazing number.... :|
Yes... and its divisible by 1 too So damn awesome
so interesting!
hope to see a nice problem-set and rating growth :)
This will be excellent preparation for the USACO December Contest.
Zlobober has a great contribution in almost every contest. Thanks bro.. :)
Have fun and good luck to all of you.
Codeforces really should think about some additional promotion, today I've found topcoder easter egg in locker room
We had these in our dormitory shower.
Time for dreamoon_love_AA :D
I think he will do it next round :D
It will be a good contest ...
Hope for much [pure] math
For me more interesting when anybody have more chances to hack each other(I want low pretests!!!).
Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.
And I thought I was the only one
i hate hacking ): I like contests like ICPC, where you know if your submission is right or wrong when you submit it.
It will be a great contest.
So happy for div.1 contest)))))
At last after 10 days !!!
hope more and more contests
Врываюсь в желтые сегодня короче)))
Не получилось, не фартануло.
Действительно. В который раз я уже лажаю на ошибке 0 — 1 != 1000000006?
hope candidate master for every expert
me too
Hope and expert for all pupil (and all Specialist)!
and all grey
Did you mean Newbie?
Wanna be Blue.... Gonna be White... -_-
Did you mean grey?
ya.. Grey..
It's possible to be white. See worse's graph.
Everything is possible
Nope...Try to get brown colour :P
I don't understand the reason why worse always tries to get negative point (Except last round). And he wants to challenge others and fails.
You don't understand why people sometimes want to do random stuff for fun?
it is my first time for div.1.....
I just want get a purple handle in this round~
Best wishes! Good Luck && Have Fun!
I hope this contest will bring me from unhappiness...... I even suspect whether coding is suitable for me...
Well...I didn't got a purple handle, en.....when you tired or lack of confidence,look at me ~, many times I tried my best but got a bad result, but I firmly believe that one day, I can become an excellent coder, not only in ACM. A gold medal is not necessary to prove yourself.
Don't you think it is a good idea to announce the scoring right now? Because of I think the website will be down (hope not) in a few minutes and you won't be able to announce it just before the contest! :D It would be after the start of the contest!
1750 points. O_O Rly?
"As you might have noticed, the scores can now be multiples of 250 as well. Let's thank Codeforces team for adding this feature!" Sounds sarcastic
CF #282
We hack as we could
Problems A, B and C are easy; but problems D and E are difficult ! (in Div. 2)
There isn't any normal problem :D
Good Bye div1)
correct score distribution (div. 1): 500 — 1500 — 2500 — 2500 — over9000
Как решать C?
Больше времени ушел на понимание 3-ого теста чем на решение задачи.
P.S. И то,и другое не имел удачи .
http://codeforces.net/contest/494/submission/9109255
В структуре T хранится распределение вероятности максимумов.
thanks a lot for nice problem :)
last 10 minutes, server was down. I could hack 10+ solutions but...
Also I could have hack some solutions
Woah, wasn't able submit my solution to A because codeforces wouldn't load. :(
A div1 / C div2:
Come across this comment, when suddenly my div2 C failed system test. What a coincidence. But really, I didn't notice that case!
Well, i am not alone in this planet :/
fail of the year
A: forgot if(b[i] < 0) ans is -1.
B: forgot if there is no S in T ans is 0.
added two ifs and got accepteds :(
What's the hacking test case for Div2A?
Here was something unrelated. Keep scrolling.
I asked for Division 2
I'm pretty sorry.
For A2, it was pretty simple too: many people had problems with calculating answers for numbers in segment 01-09.
Also many people accidentally had 6 instead of 7 for 1.
I accidentaly took 3 instead of 4 for 5 :/
That's for Div2 C/Div1 A :)
It depends on the code. Some people miscalculated the number of probabilities for a simple digit.
Server Problem,vary painful.
Я надеюсь, что "невозможно отправить в последние 5 минут контеста" = "раунд нерейтинговый" ? Под невозможно я имею ввиду "совсем невозможно" — увидеть не страницу "извините, всё плохо", так и не удалось.
What's wrong with test 6 in D, my stress test doesn't reveal any problems =(
Check all modulo operations carefully, especially with negative numbers.
Eh at least now my stress is giving different results, but I can't find the mistake =(
Преступление и наказание (одновременно взломал сам и взломали мою задачу)
Так бы эпичнее было бы
Сорри, но не умею картинки нормально вставлять
Клик, чтобы увеличить.
Last 10 minutes :(
Your avatar fits well to that pic :P.
For me it was best round ever with regard to number of hacks (I got +6/-1) :). "(#(" ftw :D! As well as best round ever with regard to place before systests (8th), I hope it will stay that way after them :P.
For div2, a lot of solutions for B had bad complexity O(a) — I managed to submit only two hacks though, due to the server being down for the final fifteen minutes.
Sadly, this time too, Codeforces went down in the last ten minutes. solved problem C but couldn't submit :(
please improve the server or limit the contestants number !!!!
Any idea about how to solve Div-1 B?
I found all occurrences of t in s using KMP, then did DP on the the position of the last substring you take.
So dp[k] would be the number of valid substring selections where none of the substrings have any chars after the kth char, and the kth char is within one of the selected substrings. Calculating dp[k+1] would depend on whether a pattern of t ended at position k+1 or not.
I'm not sure if this is right, but it passed pretests.
I did it in the same way — probably a useful structure is >> int last_before[i] << , indicating where is the last occurence of t in s, that ends before i. Then the recurrence can be sumarized to:
dp[i+1]=dp[i]+sumdp[last_before[i+1]]
sumdp[i+1]=sumdp[i]+dp[i+1]
(with edge cases and similar stuff added, of course)
Dynamic programming . For each index i in array, calculate the number of ways dp[i] such that b_k is i. And then sum of all these ways.
To do this , first find out all the occurences of pattern in text using KMP. Then recursion to calculate dp[i] for i =1 to n(size of text) would be
dp[i] = sum( j = 0 to pat_start[i] , sum(t = 0 to j, dp[t] ) ); dp[0] = 1;
where pat_start[i] = largest index p such that Substring[p,i] contains given pattern.
Now this dp might seem like O(n^2) but by maintaining some additional summations, we can do it in O(n)
Good bye, Blue. Welcome Green, again.
Я один столкнулся с тем, что, пытаясь взломать, при открытии чужого решения, открывается окно с посылками, само решение не открывается, ссылку с решением, на которую можно нажать тоже нет, в итоге взламывать невозможно? Так было вначале, потом удалось таки один раз взломать, потом тоже самое до конца контеста. Поведение одно и тоже на Ubuntu (Chrome и FF) и на Win8 (Chrome).
Я конечно и сам залажал контест, но невозможность взламывать тоже как-то выбила из колеи.
Ответы жюри:
"У вас должен быть установлен Flash. Некоторые плагины могут резать Flash, считая баннером. Попробуйте так же воспользоваться другим браузером или очистить кэш/cookies."
"В итоге ведь получилось произвести взлом? Остальные участники не жалуются, проблема где-то на вашей стороне."
"Мы не можем ничем помочь."
У меня каждый второй раз открывалось только окно для взлома, без решения. Firefox 34, Win7.
З.Ы. Это нормально, что я не могу переключить у себя галочку "по-английски" на "по-русски", отвечая на этот комментарий?
да, было такое. и ещё за 10 минут удалось взглянуть только на 4 решения.
It's midnight and I am facing an usual dilemma: do I go to sleep before the rating update or after? It's always a difficult decision...
The answer is: yes.
That's kind of a confusing answer :p 1) Yes, you should go to sleep before rating update. 2) Yes: you should go to sleep after rating update.
The answer to
V OR NOT VisTRUE:D(I'm assuming that you're unable to go to sleep exactly when the rating updates start.)
Haha. I didn't realize my dilemma was a boolean equation :p
I think he meant: Yes, you should go to sleep before or after the rating update.
Because you should go to sleep at some point, right?
I suppose to think that the contest will be unrated.
Isn't it only me who had really slow and rare access to the website? Almost all my friends say that everything was ok and it was only my problem.
Your friends are lying to you to collect some thumbs up!
How to solve C? Tried to implement some DP on a tree, but answer on the 3rd sample was slightly incorrect.
Yep, DP on a tree. On probabilities that the answer is (trivial lower bound + k).
" but answer on the 3rd sample was slightly incorrect." — no, it wasn't.
I think he means his own code's answer :D
Lol, during the round there was some announcement stating that answer to third sample is really correct, so I thought that it related to that :P.
The idea here is to change each # in such a way to get a correct sequence of brackets, correct sequence is "()", and then "(correct)" or "()correct" or "correct()", I think I didn't miss any.
If we want to get correct sequence of brackets on each index i starting from 0, we should have the number of ')'-s less or equal to number of '('-s and these two numbers should be equal for the whole string. Here we should keep in mind that we should change each # with at least one of ')'. So we can replace each # with only one ')' and we can replace the right most # with such number of ')'-s that the number of ')'-s will be equals to number of '('-s in the whole string. My solution was this, I hope it will pass system testing.
He asked for DIV-1 C, which is our E.
Yes, I was too late to see it! :D But anyway I'll leave it there.
why testing is stopped?
I solved E, but read it in a wrong way: I thought rectangles could not intersect. I understood I needed a segment tree, but couldn't wrote it in time. Now it's working with stress test. :( I think it made the problem worse. When you've already got the idea, got the formula for d[x][y], then for rectangle it should be ok. I don't see any difference (except the time). It could be very easy to write mathematical problem. I haven't read all the problems but I like all I've seen.)
Количество символов '(' должно равнятся количеству символов ')' для каждого i или для всей строки?
Равняться для всей строки.
Очевидно для всей строки, потому что нельзя составить правильную скобочную последовательность нечетной длины
Interesting question: How can somebody get runtime error on Div2-C??
Well, for example non-terminated C-string, or too small allocated size for char buffer...
.
pretty hard!!! ( And challenging. )
Е-шечку никто не решил(
You really have to maintain server stability in the last 10 mins
Damn, failed on 47th test... Is there any way to download the tests to see what went wrong?
Yes. Here is your submission together with the test it fails on: http://codeforces.net/contest/495/submission/9114817
The answer was 1000000006, and notice you subtract one to find the answer, so your dp held 1000000007 which was reduced to 0 (mod 10^9+7), and subtracting 1 gave -1.
Be careful with negative numbers and mods.
Hahahah, that was a nice find. Thank you :)
vishwacs111, thank you for hacking my C!
nice contest got +132 :D:D:D + hacked 5 users second problem in div2:D:D:D
У меня была рабочая версия задачи C, которую я не смог послать, потому что последние 10 минут сервер лежал. Оставлять этот контест рейтинговым — свинство.
Буду, вероятно, заминусован, но не могу не отметить, что авторы мудаки и задачи у них соответственные. Чем такое придумывать, лучше б вообще ничего не предлагали.
Почему? Мне задачи показались нормальными.
Во-первых, скачок сложности со 2 на 3 задачу. Во-вторых, слабые претесты допустили ситуацию, что кто-то исключительно на одних взломах обгоняет людей, честно сдавших 2 задачи. В третьих, из-за этих самых слабых претестов у меня упала 2я, что меня, конечно, слабо порадовало.
бебебе
На следующем таком же контесте не дадут сделать 12 взломов — по другому запоешь.
12 вообще-то
Тащемта, согласен хотя бы с тем, что тест с 1000000006 можно и в претесты включить. Задача не такая уж простая, чтобы у работающих решений снимать баллы за такую фигню.
Тащемта, а что тогда предлагается включать в (тесты — претесты), если не крайние случаи?
У меня всегда находится, на чем упасть решению :D
Но если серьёзно, мне кажется, обидно, когда это последняя задача из тех, которые вообще решило больше 30 человек, и она накрылась на вычислениях по модулю (которые ведь являются по сути лишь костылём над задачей для обрезания BigInt'ов, а не частью задачи).
Конкретно здесь было и КМП и не слишком тривиальная динамика. Т.е. было, на чём свалиться решению, прошедшему претесты. Если так хочется, чтобы участники на чём-нибудь свалились, можно было второй тест не делать тестом из условия. Я уверен, он пообрезал частных случаев поболее, чем -1 по модулю MOD.
Вот почему: http://codeforces.net/blog/entry/15134#comment-200784
И чем же Вам авторы так не угодили?
No luck — just skill
Isn't that a sign, that contest was totally nonadequate?
man i am going down and down and down need to come up
what is the difference between
long long ind = lower_bound (x2.begin(), x2.end(),i)-x2.begin(); if(x2[ind]>i){ind = ind-1;}
and
long long ind = upper_bound (x2.begin(), x2.end(),i)-x2.begin(); ind = ind-1;
?
Second one passed,first one didn't. I was trying to find largest element less than/equals to i in vector x2
What if ind was out of the array bounds?? This would make a problem.
but wouldn't that cause Runtime Error ? I got WA because of this
This is C++ not Java, out of array accesses result in "Undefined behavior" not strictly a runtime error!
If all elements of x2 are smaller than i, x2[ind] in first case is accessing past the end of the x2 vector.
but wouldn't that cause Runtime Error ? I got WA because of this
"wouldn't that cause Runtime Error?"
Why do you ask questions that can be easily answered with a google search? :/ http://stackoverflow.com/questions/1239938/c-accesses-an-array-out-of-bounds-gives-no-error-why
I asked because before this I always got RE in such a case.
Thanks anyways
I never understand div 1 B problem statement, could someone explain it?
How many ways to get choose some substrings of T, so that they dont'intersect and each of them has S as substring.
thanks :D
What's worse than both your solutions failing? Your friend dropping to div-2 for 1 point.
1699 Rating! — http://codeforces.net/profile/rsunny rsunny next time macha!
Haha yeah I dropped to 1697, thats mighty close too :D
Btw cheers! We're both aspiring Indian coders!
This contest was excellent!!!
not for this guy: http://codeforces.net/contest/494/standings/participant/3607564#p3607564
Hahahahaha :D! If I will ever want to complain about one of my problems failing systests I will remember that guy :D.
Объясните кто-нибудь почему в Div1C матожидание = 4,465.
Посчитаем вероятность того, что максимум равен какому-то значению.
Максимум точно не может быть меньше, чем 3.
Максимум равен 3 в том случае, если первая рекомендация не выполнена (это 0.5) и среди рекомендаций 2, 3, 5 не выполнено хотя бы две, вероятность этого 0.25(1 - 0.8)(1 - 0.9) + (1 - 0.25)0.8(1 - 0.9) + (1 - 0.25)(1 - 0.8)0.9 + (1 - 0.25)(1 - 0.8)(1 - 0.9) = 0.215, итого с вероятностью 0.5·0.215 = 0.1075 значение максимума равно 3.
Максимум равен 5 в том случае, если среди рекомендаций 1, 2, 3 и 5 выполнено ровно 3: (1 - 0.5)·0.25·0.8·0.9 + 0.5·(1 - 0.25)·0.8·0.9 + 0.5·0.25·(1 - 0.8)·0.9 + 0.5·0.25·0.8·(1 - 0.9) = 0.3925.
Максимум равен 6 в том случае, если выполнена каждая из рекомендаций 1, 2, 3, 5: вероятность этого равна 0.5 × 0.25 × 0.8 × 0.9 = 0.09.
В остальных случаях максимум равен 4: это 1 - 0.1075 - 0.3925 - 0.09 = 0.41.
Считаем матожидание: 3·0.1075 + 4·0.41 + 5·0.3925 + 6·0.09 = 4.465.
Спасибо!
dp'licious div 1 contest!
Couldn't code problem d in time and my a was buggy. I almost fell back to div2 LOL
What did just happen here? AC: 9122599 WA1: 9122592
http://codeforces.net/contest/494/submission/9117612
For some final tests, I think this should get WA.
Output
999999958.3334586600
Answer
1000000003.315735409
Checker comment
ok found '999999958.3334587', expected '1000000003.3157355', error '0.0000000'
Check this. Relative error is OK.
Thanks
That's because the relative error is less than 10 - 6.
I also noticed that for large inputs, even the trivial lower bound could get AC automatically... I wonder how the submissions could get affected by higher precision (and smaller ai-s).
judging system of codeforces is quite bad. Because in the contest time judges should provide all input/output testcases. When a coder gets Pretest Passed, he moves to other problem, but after contest he sometimes notice that the solution was wrong. If in the contest time he gets Wrong Answer he could get Accepted.
How about hacks?
No problem about hack. But judges should provide strong cases for every problem. After getting hack coder tries to solve it again in contest time.
If they provide all testcases when judging during a contest, nobody would be able to hack other peoples solution. You have to either figure the tricky testcases on your own or pray someone will hack you. This makes contests more exciting.
Yeah. Now It's clear to me. Thanks ddwebx bro..
I think -44 is worth melting for.....
I can't solve a problem, so the judging system is bad.
Cool story, bro.
I am a new programmer bloody bitch.........
Okay, sorry. You're a new programmer, so the judging system is bad.
The line — "I am a new programmer" was enough to make your point. The rest was unnecessary.
If for every code judge system tests all tests during the contest judging process will be too slow and it make some troubles during the contest,
Finally I reached EXPERT!!! :D
tourist 's 100th round!
Took off 2 zeros for rank!
Hamed and Malek two familiar people for inoi people
Iran contest is too hard..555555