Hello!
We invite you to participate in Codeforces Round #253, which will take place on Thursday, June 19th at 19:30 MSK. The round will be held in both divisions.
It's my first Codeforces Round and I hope you will enjoy it!
Many thanks to Gerald for helping to prepare the round. Also I'd like to thank MikeMirzayanov for creating such a good platform. Also thanks to testers of this round: antonkov, Aksenov239, VArtem, subscriber, niyaznigmatul and to Delinur for translating statements.
Don't miss a chance to have fun of solving interesting problems!
UPD. Score distribution:
Div1: 500-1500-1500-2000-2500
Div2: 500-1000-1500-2500-2500
UPD2. The contest is over, thanks for participating!
Congtatulations to Div1 winners:
1) tourist
2) scott_wu
3) stevenkplus
3) gs12117
5) GlebsHP
And congratulations to Div2 winners:
1) tafit3
2) thnkndblv
3) MIT3
4) lucaslima
5) liuzhijian
My congratulations to tourist, only person who managed to solve all five problems, and only one who solved problem 442E - Gena and Second Distance!
You can find editorial here.
Early announcement, thanks for this!
Early announcement
-->
more up-vote!Comment regarding Early Announcement
-->
more up-vote!Comment regarding "Comment regarding Early Announcement
-->
more up-vote!"-->
more up-vote! :DIt's too hard to write something funny. So just down-vote me pls.
Why you down-vote me? Can't we make fun a little? :(
That would have led to an infinite loop :(
Actually my last comment have '37' down-vote. So anyone doesn't say "Comment regarding bla-bla-bla
-->
more up-vote!" :DHence No infinite loop. :)
break;
// thanksRepeating jokes usually aren't very funny, especially if they're formed by repeating someone else's joke.
such wisdom.
is it always necessary every time when the auther makes an early announcement someone writes a comment saying "wow early announcment"
I think, this is earliest announcement.
Hope we all get good grades
why so many down?
Maybe because programming contests aren't school, so there are no grades? (So it's a completely off-topic/spam comment.)
I think because he used "grades" instead of "ratings". Note that similar comment from the same person with correct word has been accepted AC.
I have a good answer for that, too :D
Consider the case when all participating users rank exactly according to their rating before the contest, and all participants were specialists initially. Then, since the participant has not been 'overtaken', his rating should not decrease.
All constructive ideas, comments and clarifications are welcome.
Well now i think it is because the probability of her hope being fulfilled is 0.000000000. Proving it is a good exercise of mathematical reasoning.
Please think that whether you wish is theoretically possible. That comment is down voted mainly because it was intended towards just commenting.
Hope rating++~~~ Enjoyable contest in Codeforces becomes one of my daily life~
agree. It becomes one of my daily life :)
me too,I really enjoy it,espically when my rating gets higher :)
Me too! I really hope improve myself and get the higher rating :)
me too. Rating up and down here, so enjoyable!
This is the second : tending to infinite loop in this page.
I dont want that every user comes here and contribute like this.
So, I hope this will break the flow :
break;
This comment does not wish any replies as then the brake will fail.
ok
The final exam is approaching.But It is always enjoyable to have a codeforces round.Hope all the participant can enjoy the round.
participate in contest can keep on the feeling of algorithm. And codeforces contest costs only 2 hours.
yes,really can not stand watching stand by but not participanting in this game
May the codeFORCEs be with you...during exam ;)
The same day with TopCoder SRM 625.
Topcoder
break
Codeforces
Thanks god there is no worldcup match that time!
Colombia VS Côte d'Ivoire
oops! I didn't see that!
So, too bad that there is a worldcup match that time :(
Too many contests in the exam days , hope there will be that much in the holiday
Expecting the problems to be based on footballers / football :)
maybe like this problem? ;)
^btw...speaking of football.....nice handle(yours) :)
Hope your first Codeforces Round will success and the problems are diversity and useful for everyone
hope everyone get higher rating !
I hope not. It would mean that there's something seriously wrong with the rating system, not to mention it'd be boring.
Last Codeforces round before ACM ICPC World Finals! (or not?)
I think it is yes for Div1 , but it is not necessary to stop Div2 contests during the World Finals
last few contests users ask why problem writer write "score distribution will announce later"
but here score distribution not mentioned at all he didn't say later or mention it.
I see very little point in writing "scrore distribution will be announced later" because it doesn't give readers any new information :)
Of course as early as we dicide everything about score distibutioin I'll add the information to the post.
orly? That phrase is at least more informative than this one: "Don't miss a chance to have fun of solving interesting problems!"
I am a new member of codeforces.. I wuld like to know regarding the concept of div 1 and div 2 What are they?? and in which of them do I belong ?
Any new contestant by default belongs to Div2. If you do good, and your rating increases over 1700, then you will be promoted to Div1. The rest you will figure out once you start participating regularly.
Hope I will make it to first division! It's the first time I am so close. Only 31 points...
Looking forward to the codeforces round and the WC match after the contest between england and uruguay
Can anyone explain what is meant by the score distribution Div1: 500-1500-1500-2000-2500
Div2: 500-1000-1500-2500-2500
There will be 5 problems and maximum points for each individual problem are 500-1500-1500-2000-2500.
Had a really great performance Topcoder SRM 625 a few hours ago ... hoping for same (or maybe better) performance in this codeforces round! GL & HF everyone!
Please can anyone upvote/downvote my comment ? I want to see what kind of notifications we get when our posts are upvoted or downvoted .
I'm a new contestant of codeforces so div 1 or div 2 which appropriate for me... ????
Since you clearly don't know that you're assigned a division based on your rating (and unrated means div2 automatically), it's clear that you're new :D
div2
div2
There was some problem . Xellos and aangairbender's comments were not visible when I replied .
Why don't you press F5 when you reply?
Does Div2 B have 1500 or 1000 points?
I really don't understand C div 2 problem statement and examples!!!
Can someone explain div2 B problem ?!
my brute force approach passed the system tests.
For all different substrings, I searched for the maximum possible value for
l
.I feel like I just took out my hack interest over the past 2 years... +4 mfw
Problem B Div2 was harder than usual! I also think D div2 was easier than C! Because it had more pretest passed submissions!
Very Hard Contest O.o , C — no idea, D-I hate statistics homeworks , E — wow what a problem, but no idea :(
It reminds me of #146div1.......
Hard contest :/ !!
AC :333,
How do you solve Div.1 B ? I see lots of people have solved it. I myself submitted something that will definitely get TLE on system testing. The solution eludes me. :/
sort by decreasing values and greedy algorithm
Can you prove this solution?..
The editorial's up, and the solution's there. Key idea of the solution: if a set S has , adding p to it increases the result proportionally to p (so we want to add the largest p).
dp[i][j], i — all taken count, j — last taken
[ Deleted ]
Ive got an easy idea for that ... but waiting until the final test :D
Editorial please...!
I hope system testing and rating update come quickly
Hard contest...please give editorial soon.
Problem C (div2) is hard to understand.
Can anyone give me solution for problem D div 2?
See editorial
I am in the same room with you~ how lucky~ When you hack others.. I felt quite scared!!!!!!!!
Well, your solution was safe... which can't be said about GodDammit. Hacked after lock, early on in the contest. Talk about choosing a bad name :D
It is so hard to become International master....sad....2049.....
the system testing is very quickly! good
Damn, why TL in D was so strict :/? My O(n log n) failed and I ended up on a 171st place instead of in TOP20 :/. Moreover, I wasn't the only one. There are many failed submissions because of TLE.
Same here. Got TLE for pascal solution 6921143. The same code receives AC in 390 ms on Delphi: 6923185.
Our Java solutions work something like 500ms... I don't think 4xJava solution time limit is strict.
Are you sure? This is ~1/3 of all submitted solutions during contest.
(Edited picture, thanks nic11)
Maybe
You can post the pic in HTML, you can resize there.
You can look at Aksenov239 solution: 6923989, or mine 6923978 with classes and recursion. Both of them work quite fast.
If you can't see this submissions, you can view it on pastebin: mine and by Aksenov239.
I don't know exact shape of testcases, but solution described in editorial does something like "do something until something" which can be estimated by O(n log n), maybe maxtests where easy cases where your solution worked faster? My solution works offline and takes teta(n log n) time and I'm not using anything which can make constant to significantly grow like set or maps. My space complexity is also O(n log n), but that shouldn't be the case. Is there anything really stupid I'm doing, which was a reason I got TLE http://codeforces.net/contest/442/submission/6917926 ?
And one more question — what is the point of setting such big constraints? Will anybody get hurt if n<=10^5 instead of 10^6? I guess not.
We have maxtests on which model solution works teta(n log n). Setting smaller limits always increases chances some solutions with wrong complexity pass.
But I'm really sorry that I forgot to include a maxtest in pretests.
Sometimes, it's impossible to make sure just all solutions with good complexity pass. As was clearly the case here...
I'm glad that swistakk solution got TL. And I will get hurt if coders like swistakk take top20 place.
Lol, that's pretty rude :P. I guess this is my award for whining about TLs while I should be grateful for preparing contest, but you know, receiving TLE in solution with optimal complexity (especially those without any complicated data structures) is always frustrating :P
Would you also get hurt if coders like me get second place on ACM ICPC WF ( ͡° ͜ʖ ͡°)?
I got TLE because I stupidly used heap to maintain 2 maximals and use cout to output.
I think the TL is fine, but it would be better to add maximal test case in pretest so we will know the code is not optimal enough.
Hm, I got AC after changing vectors to arrays (and 1e6 to 1e6 + 5 :P). I guess what's taking most of the time is doing n resizes to 23 and 23n resizes to 2 :P. I was also really close to exceeding memory limit (230 out of 256MB). Allocating that amount of memory is slower than I wanted it to be.
My solution of D div2 failed in test case 5 because i didn't use setprecision :(
Many many people missed D because of this :(
In the Ukraine and Russia this coders are named "Loh" or "Noob".
Many People missed that the error was 10^-9 and not 10^-6.
I feel that to give credit to the right technique for problem B (div1), the constraints should've been such that n < = 105
P.S.: After sorting the array of probablities, I just used a naive test-all-subarrays algorithm which passed.
Your O(N2) Solution couldn't pass N = 105 ;)
Anyway , I see the O(N) solution, I think 100 has been chosen nicely by author ... cause nobody have 105 firends who set problem !!!!
Mike Mirzayanov? :D
"Your O(N2) Solution couldn't pass N = 105 ;)"
-- This is precisely why I said that the constraints should be increased. I did not find the O(N) technique and was still able to solve it.
--I don't even feel like replying to what you wrote later on man. I'm out.
Div1 — B I got wrong answer at test 17.
only for this line : printf("%.10lf\n",1);
Some of you will be amused to see the output
my WA code
my AC code
shit happens :D
Printf expects double, you pass int. It's because of the compiler.
When I passed pretests on Div. 2 B, I thought I was the luckiest guy in the room(I was just playing with the code and it started giving right answers :D). Didn't pass the systest though...
Can someone suggest a book to study algorithms please? Which books did you use to learn them? Both Russian and English ones are acceptable ;)
Introduction to Algorithms by Cormen and other guys is my favourite one, although I've read only DP chapter...
thanks
Hi, In Div 1 — B I got wrong the case #31, however when I run it locally it works fine and give the correct answer. Does somebody now where may the problem be?
Have no idea why that is a problem, but after doing the following, it worked:
Thanks, I had always though that double and long double were identical in GNU C++!. I find rather surprising the huge difference between the result in one case and in another. Well next time I'll use long double if I can remember it!
You're welcome.
But have you got any clue to why the output is like that when using "double"?
And the more weird thing is this. I don't think it's a mere precision problem (not sure): http://ideone.com/31XMxJ
Anyway, I haven't looked carefully at it yet. Will probably do that on Sat. isA.
And something that may help explain the reason but haven't tried before is checking the assembly code outputted from the compiler. But of course, don't forget to use the same compiler & compiler flags as theirs. (Sorry if it's a noob note, I'm a little nooby so I assume everyone is like me :D)
More or less I have finally found it. It has something to do with he -O2 flag it seems to handle some comparisons in a different way, I suspect that it doesn't save mx to memory so it uses a value with more precision (long double?), which is lost whne saving to memory. The question is that the order in the priority queue is changed. But now for equal values of the first parameter the queue gives the result in reverse order which is wrong.
Possibly in your ideone output, when printing the output mx is saved into memory and that affects i's precision. (Well is an hypothesis)
So it is a bug in my code. That's good I don't want to lose my faith in GCC !! :-)
Yeah can some one tell me what is wrong with his solution?
I have some understanding problem about div1 D. About the 2 conditions, what I think are:
Am I understand the 2 conditions right? And how does these 2 conditions affect the problem ? Thanks.
Round Stats