### matrix's blog

By matrix, 4 years ago, ,

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.

•
• +383
•

 » 4 years ago, # | ← Rev. 6 →   +11 wow :) iranian contest I love them :)
 » 4 years ago, # |   +30 Matrix your graph is awesome and very motivated
•  » » 4 years ago, # ^ |   -10 Maybe there will be problem about matrix/matrices this round!
•  » » 4 years ago, # ^ |   -6 Its the opposite of the identity matrix :D
•  » » 4 years ago, # ^ |   +2 I hope that someday my graph becomes like that too!
 » 4 years ago, # | ← Rev. 5 →   -44 Our special thanks goes to mruxim for skipping this round just because we needed a tester
 » 4 years ago, # |   +17 "Please don't note anything since the time is the usual time of contests."
 » 4 years ago, # | ← Rev. 6 →   -63 Happy coding
•  » » 4 years ago, # ^ | ← Rev. 2 →   -42 I got -14 after smth like that (I was gray too). But also, I got +184 rating)
•  » » 4 years ago, # ^ |   0 The most intriguing fact about 282, however, is it is the number of planar partitions of 9.
•  » » 4 years ago, # ^ |   -23 The more you know ↑
•  » » 4 years ago, # ^ |   -12 What ? 2+2+2==8? Are you kidding me ?
•  » » 4 years ago, # ^ |   0 Yeah, and 282 is permutation of digits in number 228. So awesome.
•  » » » 4 years ago, # ^ |   -15 282 is divisible by two SO AWESOME
•  » » » 4 years ago, # ^ |   -19 282 is also a funny article of russian Criminal Code.
•  » » 4 years ago, # ^ |   -19 Amazing!!! Did you know that it's divisible by 3... :| what a amazing number.... :|
•  » » » 4 years ago, # ^ |   -12 Yes... and its divisible by 1 too So damn awesome
•  » » » » 4 years ago, # ^ |   -23 зануда
•  » » » 4 years ago, # ^ |   -13 so interesting!
 » 4 years ago, # |   -7 hope to see a nice problem-set and rating growth :)
 » 4 years ago, # |   0 This will be excellent preparation for the USACO December Contest.
 » 4 years ago, # | ← Rev. 2 →   -6 Zlobober has a great contribution in almost every contest. Thanks bro.. :)
 » 4 years ago, # |   -6 Have fun and good luck to all of you.
 » 4 years ago, # |   0 Good luck everybody!
 » 4 years ago, # | ← Rev. 3 →   +38 Codeforces really should think about some additional promotion, today I've found topcoder easter egg in locker room
•  » » 4 years ago, # ^ |   +3 We had these in our dormitory shower.
 » 4 years ago, # |   -14 Yesss Mr Farbod :D
 » 4 years ago, # |   +19 Time for dreamoon :D
•  » » 4 years ago, # ^ |   +8 I think he will do it next round :D
 » 4 years ago, # |   +5 It will be a good contest ...
 » 4 years ago, # | ← Rev. 2 →   0 Hope for much [pure] math
•  » » 4 years ago, # ^ |   +37 For me more interesting when anybody have more chances to hack each other(I want low pretests!!!).
•  » » » 4 years ago, # ^ |   +1 Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.
•  » » 4 years ago, # ^ |   0 And I thought I was the only one
•  » » » 4 years ago, # ^ |   +9 i hate hacking ): I like contests like ICPC, where you know if your submission is right or wrong when you submit it.
 » 4 years ago, # |   +1 It will be a great contest.
 » 4 years ago, # |   +21 So happy for div.1 contest)))))
 » 4 years ago, # |   0 At last after 10 days !!!
•  » » 4 years ago, # ^ |   +2 hope more and more contests
 » 4 years ago, # |   +11 hope candidate master for every expert
