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.
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
I think it's because TopCoder SRM 614
TopCoder SRM 614 will be held tonight, not Sunday.
For some people the time is inconvenient, for others it is convenient.
We have the same problem here, in Mongolia 19:30MSK is 23:30
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.
In Vladivostok,usual time is inconvenient like far-east countries,I think.
I woke up at 2:30 am and did pretty well; it's not impossible :)
Если комментарий наберёт ровно 42 к концу контеста, опубликую крутую статью :)
====================================
If this comment will get exactly 42 to the end of the contest, I'll publish awesome blog entry :)
Is it ok to get 42 by absolute value? ;-)
Yes, sure ;)
If conscience allows it :)
-42 устроит? :)
Ты не понимаешь комментарий на английском выше? Какая жалость.
====================================
You don't understand English comment right above? Such a pity.
So close...
Not now :D
Just as promised.
Link
I think it coincides with March Lunchtime of Codechef :)
This time 's good for Asian. In Viet Nam it 's 2:00 PM, so I can go some where at Sunday night :)
I prefer weekend rounds. But it is probably due to NEERC this time.
3:00 pm. It'll be so perfect time for Chinese participants.
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.
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.
Good Luck for Everyone
since only 2 minutes left for round to start, can u please post the score distribution?
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?
It means side of the triangle with given length (note that we generally exclude the hypotenuse). Only consider base and height.
Leg = one of the 2 shorter sides.
Leg of length a = the length of that leg is a.
Sad day for hackers.
Seriously?:) http://codeforces.net/contest/407/standings/page/1
DIV 2. Problem A, B I was talking about. :)
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?
Wow fast system test.
wonder if this will happen again!
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.
yes i guess ur right. sorry if i offended anyone.
anyway, today ratings were updated much faster. :)
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
Why do you want my place? :P
Because it's 47th! (42nd is fine too, but that'd require moving up) :D
You know, 46=47-4/4, it is a little bit lucky too.
is
47
ur lucky number or something? :Dhussh.. Problem B div1 was easier than problem A.. :(
Very nice problems ! Congrats to the author ! I loved problems C and D ( and finally got solved D ).
Today was a good day for hacks (Div 1).
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 765
My 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".
Because it's the correct answer, not yours.
Never mind. PraveenDhinwa mistook the answer for output.
Yep, exactly. PraveenDhinwa posted the jury's answer for that test which is, of course, correct.
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
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
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.
Only problem A is tricky here, if pretests are a little bit stronger then it will be a no hack contest..
not just A, even problem B had a few (~30) hacks!
Div2 C: Can someone tell me why
is not a valid triangle?
Edit: got it
6184905
This one is valid. But your ouput is: YES 0 0 9 12 -16 12
Your output
Thank you both :)
It seems the time limit of D was too tight. Many O(N^3) solutions timed out.
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.
I guess the reason you making the TL so tight is to kill O(N^3 logN) solutions, but it doesn't work well: here
Maybe 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).
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.
Look at this page
The last rated participation in this contest siIlycross
sillycross 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 > _ <
It's hard to distinguish “I”(upper i) and "l"(lower L) sometimes on Codeforces...
wonder how siIlycross managed to stay Master despite finishing last! :D
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.
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.
Please help with my Div1 A submission 6179184.On test 34,on my computer,my solution can give the correct output:
but on CF it gives NO.
I added 0. + to all sqrt's.
6188507
UPD Try to run your original code in "launch" using visual c++ 2010.
Thanks.I used TDM-GCC 4.7.1 on my computer,without -O2,I think that's the reason.
Precision error.
You should never work with floating point numbers when you can work with integers.
how to solve problem C in div1
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.
This is a beautiful solution!
Good solution. But i still dont get how to save queries in each element and find the current element?
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.
Round Stats & Rating change
it's very Thriller contest 4 me.............
It was a nice contest. :) BTW can someone describe how to solve div-1 C? Edit : Sorry, I missed the Xellos comment.
I already did
I got the email announcing this contest during (or after) the contest!
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
Problem Div1 — A, Triangle.
For input 5 5
My program gives the following output.
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?
You don't have a right triangle.
Got it.
Thanks :)