### MrNull's blog

By MrNull, history, 4 years ago, ,

Hello, Codeforces!

I have the pleasure to invite you to the round #343 which is going to take place on Saturday! This round is consisted of 5 problems and you have 2 hours (as usual) to solve them.

The problemsetters are Mohammad Amin Vahedinia (Me) (MrNull), Daneshvar Amrollahi (daneshvar_a) and Alireza Tofighi (AliRezaT). We would also like to thank Alireza Tofighi (AliRezaT) and Ali Asadi (Amoo) for testing this round and Ali Bahjati (LiTi) for helping us preparing this round.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, and, of course, MikeMirzayanov for unique Codeforces and Polygon platforms.

This contest's Hero is Famile Door and his friends who are preparing his birthday party!

UPDATE 1: Scoring Distribution is 500 — 1000 — 1750 — 2000 — 2500

UPDATE 2: Editorial is ready HERE

UPDATE 3: System Testing is finished you can see the standings here: standings

Congrats to the div2 Winners:

1. rakhashov.maksat

2. DarthMaul

3. TakeTheAegisIDontNeedIt

4. ykaya

5. abcdef6199

Also congrats to the div1 Winners:

1. Um_nik

2. anta

3. Nerevar

4. kmjp

5. gritukan

Best of luck to everyone!

• +257

 » 4 years ago, # |   +19 A contest by my friends !Will be interesting ...
 » 4 years ago, # | ← Rev. 4 →   -37 GL & HF
 » 4 years ago, # |   0 cool!!!
 » 4 years ago, # |   +17 happy birthday Mr. FamileDoor in advance...
 » 4 years ago, # |   +12 famile door :D :))))
 » 4 years ago, # |   +8 contest in the third consecutive day, it is mid-night at my time zone, however, I will try my best like all of you here and get advanced to div.1, wish all having good result!
 » 4 years ago, # |   +35 let's hope something realistic and not for exemple N invited (N<=1000000000000) or K candles on the bithday cake where (k<=1e50) !!
•  » » 4 years ago, # ^ |   +44 Indeed, nothing is realistic in Famile Door’s world :D
•  » » » 4 years ago, # ^ |   +3 I just hope Famile Door can explain his birthday party wishes in a short and direct way :D
 » 4 years ago, # |   +88
 » 4 years ago, # |   +28 For who doesn't know about Famile door, I have to say Famile door is a character in Kolah qermezi TV series (iranian TV for sure).
•  » » 4 years ago, # ^ |   +23
 » 4 years ago, # |   0 The last codeforces before the end of my holiday. better !!
 » 4 years ago, # |   0 Its recently that I have become purple, so I still like giving DIV 2 :D :P
 » 4 years ago, # | ← Rev. 5 →   -18 //
•  » » 3 years ago, # ^ |   0 LOL
 » 4 years ago, # |   +33 Cool ! An Iranian contest after months. Come on amd !
 » 4 years ago, # |   -10 Can anyone explain how the ratings go up and down for each coder?
•  » » 4 years ago, # ^ |   +4
 » 4 years ago, # |   +21 OMG! The hero of the contest is my favorite character! And also the authors are Iranians :) best contest ever!
 » 4 years ago, # | ← Rev. 3 →   +6 The flag of Iran and Famile dooor(I Love him) is up :) Famile dooor always say:"agar darbande dar manand,dar manand...":D ty all guys who prepare this contest <3
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 It's actually dar manand, by which he means: like a door.UPD: Although dar manand literally means they will not succeed.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 oh yeah,you are right ;) but i should say :" sir dagh.. :P"
•  » » » 4 years ago, # ^ |   0 :D
•  » » 4 years ago, # ^ |   -24
•  » » » 4 years ago, # ^ |   +16 How is this relevant to the discussion at hand? Sorry I don't read/speak Persian, so I can't really understand what's written over here :(
•  » » » » 4 years ago, # ^ |   +18 The last phrase of the poem is Famil Door's signature. I can't remember a single episode without him saying it.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 You are not alone.Most of the Iranians also don't understand it (like me).It is a poet of Hafez (a great poetry).Only the last line is important which is Famil Door's signature.UPD: And means if you have a problem and God don't help you, you won't be able to solve it...UPD 2: But I'm not sure about it!
 » 4 years ago, # |   -6 Thanks to authors! Famile Door :)^D
 » 4 years ago, # | ← Rev. 2 →   +3 I have to mention that Famil is a door-keeper and he is from a city called Door. I am sure we will see problems about opening and closing some doors :DI remember preparing a practice contest for my friends, in which I used Famil (and also his wife, Dooreh) for the contest character too! I was about to prepare a CF round, also about Famil. I wish I knew the authors of this round before they announce the contest! Maybe I can help them next time preparing some of easy problems :)