•  » » 4 years ago, # ^ |   +4 me too
•  » » 4 years ago, # ^ | ← Rev. 2 →   +7 Hope and expert for all pupil (and all Specialist)!
•  » » » 4 years ago, # ^ |   +4 and all grey
•  » » » » 4 years ago, # ^ |   +9 Did you mean Newbie?
 » 4 years ago, # |   +17 Wanna be Blue.... Gonna be White... -_-
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 Did you mean grey?
•  » » » 4 years ago, # ^ |   +13 ya.. Grey..
•  » » » 4 years ago, # ^ |   +40 It's possible to be white. See worse's graph.
•  » » » » 4 years ago, # ^ |   +3 Everything is possible
•  » » » » » 4 years ago, # ^ |   0 Nope...Try to get brown colour :P
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   +42 You don't understand why people sometimes want to do random stuff for fun?
 » 4 years ago, # |   0 i am in a good mood
 » 4 years ago, # |   +8 it is my first time for div.1.....
 » 4 years ago, # |   +4 I just want get a purple handle in this round~
•  » » 4 years ago, # ^ |   +1 Best wishes! Good Luck && Have Fun!
 » 4 years ago, # |   0 I hope this contest will bring me from unhappiness...... I even suspect whether coding is suitable for me...
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   0 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!
 » 4 years ago, # |   +19 1750 points. O_O Rly?
 » 4 years ago, # |   -8 "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
 » 4 years ago, # |   0 CF #282We hack as we could
 » 4 years ago, # | ← Rev. 3 →   +3 Problems A, B and C are easy; but problems D and E are difficult ! (in Div. 2) There isn't any normal problem :D
 » 4 years ago, # |   +9 Good Bye div1)
 » 4 years ago, # |   +35 correct score distribution (div. 1): 500 — 1500 — 2500 — 2500 — over9000
 » 4 years ago, # |   0 thanks a lot for nice problem :)
 » 4 years ago, # |   0 last 10 minutes, server was down. I could hack 10+ solutions but...
•  » » 4 years ago, # ^ |   0 Also I could have hack some solutions
 » 4 years ago, # |   +2 Woah, wasn't able submit my solution to A because codeforces wouldn't load. :(
 » 4 years ago, # |   +11 A div1 / C div2: (#( Answer: -1 WA: 2 
•  » » 4 years ago, # ^ |   0 Come across this comment, when suddenly my div2 C failed system test. What a coincidence. But really, I didn't notice that case!
•  » » » 4 years ago, # ^ |   0 Well, i am not alone in this planet :/
 » 4 years ago, # | ← Rev. 7 →   +26 fail of the yearA: 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 :(
 » 4 years ago, # |   0 What's the hacking test case for Div2A?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +4 Here was something unrelated. Keep scrolling.
•  » » » 4 years ago, # ^ |   0 I asked for Division 2
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 4 years ago, # ^ |   0 I accidentaly took 3 instead of 4 for 5 :/
•  » » » 4 years ago, # ^ |   0 That's for Div2 C/Div1 A :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 [2, 7, 2, 3, 3, 4, 2, 5, 1, 2]-if something from this list is not true
•  » » 4 years ago, # ^ |   0 It depends on the code. Some people miscalculated the number of probabilities for a simple digit.
 » 4 years ago, # |   0 Server Problem,vary painful.
 » 4 years ago, # |   0 What's wrong with test 6 in D, my stress test doesn't reveal any problems =(
•  » » 4 years ago, # ^ |   0 Check all modulo operations carefully, especially with negative numbers.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Eh at least now my stress is giving different results, but I can't find the mistake =(
 » 4 years ago, # |   0 Last 10 minutes :(
 » 4 years ago, # |   +31
