### qwerty787788's blog

By qwerty787788, 6 years ago, translation,

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) gs12117

5) GlebsHP

And congratulations to Div2 winners:

1) tafit3

3) MIT3

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.

• +458

 » 6 years ago, # |   +12 Early announcement, thanks for this!
•  » » 6 years ago, # ^ |   +51 Early announcement --> more up-vote!
•  » » » 6 years ago, # ^ |   +23 Comment regarding Early Announcement --> more up-vote!
•  » » » » 6 years ago, # ^ |   -30 Comment regarding "Comment regarding Early Announcement --> more up-vote!" --> more up-vote! :D
•  » » » » » 6 years ago, # ^ |   0 It's too hard to write something funny. So just down-vote me pls.
•  » » » » » » 6 years ago, # ^ |   -59 The comment is hidden because of too negative feedback, click here to view it
•  » » » » » 6 years ago, # ^ |   -37 Why you down-vote me? Can't we make fun a little? :(
•  » » » » » » 6 years ago, # ^ |   +11 That would have led to an infinite loop :(
•  » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   -27 Actually my last comment have '37' down-vote. So anyone doesn't say "Comment regarding bla-bla-bla --> more up-vote!" :D
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 4 →   +4 Hence No infinite loop. :)break; // thanks
•  » » » » » » 6 years ago, # ^ |   +6 Repeating jokes usually aren't very funny, especially if they're formed by repeating someone else's joke.
•  » » » » » » » 6 years ago, # ^ |   +6 such wisdom.
•  » » 6 years ago, # ^ |   +14 is it always necessary every time when the auther makes an early announcement someone writes a comment saying "wow early announcment"
•  » » » 6 years ago, # ^ |   0 I think, this is earliest announcement.
 » 6 years ago, # |   -26 Hope we all get good grades
•  » » 6 years ago, # ^ |   0 why so many down?
•  » » » 6 years ago, # ^ |   +1 Maybe because programming contests aren't school, so there are no grades? (So it's a completely off-topic/spam comment.)
•  » » » 6 years ago, # ^ |   -8 I think because he used "grades" instead of "ratings". Note that similar comment from the same person with correct word has been accepted AC.
•  » » » » 6 years ago, # ^ |   +6
•  » » » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +11 Hope rating++~~~ Enjoyable contest in Codeforces becomes one of my daily life~
•  » » 6 years ago, # ^ |   +1 agree. It becomes one of my daily life :)
•  » » 6 years ago, # ^ |   +8 me too,I really enjoy it,espically when my rating gets higher :)
•  » » » 6 years ago, # ^ |   0 Me too! I really hope improve myself and get the higher rating :)
•  » » » » 6 years ago, # ^ |   0 me too. Rating up and down here, so enjoyable!
•  » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » 6 years ago, # ^ |   +1 ok
 » 6 years ago, # | ← Rev. 2 →   +35 The final exam is approaching.But It is always enjoyable to have a codeforces round.Hope all the participant can enjoy the round.
•  » » 6 years ago, # ^ |   +1 participate in contest can keep on the feeling of algorithm. And codeforces contest costs only 2 hours.
•  » » 6 years ago, # ^ |   +1 yes,really can not stand watching stand by but not participanting in this game
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 May the codeFORCEs be with you...during exam ;)
 » 6 years ago, # |   +36 The same day with TopCoder SRM 625.
•  » » 6 years ago, # ^ |   0 Topcoder break Codeforces
 » 6 years ago, # |   +20 Thanks god there is no worldcup match that time!
•  » » 6 years ago, # ^ |   +22 Colombia VS Côte d'Ivoire
•  » » » 6 years ago, # ^ |   +47 oops! I didn't see that! So, too bad that there is a worldcup match that time :(
 » 6 years ago, # | ← Rev. 2 →   0 hope you wil enjoy the contest ! reminds me when a DR writes in the end of the exam "hard" "good luck " XD ! :3 :D
 » 6 years ago, # | ← Rev. 2 →   0 Too many contests in the exam days , hope there will be that much in the holiday
•  » » 6 years ago, # ^ |   0 to higher the rating fast =D wal3a ya druid =D
 » 6 years ago, # |   +12 Expecting the problems to be based on footballers / football :)