•  » » 4 years ago, # ^ |   -7 I used to think he is a relative of "aghaye mojri"(a far one :|)
 » 4 years ago, # |   +22 Iranian Contest style and statements are always funny.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 iranians are alyways happy and kindly
 » 4 years ago, # |   -6 so lately :( in my time.
 » 4 years ago, # |   +3 I Love he 's son :))
 » 4 years ago, # |   -49 OhAnother awful Iranian contest
•  » » 4 years ago, # ^ |   +44
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 1- you don't have to practice on this contest.2- when codeforces is going to run this contest , it means codeforces has considered that this contest has the least quality to be the contest of codeforces !
 » 4 years ago, # |   +61 This guy looks creepy af :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 Looks can be deceiving my friend ! He's one of the loveliest puppet characters I can think of.
 » 4 years ago, # |   +7 An attractive hero. So, let's hope an attractive contest :)
 » 4 years ago, # |   +1 I forgot to register LOL
 » 4 years ago, # |   0 wierd contest !!!
 » 4 years ago, # | ← Rev. 2 →   0 Very good contest!!! Thanks for the round...I liked problem C.
 » 4 years ago, # |   +4 A<=B
 » 4 years ago, # |   +4 Problem D LIS?
•  » » 4 years ago, # ^ |   +3 I used segment tree.
•  » » » 4 years ago, # ^ |   0 D can be solved using seg tree + coordinate compression . Didn't get the time to implement it :(
•  » » » » 4 years ago, # ^ |   0 No need for coordinate compression. D is easy this time.
•  » » » » 4 years ago, # ^ |   +11 For such problems, using fenwick tree is better since it takes much less time to implement. It is also easier to learn than segment tree, though not as universally applicable.
•  » » » » » 4 years ago, # ^ |   +8 I find BIT harder to understand, things are more intuitive when working with segment tree :)
•  » » » » » » 4 years ago, # ^ |   -7 Do you need to know how an aeroplane is made just to take a flight? Sometimes we must use the concept of blackboxing in life.
•  » » » » » » » 4 years ago, # ^ |   +18 I thought we are aeroplane makers.
•  » » » » » » » 4 years ago, # ^ |   +13 What you say is a really bad way of learning.
•  » » » » » » » » 4 years ago, # ^ |   0 LOL. So, you won't fly in an aeroplane unless you know how to make one in your backyard? Does Google maps show you every district, every house on every country on earth, or does does it blackbox most of it untill and unless you zoom in? I don't say bro, learning algorithms is bs, just mug them up but I say bro, BIT is really cool to use because the code is short, even if you find it confusing, you can still use it
•  » » 4 years ago, # ^ |   +5 Yes. LIS but on the volumes. Solution 1. Use Binary Search Solution 2. Use Segment Tree.
•  » » » 4 years ago, # ^ |   0 what is the LIS?
•  » » » » 4 years ago, # ^ |   0 Largest Increasing Subsequence
•  » » » » 4 years ago, # ^ |   0
•  » » » » » 4 years ago, # ^ |   0 And how this helped to solve problem? The longet do not mean the subsequence with the biggest sum...
•  » » » » » » 4 years ago, # ^ |   0 No, but try to maximize the volume with the concept of LIS.
•  » » » » 4 years ago, # ^ |   0 Longest Increasing Subsequence.
•  » » » » 4 years ago, # ^ |   0 Is it possible to get the LIS in nlogk , the best LIS? What modification do I need to do to get the LIS with max volume?
 » 4 years ago, # |   +2 Wasted alot of time in problem C trying to find out Catalan Numbers and bunch of nCr's. It ought to be DP. (Why the hell is DP so hard ?)
 » 4 years ago, # |   +15 I feel very happy because yesterday I was learned how to find LIS on good time with indexing tree and now I was solved problem D for my first time :)
 » 4 years ago, # |   +33 I tried hacking on D, with the fact that if PI has < than 17 digits after the decimal point the error will change. Example:1 10000 10000real answer = 3141592653589.793238401 (with PI's digits equal to 50) asymptote_ 's output = 3141592653590.0000000 (with PI's digits = 12)System verdict: Solution verdict: OK Checker: ok found '3141592653590.0000000', expected '3141592653590.0000000', error '0.0000000' Input: 1 10000 10000 Output: 3141592653590.0000000 Answer: 3141592653590.000061512 Time: 0 Memory: 901120 And the hack was Unsuccessful. . .
