### GreenGrape's blog

By GreenGrape, 4 years ago, translation, Code: 36605296

Code: 36605336

Code: 36605356

Code: 36605449

Code: 36605502

Code: 36605519 Tutorial of Codeforces Round #471 (Div. 2) Comments (21)
 » It would be a good idea to add tutorial link in contest page.
 » what does the function root() in problem C solution
•  » » sorry for the question. I understand all the thing.
 » 4 years ago, # | ← Rev. 2 →   C's time limit was stupidly strict. 36551515 is TLE(runs in about 2.15 seconds), while 36625920 is AC. The only difference was adding special cases if the exponent>=30.
•  » » Well, usually time limits are set 2-3 times as authors' solutions. As you can see, my solution (without any optimizations) runs in ~700 ms. 36551515 is TLE due to endl & flushes. 36629869
 » 4 years ago, # | ← Rev. 5 →   In problem C, my question is when there are much more element need to be inserted in a container so "should we prefer vector on the place of the set?" in c++.because of the same thing I implemented using set giving TLE and by vector AC
 » Can anyone please tell me why are we disposing sqrts in problem c
•  » » There are 10^9 squares in the range [1..10^18], so we can't just store them to answer our queries. But floor(sqrt(x)) is a number of squares in the range [1..x], so, we just calculate floor(sqrt(R))-floor(sqrt(L-1)) to know how many squares are in the range [L..R]
•  » » » Now I got it ,Thanks!!
 » I think that in problem A first test case the ans should be 26700.0000Because after starting from 20:00 H= 315 and H/N=315 Hence we must give cat food in upcoming 315 minutes continuously to ensure that cat gets fed after 315 min in the min cost.. But 20:00- 23:59 there are total of 240 min hence 240*(4/5)*100+(315-240)*100 = 26700.0000 This will be the ans because remaining (315-240) i.e 75 min will be out of the discount period hence we have to pay for each bun C roubles in that period giving total cost of 26700.0000 Correct me if i am wrong !
 » In problem A, there could be a optimal timing in between waking up and 20:00 too right? Can someone explain why isn't this so?
 » Problem D can be solved by KMP with O(n) time complexity.
 » question C can be easily solved by using the Mobius function (inclusion-exclusion of numbers l<=x<=r that can be generated in several ways). However, this solution requiers accuracy of the pow function and in test 5 (very big numbers) I get an off-by-one solution. How can one use the pow function to get the actual floor of the result even if the base is 10^18?
•  » » You can test it manually.Imagine that the number returned by pow is x. Then test xp, (x + 1)p and (x - 1)p and choose the one that satisfies the conditions.