•  » » 4 years ago, # ^ |   +5 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.
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   0 Sadly, this time too, Codeforces went down in the last ten minutes. solved problem C but couldn't submit :(
 » 4 years ago, # |   +11 please improve the server or limit the contestants number !!!!
 » 4 years ago, # |   0 Any idea about how to solve Div-1 B?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » 4 years ago, # ^ |   0 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 bedp[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)
 » 4 years ago, # |   +4 Good bye, Blue. Welcome Green, again.
 » 4 years ago, # |   -10 Я один столкнулся с тем, что, пытаясь взломать, при открытии чужого решения, открывается окно с посылками, само решение не открывается, ссылку с решением, на которую можно нажать тоже нет, в итоге взламывать невозможно? Так было вначале, потом удалось таки один раз взломать, потом тоже самое до конца контеста. Поведение одно и тоже на Ubuntu (Chrome и FF) и на Win8 (Chrome).Я конечно и сам залажал контест, но невозможность взламывать тоже как-то выбила из колеи.Ответы жюри:"У вас должен быть установлен Flash. Некоторые плагины могут резать Flash, считая баннером. Попробуйте так же воспользоваться другим браузером или очистить кэш/cookies.""В итоге ведь получилось произвести взлом? Остальные участники не жалуются, проблема где-то на вашей стороне.""Мы не можем ничем помочь."
•  » » 4 years ago, # ^ |   -8 У меня каждый второй раз открывалось только окно для взлома, без решения. Firefox 34, Win7. З.Ы. Это нормально, что я не могу переключить у себя галочку "по-английски" на "по-русски", отвечая на этот комментарий?
•  » » 4 years ago, # ^ |   0 да, было такое. и ещё за 10 минут удалось взглянуть только на 4 решения.
 » 4 years ago, # |   +45
 » 4 years ago, # |   +13 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...
•  » » 4 years ago, # ^ |   +24 The answer is: yes.
•  » » » 4 years ago, # ^ |   +8 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.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +12 The answer to V OR NOT V is TRUE :D(I'm assuming that you're unable to go to sleep exactly when the rating updates start.)
•  » » » » » 4 years ago, # ^ |   +5 Haha. I didn't realize my dilemma was a boolean equation :p
•  » » » » 4 years ago, # ^ |   +10 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?
•  » » 4 years ago, # ^ |   +4 I suppose to think that the contest will be unrated.
•  » » » 4 years ago, # ^ |   +44 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.
•  » » » » 4 years ago, # ^ |   +19 Your friends are lying to you to collect some thumbs up!
 » 4 years ago, # |   +8 How to solve C? Tried to implement some DP on a tree, but answer on the 3rd sample was slightly incorrect.
•  » » 4 years ago, # ^ |   0 Yep, DP on a tree. On probabilities that the answer is (trivial lower bound + k).
•  » » 4 years ago, # ^ |   -34 " but answer on the 3rd sample was slightly incorrect." — no, it wasn't.
•  » » » 4 years ago, # ^ |   +31 I think he means his own code's answer :D
•  » » » » 4 years ago, # ^ |   +11 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 4 years ago, # ^ |   0 He asked for DIV-1 C, which is our E.
•  » » » » 4 years ago, # ^ |   0 Yes, I was too late to see it! :D But anyway I'll leave it there.
 » 4 years ago, # |   +4 why testing is stopped?
 » 4 years ago, # |   0 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.)
 » 4 years ago, # |   0 Interesting question: How can somebody get runtime error on Div2-C??
•  » » 4 years ago, # ^ |   +6 Well, for example non-terminated C-string, or too small allocated size for char buffer...
 » 4 years ago, # | ← Rev. 2 →   0 .
 » 4 years ago, # |   0 pretty hard!!! ( And challenging. )
 » 4 years ago, # |   0 You really have to maintain server stability in the last 10 mins
 » 4 years ago, # |   0 Damn, failed on 47th test... Is there any way to download the tests to see what went wrong?
•  » » 4 years ago, # ^ |   0 Yes. Here is your submission together with the test it fails on: http://codeforces.ru/contest/495/submission/9114817
•  » » 4 years ago, # ^ |   +3 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.
•  » » » 4 years ago, # ^ |   0 Hahahah, that was a nice find. Thank you :)
 » 4 years ago, # |   0 vishwacs111, thank you for hacking my C!
 » 4 years ago, # |   0 nice contest got +132 :D:D:D + hacked 5 users second problem in div2:D:D:D
 » 4 years ago, # |   +69 No luck — just skill