•  » » 6 years ago, # ^ |   +7 maybe like this problem? ;)
•  » » » 6 years ago, # ^ |   +16 ^btw...speaking of football.....nice handle(yours) :)
 » 6 years ago, # |   0 Hope your first Codeforces Round will success and the problems are diversity and useful for everyone
 » 6 years ago, # |   -15 hope everyone get higher rating !
•  » » 6 years ago, # ^ |   +52 I hope not. It would mean that there's something seriously wrong with the rating system, not to mention it'd be boring.
 » 6 years ago, # |   +47 Last Codeforces round before ACM ICPC World Finals! (or not?)
•  » » 6 years ago, # ^ |   +12 I think it is yes for Div1 , but it is not necessary to stop Div2 contests during the World Finals
 » 6 years ago, # |   +1 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.
•  » » 6 years ago, # ^ |   +21 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.
•  » » » 6 years ago, # ^ |   -7 orly? That phrase is at least more informative than this one: "Don't miss a chance to have fun of solving interesting problems!"
 » 6 years ago, # |   0 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 ?
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   +1 Hope I will make it to first division! It's the first time I am so close. Only 31 points...
 » 6 years ago, # |   0 Looking forward to the codeforces round and the WC match after the contest between england and uruguay
 » 6 years ago, # |   0 Can anyone explain what is meant by the score distribution Div1: 500-1500-1500-2000-2500Div2: 500-1000-1500-2500-2500
•  » » 6 years ago, # ^ |   +5 There will be 5 problems and maximum points for each individual problem are 500-1500-1500-2000-2500.
 » 6 years ago, # |   0 sadly this is coinciding with the world cup match :(
 » 6 years ago, # |   0 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!
 » 6 years ago, # |   +1 Please can anyone upvote/downvote my comment ? I want to see what kind of notifications we get when our posts are upvoted or downvoted .
 » 6 years ago, # |   0 I'm a new contestant of codeforces so div 1 or div 2 which appropriate for me... ????
•  » » 6 years ago, # ^ |   0 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
•  » » 6 years ago, # ^ |   0 div2
•  » » 6 years ago, # ^ |   -12 div2
•  » » » 6 years ago, # ^ |   0 There was some problem . Xellos and aangairbender's comments were not visible when I replied .
•  » » » » 6 years ago, # ^ |   0 Why don't you press F5 when you reply?
 » 6 years ago, # |   0 Does Div2 B have 1500 or 1000 points?
 » 6 years ago, # | ← Rev. 2 →   0 I really don't understand C div 2 problem statement and examples!!!
 » 6 years ago, # |   +1 Can someone explain div2 B problem ?!
•  » » 6 years ago, # ^ |   0 my brute force approach passed the system tests.For all different substrings, I searched for the maximum possible value for l.
 » 6 years ago, # | ← Rev. 2 →   +1 I feel like I just took out my hack interest over the past 2 years... +4 mfw
 » 6 years ago, # |   +1 Problem B Div2 was harder than usual! I also think D div2 was easier than C! Because it had more pretest passed submissions!
 » 6 years ago, # |   +32 Very Hard Contest O.o , C — no idea, D-I hate statistics homeworks , E — wow what a problem, but no idea :(
•  » » 6 years ago, # ^ |   0 It reminds me of #146div1.......
•  » » 6 years ago, # ^ |   0 Hard contest :/ !!
•  » » » 6 years ago, # ^ |   0 AC :333,
 » 6 years ago, # | ← Rev. 2 →   +10 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. :/
•  » » 6 years ago, # ^ |   +6 sort by decreasing values and greedy algorithm
•  » » » 6 years ago, # ^ |   +14 Can you prove this solution?..
•  » » » » 6 years ago, # ^ |   +8 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).
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 dp[i][j], i — all taken count, j — last taken for (int j = 0; j < n; ++j) { d[0][j] = p[j]; no[0][j] = (1 - p[j]); } for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { for (int k = j + 1; k < n; ++k) { double x = d[i][j] * (1 - p[k]) + no[i][j] * p[k]; if (x > d[i + 1][k]) { d[i + 1][k] = x; no[i + 1][k] = no[i][j] * (1 - p[k]); } } } } 
 » 6 years ago, # | ← Rev. 3 →   +5 [ Deleted ]
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Ive got an easy idea for that ... but waiting until the final test :D
 » 6 years ago, # |   0 Editorial please...!
 » 6 years ago, # |   0 I hope system testing and rating update come quickly
 » 6 years ago, # |   +8 Hard contest...please give editorial soon.
 » 6 years ago, # |   +1 Problem C (div2) is hard to understand.
 » 6 years ago, # |   0 Can anyone give me solution for problem D div 2?