•  » » 4 years ago, # ^ |   +2 "Your answer will be considered correct if its absolute or relative error does not exceed 1e-6."here the relative error is less than 1e-6.
•  » » » 4 years ago, # ^ |   +1 But the authors solution gives wrong answer. The error is actually 0.206761599 which is larger than 1e-6.
•  » » » » 4 years ago, # ^ |   +2 Absolute yes, but relative error is less than 1e-12
•  » » » » » 4 years ago, # ^ |   +17 Ok, I understood. Thanks :)Lesson learned — Never hack about precision errors.
•  » » 4 years ago, # ^ |   +3 The error 10^-6 is relative, not absolute. Therefore, in this case is aproximately 3141593.0 difference allowed.
•  » » » 4 years ago, # ^ |   -8 I was too slow :D
 » 4 years ago, # |   +7 Codeforces servers were pretty good today :)
 » 4 years ago, # | ← Rev. 2 →   +11 Basically just calculate r2h for each cylinder, use this, and multiply the answer by Pi.
•  » » 4 years ago, # ^ |   +5 I googled that and I didn't find anything...
 » 4 years ago, # |   0 Any ideas why O(n log n) give TLE on pretest 6 in problem D ? My implementation : http://codeforces.com/contest/629/submission/16246075
 » 4 years ago, # |   +8 It didn't feel like a Div.2 contest.
•  » » 4 years ago, # ^ |   0 lol what did it feel like?
 » 4 years ago, # |   +12 I problem B , due to my bad internet connection , my code was submitted twice , so I got -50 coz of resubmission How did the judge accept the 2 submissions however they're similar (i.e. why there was no warning for the second submission )? submissions links : 16236771 16236745
•  » » 4 years ago, # ^ |   0 your first submission gets skipped
•  » » » 4 years ago, # ^ |   0 Sure but when I submit the same code twice ,the system should send me a warning (as usual) , this didn't happen in the contest :)
•  » » 4 years ago, # ^ |   0 same thing happened with me! mine was worse because i got three consecutive wrong answers! :(
 » 4 years ago, # |   +2 Really nice contest! :)I liked problem C very much, although I couldn't get all the pretests pass on time... next time, maybe!
 » 4 years ago, # |   +4 there might be a hack on c which s is like ")))))(((((" but i am not sure and i didn't solve the problem anyway.
 » 4 years ago, # |   +18 I always wonder why the System Test doesn't start immediately after the contests ends.
•  » » 4 years ago, # ^ |   +7 maybe someone need process the hack data.
 » 4 years ago, # |   0 I have no clue why my code to D does not work on pretest 6, can someone drop a hint? :D http://www.codeforces.com/contest/629/submission/16246045
 » 4 years ago, # |   +6 Problem C has nice hacking testcase (exceeded of memory) :)
•  » » 4 years ago, # ^ |   0 I used fixed memory. should I worry about MLE? :)
•  » » » 4 years ago, # ^ |   0 You got RTE, I saw my mistake 20 seconds before end and I couldn't change it :(
•  » » » » 4 years ago, # ^ |   0 Just needed to make a simple check diff>=MX to discard the access of the memory outside its limits. I fell from top 200 to top 500. a huge gap. :(AC : 16247743
•  » » 4 years ago, # ^ |   0 Why? 2.4*10^8 bytes in bss are allowed. Could you please explain what you mean by memory limit exceed? If you mean negative indexing, then a simple shift by N is enough
•  » » » 4 years ago, # ^ |   0 No, he defined matrix d[2000][2000] and it should be at least d[2000][10^5+2000].
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 No, it shouldn't. I got it AC with d[2000][2000]. just used a simple shift trick.
 » 4 years ago, # |   +12 Why on earth do problem setters make C harder than D!!!!