•  » » 4 years ago, # ^ |   0 Wow,your graph !Impresive!
•  » » 4 years ago, # ^ |   -8 Isn't that a sign, that contest was totally nonadequate?
 » 4 years ago, # |   0 man i am going down and down and down need to come up
 » 4 years ago, # |   0 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
•  » » 4 years ago, # ^ |   0 What if ind was out of the array bounds?? This would make a problem.
•  » » » 4 years ago, # ^ |   0 but wouldn't that cause Runtime Error ? I got WA because of this
•  » » » » 4 years ago, # ^ |   +11 This is C++ not Java, out of array accesses result in "Undefined behavior" not strictly a runtime error!
•  » » 4 years ago, # ^ |   0 If all elements of x2 are smaller than i, x2[ind] in first case is accessing past the end of the x2 vector.
•  » » » 4 years ago, # ^ |   0 but wouldn't that cause Runtime Error ? I got WA because of this
•  » » » » 4 years ago, # ^ |   +2 "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
•  » » » » » 4 years ago, # ^ |   0 I asked because before this I always got RE in such a case.Thanks anyways
 » 4 years ago, # |   +15 I never understand div 1 B problem statement, could someone explain it?
•  » » 4 years ago, # ^ |   +1 How many ways to get choose some substrings of T, so that they dont'intersect and each of them has S as substring.
•  » » » 4 years ago, # ^ |   0 thanks :D
 » 4 years ago, # |   0 What's worse than both your solutions failing? Your friend dropping to div-2 for 1 point.1699 Rating! — http://codeforces.com/profile/rsunny rsunny next time macha!
•  » » 4 years ago, # ^ |   +1 Haha yeah I dropped to 1697, thats mighty close too :DBtw cheers! We're both aspiring Indian coders!
 » 4 years ago, # |   +3 This contest was excellent!!!
•  » » 4 years ago, # ^ |   +39
•  » » » 4 years ago, # ^ |   +17 Hahahahaha :D! If I will ever want to complain about one of my problems failing systests I will remember that guy :D.
 » 4 years ago, # |   +5 dp'licious div 1 contest!
 » 4 years ago, # |   0 Couldn't code problem d in time and my a was buggy. I almost fell back to div2 LOL
 » 4 years ago, # |   +5 What did just happen here? AC: 9122599 WA1: 9122592
 » 4 years ago, # | ← Rev. 3 →   +8 http://codeforces.com/contest/494/submission/9117612For some final tests, I think this should get WA.Output999999958.3334586600Answer1000000003.315735409Checker commentok found '999999958.3334587', expected '1000000003.3157355', error '0.0000000'
•  » » 4 years ago, # ^ |   +18 Check this. Relative error is OK.
•  » » » 4 years ago, # ^ |   0 Thanks
•  » » 4 years ago, # ^ |   +8 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).
 » 4 years ago, # |   -55 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.
•  » » 4 years ago, # ^ |   +12 How about hacks?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -17 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.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 Yeah. Now It's clear to me. Thanks ddwebx bro..
•  » » » » » » 4 years ago, # ^ |   +10 I think -44 is worth melting for.....
•  » » 4 years ago, # ^ |   +8 I can't solve a problem, so the judging system is bad.Cool story, bro.
•  » » » 4 years ago, # ^ |   -11 I am a new programmer bloody bitch.........
•  » » » » 4 years ago, # ^ |   +45 Okay, sorry. You're a new programmer, so the judging system is bad.
•  » » » » 4 years ago, # ^ |   -8 The line — "I am a new programmer" was enough to make your point. The rest was unnecessary.
•  » » 4 years ago, # ^ |   0 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,
 » 4 years ago, # |   +3 Finally I reached EXPERT!!! :D
 » 4 years ago, # |   0 tourist 's 100th round!Took off 2 zeros for rank!
 » 4 years ago, # |   -11 Hamed and Malek two familiar people for inoi people
 » 4 years ago, # |   -9 Iran contest is too hard..555555