•  » » 6 years ago, # ^ |   +8 See editorial
•  » » » 6 years ago, # ^ |   +3 I am in the same room with you~ how lucky~ When you hack others.. I felt quite scared!!!!!!!!
•  » » » » 6 years ago, # ^ |   0 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
•  » » » » » 6 years ago, # ^ |   0 It is so hard to become International master....sad....2049.....
 » 6 years ago, # |   0 the system testing is very quickly! good
 » 6 years ago, # |   +24 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.
•  » » 6 years ago, # ^ |   +8 Same here. Got TLE for pascal solution 6921143. The same code receives AC in 390 ms on Delphi: 6923185.
•  » » 6 years ago, # ^ |   +32 Our Java solutions work something like 500ms... I don't think 4xJava solution time limit is strict.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   0 Are you sure? This is ~1/3 of all submitted solutions during contest.(Edited picture, thanks nic11)
•  » » » » 6 years ago, # ^ |   +8 Maybe  
•  » » » » 6 years ago, # ^ |   +8 You can post the pic in HTML, you can resize there.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 6 years ago, # ^ |   0 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.com/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.
•  » » » » » » 6 years ago, # ^ |   0 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.
•  » » » » » » » 6 years ago, # ^ |   +8 Sometimes, it's impossible to make sure just all solutions with good complexity pass. As was clearly the case here...
•  » » » » » » 6 years ago, # ^ |   -14 I'm glad that swistakk solution got TL. And I will get hurt if coders like swistakk take top20 place.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +44 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
•  » » » » » » » 3 years ago, # ^ |   -48 Would you also get hurt if coders like me get second place on ACM ICPC WF ( ͡° ͜ʖ ͡°)?
•  » » » » 6 years ago, # ^ |   +1 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.
•  » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 My solution of D div2 failed in test case 5 because i didn't use setprecision :(
•  » » 6 years ago, # ^ |   0 Many many people missed D because of this :(
•  » » 6 years ago, # ^ |   -28 In the Ukraine and Russia this coders are named "Loh" or "Noob".
•  » » 6 years ago, # ^ |   +3 Many People missed that the error was 10^-9 and not 10^-6.
 » 6 years ago, # |   +1 I feel that to give credit to the right technique for problem B (div1), the constraints should've been such that n <  = 105P.S.: After sorting the array of probablities, I just used a naive test-all-subarrays algorithm which passed.
•  » » 6 years ago, # ^ |   +20 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 !!!!
•  » » » 6 years ago, # ^ |   +13 Mike Mirzayanov? :D
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +2 "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.
 » 6 years ago, # | ← Rev. 2 →   +18 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
•  » » 6 years ago, # ^ |   +1 shit happens :D
•  » » 6 years ago, # ^ |   0 Printf expects double, you pass int. It's because of the compiler.
 » 6 years ago, # |   0 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...
 » 6 years ago, # |   0 Can someone suggest a book to study algorithms please? Which books did you use to learn them? Both Russian and English ones are acceptable ;)
•  » » 6 years ago, # ^ |   +1 Introduction to Algorithms by Cormen and other guys is my favourite one, although I've read only DP chapter...
•  » » » 6 years ago, # ^ |   0 thanks
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   0 Have no idea why that is a problem, but after doing the following, it worked: Changed "mx"'s type to "long double". Then changed the specifier of printing to "%Lf", of course, because of that: http://www.cplusplus.com/reference/cstdio/printf/
•  » » » 6 years ago, # ^ |   0 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!
•  » » » » 6 years ago, # ^ |   0 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/31XMxJAnyway, 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)
•  » » » » » 6 years ago, # ^ |   0 But have you got any clue to why the output is like that when using "double"?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 !! :-)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yeah can some one tell me what is wrong with his solution?
 » 6 years ago, # |   0 I have some understanding problem about div1 D. About the 2 conditions, what I think are: All the colors of edges connected with the same vertex does not show up more than twice. If vertex i has an edge colored C, vertex j!=i has an edge colored the same C, then the path between i and j are all colored C. Am I understand the 2 conditions right? And how does these 2 conditions affect the problem ? Thanks.
 » 6 years ago, # |   +9