### izban's blog

By izban, 7 years ago, translation,

Hello everyone!

This Sunday, on March 30 at 11:00 MSK (March 30 at 07:00 UTC), Codeforces Round #239 for both divisions participants will take place. Note the unusual time of the round.

The problems have been prepared by me. I want to thank Codeforces team: tasks coordinator Gerald Agapov (Gerald) for invaluable contribution to the preparation of tasks and Maria Belova (Delinur), who has translated the problems. Also thank to Niyaz Nigmatullin (niyaznigmatul) for testing.

I wish you all good luck and have a good weekend!

UPD: You can see score distribution at the problems page.

UPD2: You can find editorial here.

• +228

 » 7 years ago, # |   +5 Why is the time at 11:00 AM MSK rather than the usual 7:30 PM? Now the Americans won't be able to compete in the contest unless we stay up until 2AM or later in some parts
•  » » 7 years ago, # ^ |   0 I think it's because TopCoder SRM 614
•  » » » 7 years ago, # ^ |   +15 TopCoder SRM 614 will be held tonight, not Sunday.
•  » » 7 years ago, # ^ |   +15 For some people the time is inconvenient, for others it is convenient.
•  » » 7 years ago, # ^ |   +5 We have the same problem here, in Mongolia 19:30MSK is 23:30
•  » » 7 years ago, # ^ |   -26 I would say I'm in America, but I'm not American. Almost Americans won't care about this kind of competition, as well as Obama. In anyway, I will stay waiting and participate for this codeforces round.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +17 In Vladivostok,usual time is inconvenient like far-east countries,I think.
•  » » 7 years ago, # ^ |   +5 I woke up at 2:30 am and did pretty well; it's not impossible :)
 » 7 years ago, # |   -39 Если комментарий наберёт ровно 42 к концу контеста, опубликую крутую статью :)====================================If this comment will get exactly 42 to the end of the contest, I'll publish awesome blog entry :)
•  » » 7 years ago, # ^ |   +160 Is it ok to get 42 by absolute value? ;-)
•  » » » 7 years ago, # ^ |   -48 Yes, sure ;)If conscience allows it :)
•  » » 7 years ago, # ^ |   -39 -42 устроит? :)
•  » » » 7 years ago, # ^ |   -43 Ты не понимаешь комментарий на английском выше? Какая жалость.====================================You don't understand English comment right above? Such a pity.
•  » » 7 years ago, # ^ |   +6 So close...
•  » » » 7 years ago, # ^ |   +3 Not now :D
•  » » 7 years ago, # ^ |   +17 Just as promised.Link
 » 7 years ago, # | ← Rev. 2 →   +10 I think it coincides with March Lunchtime of Codechef :)
 » 7 years ago, # |   +13 This time 's good for Asian. In Viet Nam it 's 2:00 PM, so I can go some where at Sunday night :)
 » 7 years ago, # |   -11 I prefer weekend rounds. But it is probably due to NEERC this time.
 » 7 years ago, # |   -8 I think the time is reasonable for Asian people, now I can do it during the day.
 » 7 years ago, # | ← Rev. 2 →   +14 3:00 pm. It'll be so perfect time for Chinese participants.
 » 7 years ago, # | ← Rev. 2 →   +12 Please clarify the start time of the round. The link to the start time indicates the round will start at 10 am Bulgarian time while the counter says it will start at 9. Please note tonight whole europe will switch to summer time while AFAIK Russia no longer switches the clock. Could you please clarify the time in GMT to avoid confusion?EDIT: please note that after my comment the authors did at the start time in UTC.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 Actually both times point to 10am Bulgarian time after the switch which makes sense. Still please post the time in GMT for people who do not know that in Moscow no switch to summer time will happen.
 » 7 years ago, # |   +1 Good Luck for Everyone
 » 7 years ago, # |   +3 since only 2 minutes left for round to start, can u please post the score distribution?
 » 7 years ago, # | ← Rev. 2 →   +5 Hello. Please understand me, I am new to the site and I don't know where to post and I'm not a genius when it comes to English. What is the leg of length?
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 It means side of the triangle with given length (note that we generally exclude the hypotenuse). Only consider base and height.
•  » » 7 years ago, # ^ |   0 Leg = one of the 2 shorter sides.Leg of length a = the length of that leg is a.
 » 7 years ago, # |   0 Sad day for hackers.