•  » » 4 years ago, # ^ |   0 I think it's about opinions because I was learned LIS yesterday and it looks hardly to me but C is dp. There is easy problem that asks how many sequences of given length are correct and it is the same dp but we need extra flag so it's no so hardly :)
•  » » » 4 years ago, # ^ |   0 I spent 1 hr 30 minutes on C and din't find the recurrence relation. What was the recurrence relation for p? I used dp[len][reqirement]=dp[len-1][requirement-1]{for an open parenthesis (.....}+ dp[len-2][requirement]{for ().....}
•  » » » » 4 years ago, # ^ |   +8 Look, my English is not very good but I will be trying to explain it in best way. The usual dp is dp[position][sum] and we try to move to next position with sum+1 and sum-1. Here we do the same dp[position][sum] but we need to know if we are being on left or right of S (I want to say if we are in P or Q) so flag F will show 0 if we are on left and 1 if we are on right. Each time we have some state(Pos,Sum,F) we try move to state(Pos+1,Sum+1,F) and state(Pos+1,Sum-1,F). And additional, if F is false, means we are on the left we try to move to the right but on same position with state(Pos,Sum+SumOfS,true). Only if we do it we need to know that Sum+MinSumOfS is not negative. Try to check my code, sorry for English :)
•  » » » » » 4 years ago, # ^ |   0 Could you give me a pastebin or ideone link to your code?
•  » » » » » » 4 years ago, # ^ |   0 Yes, I give you — http://pastebin.com/aBHAG8k9
•  » » » » » » » 4 years ago, # ^ |   0 Thanks! And your English isn't as bad as you think(although I should first check whether your explanation matches your code :) )
•  » » » » » » » » 4 years ago, # ^ |   0 No problem, I am hoping you understand it!
•  » » » » » 4 years ago, # ^ |   +5 great explaination .... now it looks very easy for me :) thank you
•  » » 4 years ago, # ^ |   +3 The difficulty of a problem varies from person to another person. Because we don't train on some topic with the same intensity. So it differs ! e.g. for me C was easier than D. So you demand the impossible from the problem setter when you say sort them by the difficulty equally for everyone.
•  » » » 4 years ago, # ^ |   0 Direct implementation of LIS is not even at D's level. Its a B or C.
 » 4 years ago, # |   +4 16242198 = 16242896 cheaters?
•  » » 4 years ago, # ^ |   0 Look my blog entry, I one time was reported two cheaters but nobody care unfortunately.
•  » » 4 years ago, # ^ |   0 The solution verdict for the unrated user of the two says "Skipped". What does that mean? Did the CF servers somehow discover that the two were identical solutions? :D
 » 4 years ago, # | ← Rev. 2 →   +8 I've seen problem D before : problem.The same solution will work for it just add a few lines of code .
 » 4 years ago, # |   0
 » 4 years ago, # |   +4 so many WAs on test case 37 for problem D! i wish some1 had hacked my solution
•  » » 4 years ago, # ^ |   -6 I wonder what is this test.
•  » » » 4 years ago, # ^ |   0 "strictly greater"
•  » » » » 4 years ago, # ^ |   0 Oooooooh. Man I never learn :(
•  » » » » 4 years ago, # ^ |   +1 I think it is round off error. Instead of using double for calculation, one should use long ie r^2*h. Then just before printing answer multiple by acos(-1).That way precision is maintained. I can't believe I made the mistake. Was supposed to be expert today :(
•  » » » » » 4 years ago, # ^ |   0 This one might be too.But I know some who used long long everywhere, but failed because of missing the word "strictly greater".
•  » » » » 4 years ago, # ^ |   0 How do you check for "strictly greater"?
•  » » » » » 4 years ago, # ^ |   +1 See my solution. I compress all areas (so they are less than N) and just take maximum in prefix (1...new_value[i] — 1). Here, -1 is for counting only strictly less numbers.
•  » » » » » 4 years ago, # ^ |   +1 You can index every r^2 * h from the given test in increasing order (sorted first), then check the elements with lower index, this way you will never use a cake with the same volume
 » 4 years ago, # |   +7 My accepted solution for problem C (practice) should give RE:100000 98000 (98000 open brackets)I corrected this problem in contest (incorrectly) and I got WA :'( while the original code received AcceptedKill me please
 » 4 years ago, # |   +4 When can I see the changed rating?