•  » » 7 years ago, # ^ |   +15
•  » » » 7 years ago, # ^ |   0 DIV 2. Problem A, B I was talking about. :)
 » 7 years ago, # |   +17 I figured the tricky case for A but somehow couldn't hack for the entire contest :(I have tried using Chrome and IE in Windows, Chrome and Firefox in Linux. All I saw is a spinning black circle and unresponsive "Hack" button.What is the flash player version I should have? Or is anyone having the same problem?
 » 7 years ago, # |   +19 Wow fast system test.
•  » » 7 years ago, # ^ |   0 wonder if this will happen again!
•  » » » 7 years ago, # ^ |   0 Well, ratings don't need to be updated really fast, unlike the systest. It's the place in the ranklist that's keeping us on edge; when we know it, we can estimate the rating change, but the exact value doesn't matter so much.I guess people are used to superfast rating changes from TC. That's one of TC's biggest pluses (although it still doesn't balance out the Bad Idea Arena).Of course, taking a week just to update ratings is not OK, like some sites do.
•  » » » » 7 years ago, # ^ |   0 yes i guess ur right. sorry if i offended anyone. anyway, today ratings were updated much faster. :)
 » 7 years ago, # |   +16 So close! 46th...I know I can't be moved up the ranklist for no reason. But can I be moved down? Just 1 place, plz :D
•  » » 7 years ago, # ^ |   +20 Why do you want my place? :P
•  » » » 7 years ago, # ^ |   +5 Because it's 47th! (42nd is fine too, but that'd require moving up) :D
•  » » » » 7 years ago, # ^ |   +5 You know, 46=47-4/4, it is a little bit lucky too.
•  » » » » » 7 years ago, # ^ |   +22
•  » » 7 years ago, # ^ |   0 is 47 ur lucky number or something? :D
 » 7 years ago, # |   0 hussh.. Problem B div1 was easier than problem A.. :(
 » 7 years ago, # | ← Rev. 4 →   0 Very nice problems ! Congrats to the author ! I loved problems C and D ( and finally got solved D ).
 » 7 years ago, # |   +6 Today was a good day for hacks (Div 1).
 » 7 years ago, # | ← Rev. 2 →   +4 I mistakenly read the answer instead of output, Sorry for inconvenience. I can not understand why is my answer wrong for this test case #33. I think that my answer is right, Any helps ??408 765My output is: YES 0 0 360 192 -360 675 System test checker says "wrong answer side of a triangle is parallel to OX or OY".
•  » » 7 years ago, # ^ |   +2 Because it's the correct answer, not yours.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Never mind. PraveenDhinwa mistook the answer for output.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 Yep, exactly. PraveenDhinwa posted the jury's answer for that test which is, of course, correct.
•  » » » » » 7 years ago, # ^ |   +1 Yes, I mistakenly took the jury output :(Actually I have considered this kind of test case while coding. I made a stupid comparison bug in Java, as this was 2nd time I was using Java.I made wrong comparison like the below given example:(Integer a = 3, b = 5; if (a == b) out.println ("matched");I missed the point that their references are being compared rather than values :(, Nice point to take care in future
 » 7 years ago, # |   +1 After system test fewer accepted problem A than B .. Seems that many don't figure out the third edge can't be parallel to x axis..Most programs failed on test: 20 15
 » 7 years ago, # |   +16 Too many hacks on A : /. kmjp reached 63rd place without solving any problem, because he got 15 hacks on A :P. It's a bad thing where there aren't any hacks but in my opinion so big number of people with >10 hacks is also undesirable. I suppose it's a hard task to make such pretests that some solutions can be hacked but not that big number of them :P.
•  » » 7 years ago, # ^ |   0 Only problem A is tricky here, if pretests are a little bit stronger then it will be a no hack contest..
•  » » » 7 years ago, # ^ |   0 not just A, even problem B had a few (~30) hacks!
 » 7 years ago, # | ← Rev. 2 →   +1 Div2 C: Can someone tell me why YES 0 0 12 9 -12 16 is not a valid triangle?Edit: got it6184905
•  » » 7 years ago, # ^ |   +1 This one is valid. But your ouput is: YES 0 0 9 12 -16 12
•  » » 7 years ago, # ^ |   +1 Your output YES 0 0 9 12 -16 12 
•  » » 7 years ago, # ^ |   0 Thank you both :)
 » 7 years ago, # |   +24 It seems the time limit of D was too tight. Many O(N^3) solutions timed out.
•  » » 7 years ago, # ^ |   +12 Hi, I think it's not. All our good solutions work <= 900, even Java solutions, even with n^3 memory. I think 3 times margin is enough. Of course there are some solutions with huge constant factor that shouldn't pass.
•  » » » 7 years ago, # ^ |   0 I guess the reason you making the TL so tight is to kill O(N^3 logN) solutions, but it doesn't work well: hereMaybe it'd be better to let O(N^3 logN) pass (and if you think it is too easy, we can use it as 1500p).
•  » » » 7 years ago, # ^ |   +8 In POI there's a rule that constraints should be as small as they can not to let worse solution pass and there also one that making a distinction between solutions differing by a log factor is probably pointless. I guess noboby will be hurt if TL would be increased/constraints would be decreased, so their solutions can pass, because since they are in O(n^3), they deserve to. I'm a follower of an idea that every two solutions in the same complexity are equivalent :P.
 » 7 years ago, # | ← Rev. 5 →   +45 Look at this pageThe last rated participation in this contest siIlycrosssillycross and tourist both won IOI gold medals...I wondered what siIlycross was doing...Failed on all the problems, even tried to hack tourist for many times on problem A...。。。But finally, I found that siIlycross and sillycross were different people > _
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 wonder how siIlycross managed to stay Master despite finishing last! :D
•  » » » 7 years ago, # ^ |   +1 It seems that there is some cap (different for different users), and your raiting can't decrease by more than ~100 points — does not matter how bad your performance is.For example, look at TMandzu or Zlobober.
•  » » » » 7 years ago, # ^ |   0 hmm, makes sense. i guess the maximum increase/decrease of rating depends on number of contests user has participated before current round. the higher this number, the smaller the "cap" by which rating can change.
 » 7 years ago, # | ← Rev. 2 →   0 Please help with my Div1 A submission 6179184.On test 34,on my computer,my solution can give the correct output: YES 0 0 75 180 432 -180 but on CF it gives NO.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I added 0. + to all sqrt's.6188507UPD Try to run your original code in "launch" using visual c++ 2010.
•  » » » 7 years ago, # ^ |   0 Thanks.I used TDM-GCC 4.7.1 on my computer,without -O2,I think that's the reason.
•  » » 7 years ago, # ^ |   +5 Precision error.
•  » » 7 years ago, # ^ |   +11 You should never work with floating point numbers when you can work with integers.
 » 7 years ago, # |   0 how to solve problem C in div1
•  » » 7 years ago, # ^ | ← Rev. 2 →   +38 I decompose a binomial coefficient for i > l into Take an array A[] whose j-th element is the k - j-th term of this sum (if i = l, then A[k] = 1 and A[j < k] = 0). When you increment i, A transforms into the array of its own suffix sums, because where the first term is A[j] of the original A and the second is A[j + 1] after the transformation, which is the recurrence describing suffix sums.This transformation is also additive — performing it on the sum of queries gives the same result as performing it on each of those queries separately and then summing up the results. That means you can use a sweepline with adding new queries (A[k] +  + ) and removing them (you need to subtract bin. coefficients from the corresponding terms of A).UPD: The exact formulas were wrong, also it wasn't prefix, but suffix sums. The confusion came about because I changed the indexing from the one used in my solution (6186385). Nevertheless, the original decomposition is unchanged.
•  » » » 7 years ago, # ^ |   0 This is a beautiful solution!
•  » » » 7 years ago, # ^ |   0 Good solution. But i still dont get how to save queries in each element and find the current element?
•  » » » » 7 years ago, # ^ |   0 Find the current element: sum up the terms of array A — it's the same as computing the sum above.Adding queries is trivial — just increment A[k] for the k of that query. When deleting queries, you'd need to subtract from A the values that would be there if you applied the same algorithm on only that one query — those are the bin. coefficients in the sum.
 » 7 years ago, # |   +25
 » 7 years ago, # |   0 it's very Thriller contest 4 me.............
•  » » 7 years ago, # ^ |   0 love U choochoolak..........
 » 7 years ago, # | ← Rev. 2 →   0 It was a nice contest. :) BTW can someone describe how to solve div-1 C? Edit : Sorry, I missed the Xellos comment.
•  » » 7 years ago, # ^ |   +1
 » 7 years ago, # |   +22 I got the email announcing this contest during (or after) the contest!
•  » » 7 years ago, # ^ |   0 i still havent got any email. hopefully i'll get it before the start of next contest (which is now less than 48 hours)! :D
 » 7 years ago, # |   0 Problem Div1 — A, Triangle.For input 5 5My program gives the following output. YES 2496 2497 2500 2500 2497 2496 I got Wrong answer. But two lengths of these three points are 5 and 5. Could anyone help me to find the place where I am doing mistake?
•  » » 7 years ago, # ^ |   +3 You don't have a right triangle.
•  » » » 7 years ago, # ^ |   +3 Got it.Thanks :)
 » 4 years ago, # |   0 Can someone explain the first testcase in proB div 2?