•  » » 4 years ago, # ^ |   0 I hope soon!!
 » 4 years ago, # |   +5 Can you congratulate top 10, not top 5, please :(
•  » » 4 years ago, # ^ |   0 Top 10 is too much. Top 9? XD
 » 4 years ago, # |   +16 So it turns out this code could pass all pretest in last task: ret += 1.0 * countLengthSum[b] / countNodes[b]; if(lca != a) ret += 1.0 * countLengthSum[b] / countNodes[b]; // <-- It should be a instead of b Why? It is because in all tests, if we choose 1 as the root then in each query(a,b) one of them is true: lca(a,b) will be a or b: so we will not run the code with bug both a, b are leaves: so countLengthSum[b] = countLengthSum[a] = 0. If we root the tree at 2 or 3 or a random one then pretest will catch this bug.So is this intended?
 » 4 years ago, # |   0 Worst feeling in the world: being 2 rating points lower than purple.
•  » » 4 years ago, # ^ |   0 1 point here :'(
•  » » » 4 years ago, # ^ |   0 I know that feel bro :'(
 » 4 years ago, # |   0 can any body explain problem C elaborately. I was not able to understand tutorials
 » 4 years ago, # |   0 Can someone help me find bug in my solution to C? I cant find it.http://codeforces.com/contest/629/submission/16248986i was comparing it to the um_nik's code and i cant see any differencehttp://codeforces.com/contest/629/submission/16235943
 » 4 years ago, # |   0 Could someone tell me what's wrong with my code? Please! I can't understand the bugs with only one for loop. :( 16249539
 » 4 years ago, # |   0 thank for contest problems is good :D
 » 4 years ago, # | ← Rev. 3 →   0 EditWhy does both submission give AC?CorrectWrongTest case 100Every element of this matrix is C.
•  » » 4 years ago, # ^ |   0 The other one gives verdict as Skipped not AC
•  » » » 4 years ago, # ^ |   0 Edited
 » 4 years ago, # |   0 Iranian contests are unlucky for me :(But now no claims to the authors
 » 4 years ago, # |   0 can any body explain problem C elaborately. I was not able to understand tutorials
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 we count dp[length][balance] = number_of_correct_bracket_sequences_with_balance=balance like dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]. dp[0][0] = 1then consider length_of_prefix = i (i=0..n-m), it means length_of_suffix = n-m-i. then iterate over balance of prefix (it must be not lower than (minimum prefix balance of string) * -1), so ans += dp[i][current_balance] * dp[n-m-i][current_balance + balance_of_string] (need to process RE).
 » 4 years ago, # |   0 Can someone explain the solution B? looks to be greedy, sort by start or end, and doing a linear traversal on both male and female intervals does not work? looks to be a standard problem, can someone help please?
•  » » 4 years ago, # ^ |   0 First Notice that number of females and males have to be same.So answer is always a' multiple of two. I did it as follow- Make an array of 366 days for male and female separately. take start and end . Increment the array b/w start and end for each gender separately. Then traverse both the array and take max of min of both arrays and multiply by two. Since days are only 366 This method works easily
 » 4 years ago, # | ← Rev. 2 →   -7 629C - Famil Door and Brackets : 16243295 16244309 cheaters629D - Babaei and Birthday Cake : 16246407 16254007They will never give up :)
 » 4 years ago, # |   0 Good problemset! (specially C)
 » 4 years ago, # |   0 Hello codeforces, I am having struggle with problem B and i want to solve it alone before looking at editorial but i am really having difficulties with it.Can someone help me out or atleast give me a hint what is wrong with my code?Cheers CODE
•  » » 4 years ago, # ^ |   +3 Consider this test case: 4 M 1 4 M 1 4 F 1 2 F 3 4 Your code will answer 4, while the correct answer is 2. You don't consider the fact that the friends who have available time in common with a specific person, might not be available together at all. Try to think of it from a different angle.