gepardo's blog

By gepardo, history, 16 months ago, translation, ,

Hello, Codeforces!

Tomorrow, in March 15, 2017 at 18:05 MSK a regular rated Codeforces round for participants from the second division will take place. As usual, participants from the first division can take part out of competition. It's my second contest and I hope you'll like it more than my previous one.

As usual, there will be five problems on the contest and two hours to solve them. I advice you to read all the problems' statements attentively. Also check all your solutions for correctness even if they passed all the pretests. Verdict Pretests passed doesn't mean that the solution is completely correct! I wish you to enjoy the contest and learn something new solving the problems.

Like in the last time, the problems will be about Anton and his friends.

Great thanks to Alexey Vistyazh (netman) for help in preparing the contest, Vladislav Vishnevsky (Vladik) for testing the round, Dmitry Klebanov (dakdima) for reading the statements carefully, and of course, Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon.

Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500.

UPD. The contest is over, system testing has already started, the editorial will appear soon.

UPD2. Editorial has arrived.

UPD3. Congratulations to the winners of the contest!

Div. 2

Thanks everyone for participating :)

•
• +222
•

 » 16 months ago, # |   +1 Auto comment: topic has been translated by alex256 (original revision, translated revision, compare)
 » 16 months ago, # |   0 Why not in main page?
•  » » 16 months ago, # ^ |   +153 404 not found
•  » » » 16 months ago, # ^ | ← Rev. 3 →   +54 FOUND! I'm here.
•  » » » » 16 months ago, # ^ |   +75 You must have been waiting for a long time for commenting in this round
•  » » » » » 16 months ago, # ^ | ← Rev. 4 →   +33 yeah, I have been waiting for 403 rounds! :D
•  » » » 16 months ago, # ^ |   -19
 » 16 months ago, # |   +15 finally a regular round after 10 days .
 » 16 months ago, # | ← Rev. 2 →   +21 Looks like more hacking is gonna happen in the contest. Also love the statement I wish you to enjoy the contest and learn something new solving the problems.
 » 16 months ago, # |   +20 Thanks for the contest.
 » 16 months ago, # |   -13 ERROR 404 :p
•  » » 16 months ago, # ^ |   -29
 » 16 months ago, # |   +19 Expecting a lot of Hacks !!
 » 16 months ago, # |   +96 Codeforces should have just skipped round 404 and have gone to round 405. That way, whenever someone searched for round 404, they would have got the error message "Round 404 not found" xD
 » 16 months ago, # |   +197 I advice you to read all the problems' statements attentively Delicate way of saying that pretests are guaranteed to be shit.
•  » » 16 months ago, # ^ |   +34 Verdict Pretests passed doesn't mean that the solution is completely correct! True
•  » » » 16 months ago, # ^ |   -6 Verdict Pretests passed mean that the solution is completely incorrect!
•  » » » 16 months ago, # ^ |   +79 Verdict "Accepted" also doesn't mean that the solution is completely correct, but we tend to forget it.
•  » » 16 months ago, # ^ |   -13 I think it means that problem statement is complicated, but is it true?
•  » » 16 months ago, # ^ |   +6 I saw sources that passed C with brute-force,but a simpla 10^18 1 test shut them down.Also,there were some with sqrt(n-m),but n
 » 16 months ago, # |   -11 Div. 1 Round not found.
 » 16 months ago, # |   +23 Btw anyone knows the reason behind the low frequency of cf rounds thesedays.
 » 16 months ago, # |   0 I hope short statements!!!
•  » » 16 months ago, # ^ |   0 Why? Longer statements are usually more understandable and more interesting to read.
•  » » » 16 months ago, # ^ |   +33 mmmm..! Actually I mean short and understandable!!! You can see Csacademy's problems!!! Some of part of stories is really useless!!! We can make a short interesting problem.
•  » » » » 16 months ago, # ^ | ← Rev. 3 →   +9 Yes, such statements are good. I hope you'll find my statements short enough, understandable and interesting :)
•  » » » » » 16 months ago, # ^ |   +14 Don't worry! I guess your contest is strong and interesting enough to don't think about the statements :)In Allah's safeguard
 » 16 months ago, # |   +8 Also check all your solutions for correctness even if they passed all the pretests. Verdict Pretests passed doesn't mean that the solution is completely correct!That's look like problem's are a little bit tricky and suitable for hack...:)
 » 16 months ago, # |   -49 This is the first contest that I skip because I have 1900 rating!
•  » » 16 months ago, # ^ |   +12 You can participate unofficially too. Main thing is learning, not rating, and I'm sure you can learn new things from any contest (no matters Div.1 or Div.2).
•  » » » 16 months ago, # ^ |   0 Yeah, that's true. Rating doesn't matter much :)
•  » » » » 16 months ago, # ^ |   +3 says an International Master
 » 16 months ago, # | ← Rev. 2 →   -14 It is too late for me to join it. :(
 » 16 months ago, # |   -38 Contest 404 not found ! :P
 » 16 months ago, # | ← Rev. 2 →   -36 :|
•  » » 16 months ago, # ^ |   +18
 » 16 months ago, # |   -17 Verdict Pretests passed doesn't mean that the solution is completely correct! be carefull everyone , today's questions will have many hacks :) wishing everyone positive rating change , good luck ..
 » 16 months ago, # |   -6 Thanks
 » 16 months ago, # |   +14 Hoping of getting a color change to dark blue:)
 » 16 months ago, # |   -32
 » 16 months ago, # |   +17 This post scares me for the contest.
 » 16 months ago, # |   +26 Anybody noticed the "tag not found" tag? :D :V
 » 16 months ago, # |   +35 Let's see if there will be server problems this round...
 » 16 months ago, # | ← Rev. 3 →   -29 The comment is hidden because of too negative feedback, click here to view it
•  » » 16 months ago, # ^ |   +2 Nice
•  » » 16 months ago, # ^ |   +3 It looks like you smoke too much this time :V
 » 16 months ago, # |   -48 The comment is hidden because of too negative feedback, click here to view it
 » 16 months ago, # |   0 Auto comment: topic has been updated by alex256 (previous revision, new revision, compare).
 » 16 months ago, # |   +7 Last time I did a comment like this I lost a 100 point in rating but...This is the last CF round before the selection test here...I really hope that I can get to Div1 so I can impress everyone I know with a new color wish me luck!!!
•  » » 16 months ago, # ^ |   +12 it doesn't matter buddy rating does nothing on the field hope we can make it together
 » 16 months ago, # |   0 finally a regular round after many days.
 » 16 months ago, # |   0 The contest starts in 12 minutes. Good luck all!
 » 16 months ago, # |   0 Did you experience a bug? The site said the the contest had started.
 » 16 months ago, # |   +35 I think the score distribution for hacks isn't fair. Hacking a Div2A and Div2D isn't the same. Harder problems should have more points for hacks than the easier ones. Also it would be interesting if hack score decreased with time :P
•  » » 16 months ago, # ^ |   +3 Good thinking!!
 » 16 months ago, # |   0 nice problems ... thanks alex256
 » 16 months ago, # | ← Rev. 2 →   0 I hate acting like a copy-past machine I'm talking about div2 A
 » 16 months ago, # |   +16 Long submission queue. Anybody else facing this problem?
•  » » 16 months ago, # ^ |   +1 yes..
 » 16 months ago, # | ← Rev. 2 →   +25 Rating prediction for this contest could be found hereExtensions: Have a high rating and don't lose anything:)
•  » » 16 months ago, # ^ |   +8 This rating-predictor is vert accurate. Thank you very much for it :)
•  » » » 16 months ago, # ^ |   +4 I'm glad to read this:)
•  » » 16 months ago, # ^ |   +5 Thank u very much for the predictions.Great work.Anyway what do use to make these predictions.
•  » » » 16 months ago, # ^ |   +2 Actually prediction is quite wrong word, couple of my friend misunderstand it too. I would be happy if someone propose better service's name:) My app just periodically calculate rating change based on open formulas, assuming that current standings is final.
•  » » » » 16 months ago, # ^ |   +5 Got it.Thankyou once again :-)
•  » » 16 months ago, # ^ |   +5 It predicted exactly the same for me.
•  » » » 16 months ago, # ^ |   +10 Unfortunately today's prediction is a bit wrong — my tool predicted for everyone exactly 1 point higher rating than official.I haven't figured out yet what is reason of this, for previous contests prediction was absolutely correct:)
 » 16 months ago, # | ← Rev. 3 →   +7 Judge 404 not found :PPlease fix it (I submitted my solution to E and scared when seeing long long queue :D).UPD: Nevermind it got TLE :P
 » 16 months ago, # |   +7 My solution is saying in queue for the last 5 minutes. :( and only 10 minutes are left for the contest.
•  » » 16 months ago, # ^ |   +1 Same here :(
 » 16 months ago, # |   +9 Oh, another round about me! Thank you, my brother!Good luck everyone in solving tasks about me!
 » 16 months ago, # |   0 the round is extended by 10 minutes.
 » 16 months ago, # | ← Rev. 2 →   +1 What just happened? Was the contest extended?
 » 16 months ago, # |   0 So hard round, especially math in D
•  » » 16 months ago, # ^ |   +1 I think D is dynamic programming (maybe I'm wrong).
•  » » » 16 months ago, # ^ |   +3 combinatorics
•  » » » » 16 months ago, # ^ |   0 How did you solve it?The best complexity i have discovered so far is N^2
•  » » » » » 16 months ago, # ^ |   0 read Vandermonde's identity and try to solve it yourself :)
•  » » » » » » 16 months ago, # ^ |   +3 this was exactly what i needed.Too bad i didn't use it in the contest,but thank you for showing it to me.
•  » » » » » » » 16 months ago, # ^ |   0 you're welcome
 » 16 months ago, # |   +16 A similar problem of today's E : link
•  » » 16 months ago, # ^ |   0 just wait until the end of the round
•  » » 16 months ago, # ^ |   0 This problem was bad. It timed out solutions based on ordered statistics tree for example, but allowed sorted vectors. The query answer complexity is the same O(sqrtn*logn)...
 » 16 months ago, # |   +220
•  » » 16 months ago, # ^ | ← Rev. 3 →   +5 How to do it? I tried sqrt root decompostion .But it was TLE. UPD: sqrt decomposition passed in 702 ms.
•  » » » 16 months ago, # ^ |   0 I've tried to store a treap in every node of the segment tree, but i didn't manage to code it in time. The time should be O(q log^2 n)
•  » » » » 16 months ago, # ^ |   0 i tried it here, it got TLE, maybe weak implementation, idkhttp://codeforces.com/contest/785/submission/25524189
•  » » » » » 16 months ago, # ^ |   0 I'll try sumbitting mine after the testing phase ends.
•  » » » 16 months ago, # ^ |   0 You can't pick block size as sqrt(n) if you use BIT. Sqrt(n) only optimizes stuff like N/x + x, whereas BIT has a log factor. Look at this comment: http://codeforces.com/blog/entry/50329?#comment-343301
•  » » » » 16 months ago, # ^ |   0 should still pass by a narrow margin actually.
•  » » » 16 months ago, # ^ |   0 for me I solve it with sqrt decomposition and a BIT for each block and it passed the pretests
•  » » » » 16 months ago, # ^ |   0 I solved it with sqrt decomposition and sorted vectors, 2.5 sec on pretests.
•  » » 16 months ago, # ^ |   +18 Sorry for this, I didn't know about this problem before. Anyway, I hope you enjoyed other problems :)
•  » » 16 months ago, # ^ |   0 I knew INVCNT but not this one :(
 » 16 months ago, # |   +2 How do you do C? I was trying binary search, it was working alright on smaller cases, but it wasn't working on bigger cases.
•  » » 16 months ago, # ^ |   0 I thought of this equation but couldn't implement in time. (ans * (ans + 1))/2 = N + ans * M — ((M * (M + 1))/2).It says, amount of food birds ate = N + grains_brought — grains_wasted I'm not sure if it's correct.
•  » » 16 months ago, # ^ |   0 (1e18 * (1e18 + 1)) / 2 is really big...you shouldn't try a day that is bigger than 1e10
•  » » » 16 months ago, # ^ |   0 Ans is not more than 1e9. Cause in worst case ans = sqrt n which is not more than 1e9.
•  » » » » 16 months ago, # ^ |   +7 Nope, if n<=m, then ans is n.
•  » » » » 16 months ago, # ^ |   +3 The result is < sqrt(2 * 1e18), not 1e9
•  » » » » » 16 months ago, # ^ |   0 Why ?
•  » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 Let m = 1, and N = 10^18. ie from 2nd day onwards bird start depleting the barn.=> x*(x+1)/2 — 1 = N.=> x^2 + x = 2*N + 1=> x can be up to sqrt(2N)+1. => search from 0 to ceil(sqrt(2*1e18)+1)
•  » » 16 months ago, # ^ |   0 I used binary search. But I guess there was an O(1) solution as well.
•  » » » 16 months ago, # ^ | ← Rev. 2 →   +2
 » 16 months ago, # |   0 Hating Math more and more.
•  » » 16 months ago, # ^ |   +5 Where is math? In task D?
•  » » » 16 months ago, # ^ |   0 isn't C math? :/
•  » » » » 16 months ago, # ^ |   +4 It can be solved by binary search also.
•  » » » » » 16 months ago, # ^ |   +6 you have to do math calculation in the BS :P
 » 16 months ago, # |   +6 My 10 minutes are wasted... :(
 » 16 months ago, # |   +12 How to solve D?
•  » » 16 months ago, # ^ |   +59 for each i such that arr[i] == ( let x = number of ( from 1 to i — 1 let y = number of ) from i + 1 to n add to the answer this can be simplified to
•  » » » 16 months ago, # ^ |   +18 Can you show how to simplify it? I got the summation part, but I couldn't simplify.
•  » » » » 16 months ago, # ^ |   +71 = This can be seen as you have objects on left and objects on right and you have to select objects in total which is just
•  » » » » » 16 months ago, # ^ |   +23 I also came up with the summation part but couldn't simplify it. Now when I saw that I feel like a total retard.
•  » » » » » » 16 months ago, # ^ |   0 You and me both. :(Another way of looking at it is by saying that we have a group of (x+y) items, x of which are '(' and y are ')'. Now find all ways to select k (from 0) items from x and k+1 items from y.This is the same as selecting k items from x and (y-k-1) items from y.If we consider this summation, this is basically, selecting (k+y-k-1) items (i.e y-1 items) from the group (x+y), considering the ways in which we can 'divide' the (y-1) items in the two distinct groups.=> Reduces to all ways of selecting y-1 items from (x+y) group.Funny thing is, I remember doing this reduction long back. Just couldn't redo it during the contest no matter how hard I tried. :/
•  » » » » » » » 16 months ago, # ^ |   +1 Is this ok? Suppose we have x "(" and y ")", and we want choose k items from each. so it should be (x + y)Cy ? But for case ()) and k be 1, it will give answer as 3 but not 2.Here I'm not going with the same logic as rajat1603 where he omits one "(" and adds k + 1 to y. Infact, if we have at position i, X chars "(" until i and Y chars of ")" after i, the answer should be xCx . yCx, am I right? :)
•  » » » » » » » » 16 months ago, # ^ |   +1 If it was xCx*yCx, you are double counting a lot of cases, for example (()). at pos = 0, you will get 1C1*2C1 = 2 at pos = 1, you will get 2C2*2C2 = 1 at pos = 2, you will get 2C2*2C2 = 1 at pos = 3, you will get 2C1*1C1 = 2=> total ways = 6, there's a lot of double counting in there.To remove double counting, iterate from left to right, and only add when a new '(' is encountered, finding number of ways where the current '(' is included. That's why we omit one count for '('.This way, in your example we getat pos 0, two pos (.) and (). or (3-1)C(1) at pos 1, we get 0 (since not '(') at pos 2, we get 0 (since not '(') => total = 2.
•  » » » » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 Thanks priyanshu_95 for taking the time to explain. :) However in the example, (()), with xCx. yCx we would get 3 but not 6. We get three like this: 1C1 . 2C1 + 2C2 . 2C2 + (2C2 . 1C2 = 0) + (2C2 + 0C2 = 0). However, The real answer is 5.
•  » » » » » 16 months ago, # ^ |   0 According to the definition we can use (x-1) instead of (y-1), how would that be true?
•  » » » » 16 months ago, # ^ |   +4 Suppose you have 2 collections of size x and y respectively. Consider the number of ways choosing y-1 from the combined collection. Now each of these ways can be broken down to choosing some number of items from among the x, and some number of items from among the y. This is exactly what the first formula says.
•  » » » 16 months ago, # ^ |   +7 My idea for D is divide and conquer compute answer for left part and right part and merge the answers and then compute the answer for range l to r , i don't know where i went wrong could some one please help : link [submission:http://codeforces.com/contest/785/submission/25527662]
•  » » » 16 months ago, # ^ |   0 Let me check if I got your idea correctly: you're counting the number of RSBS which will include the '(' occurring at position i. Is that it?
•  » » » » 16 months ago, # ^ |   +3 i am counting number of sequences such that that rightmost ( is at i
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 This formula is giving 5 for the first sample:)(()()Could you please check my code? 25530480UPD: Sorry, found my bug.
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   +3 Steps : 1 compute the answer for range [l,m] and [m+1,r]  2 get the open '(' count in [l,m] and get the ')' close count in [m+1,r]  int minc=min(oc,cc); for(int i=1;i<=minc;i++){ ans+=(C(oc,i,mod)*C(cc,i,mod)%mod); ans%=mod; } where C(n,r,mod) i am using Lucas theorem here .
•  » » » » » 16 months ago, # ^ |   0 Did it work for you? I got WA case 4...
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 The case )()()()(((( gives wrong answer with this approach. But I don't know how to fix it.
•  » » » » » 16 months ago, # ^ |   0 I think the right summation for ans is: ans+=(C(oc-1,i,mod)*C(cc,i,mod)%mod); ans%=mod; 
•  » » » » » » 16 months ago, # ^ |   0 why do you think that explain please ?
•  » » » 16 months ago, # ^ |   +3 Why i from 0 to x ? Why not 0 to min(x, y) ?
•  » » » » 16 months ago, # ^ |   0 I thought the same...
•  » » » » 16 months ago, # ^ |   +3 for i > x you can consider the terms as 0 so it it doesn't matter.
•  » » » » » 16 months ago, # ^ |   0 I have understood it, thanks a lot :D
•  » » 16 months ago, # ^ |   +23 using Vandermonde's identity
 » 16 months ago, # |   -10 A and B are silly problems E is so standard, and now I found that it's even a copied problem for D I can't come up with an easy-coding solution and I hope it has an interesting solution I think C is good but it's so easy for a div2 C problem
•  » » 16 months ago, # ^ |   +9 Yup, its copied from SPOJ. I just found it out. I wished I found it earlier.
•  » » » 16 months ago, # ^ |   0 You can also find solution here — How to solve SWAPS
 » 16 months ago, # | ← Rev. 2 →   +1 My idea of D is to calculate the partial sums of open brackets and close brackets, and sweep a line from start to end while doing some combinatorics. However this is quadratic and I got TLE on pretest 6. Cannot find a method to optimize it.
 » 16 months ago, # |   0 when SYSTEM TESTING WOULD START?
 » 16 months ago, # |   0 Was server slow or problem with my service provider? I waited to hack two solution in two tab, refreshed again and again but couldn't put the cases :/
•  » » 16 months ago, # ^ |   0 Same here. Because of that problem I ended up putting the wrong hack and got unsuccessful hack.
 » 16 months ago, # |   0 A big glitch in COdeforces is there.I hacked a user's submission which was clearly wrong.The thing is time was over when my hack was in process, hence I got -50 points loss without hack being processed. Moderators please check the glitch
 » 16 months ago, # |   +12 I solved the problem E in the last minute ,but I submitted it failed because it just had a "%lld" which was commented out.
 » 16 months ago, # |   +1 404 rating not found :(
 » 16 months ago, # |   0 Too many Binary Search problems these days!
 » 16 months ago, # |   0 What is the hacking input of problem C?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 n
•  » » » 16 months ago, # ^ |   0 also binary search that has x * y where x , y can be up to 1e18
•  » » » » 16 months ago, # ^ |   0 I got hacked on that one and sent my second submission in Python =D
•  » » 16 months ago, # ^ |   0 I hacked two guys with 1 10000and one guy with 1e18 1
•  » » 16 months ago, # ^ |   +3 2 3 worked for me (:
•  » » 16 months ago, # ^ |   0 2 3
 » 16 months ago, # |   0 Problem C has funny test data. I passed the pretests but got TLE-hacked. :-(The algorithm I used is speed through the first m days, and then manually implement the rest. I barely passed the pretests with a 499ms running time, but then failed with a hack.
 » 16 months ago, # |   0 what is the pretest 4 in E ?
 » 16 months ago, # | ← Rev. 2 →   +4 What is the time complexity of this code? I tried to hack (unsuccessful ) it with test case:1e18 1its ans is 1414213563this guy saves 1 initially in i and m in ans, and he updates i every time by 1, i.e., his while loop should be running 1414213562 times! But no TLE.
•  » » 16 months ago, # ^ |   +5 Yes, it iterates about 1.4e9 times. But the loop is very very simple, so it might run faster than expected. It runs within 600 ms in my desktop.
•  » » 16 months ago, # ^ |   0 Also thought abouth this solution, but i guessed that there will be TL :/
•  » » » 16 months ago, # ^ |   0 And it got AC :/
•  » » » 16 months ago, # ^ |   +5 Just determine on how simple your code is, i saw some people using similar approach with time complexity O(answer - m) as well but unfortunately got TLE.
 » 16 months ago, # |   0 What is the hack for problem C? :'v
•  » » 16 months ago, # ^ |   0 Anything with n
•  » » 16 months ago, # ^ |   0 If someone uses like m*m without long arithmetic, that just 100 and 10^18
 » 16 months ago, # |   0 How to solve C?I tried binary search over fucntion f(mid) = n-m-(mid*mid + mid) and set answer as the ceil of the root of the equation.Solution Link: Solution
•  » » 16 months ago, # ^ |   0 mid * mid is way too big
•  » » » 16 months ago, # ^ |   0 So, what should be the approach?
•  » » » » 16 months ago, # ^ | ← Rev. 3 →   0 I used BigInteger on java. So i guess, that it is a long arithmetic also
•  » » » » 16 months ago, # ^ | ← Rev. 3 →   +6 The upper bound can be lowered to about as this is approximately the maximum value of answer - m.
•  » » » » » 16 months ago, # ^ |   0 How did you get the upper bound ?
•  » » » » » » 16 months ago, # ^ |   +8 The answer is finding minimum value of X such that m + (1 + 2 + ... + X) ≥ n, which is same as finding min X s.t. X(X + 1) ≥ 2(n - m). So, X should be around , and here the maximum value of n is 1018. So upper bound is about .
•  » » » » » » » 16 months ago, # ^ |   +5 Thanks :)
•  » » » » » » » 16 months ago, # ^ |   +5 I should have read this comment earlier was trying to figure out the same thing and understood after 2 hours that the problem is with overflow.PS : Thanks for the explanation
•  » » » » 16 months ago, # ^ |   0 easy . mid * mid might be too big but mid * mid / 1e18 is good enough . just be careful to write mid / 1e18 * mid
 » 16 months ago, # |   0 Auto comment: topic has been updated by alex256 (previous revision, new revision, compare).
 » 16 months ago, # |   +21 The Rank, The Name :D
•  » » 16 months ago, # ^ |   +3 You are old driver!
 » 16 months ago, # |   0
•  » » 16 months ago, # ^ |   0 +1 instead of -1: ans=(1+math.sqrt(1+8*(n-m)))/2 for me it passed tests
•  » » » 16 months ago, # ^ |   0
•  » » 16 months ago, # ^ |   0 Exactly same with my code (25526817) :(
 » 16 months ago, # |   0 http://codeforces.com/contest/785/submission/25527584 Please point out the mistake!!!
•  » » 16 months ago, # ^ |   +17 Debugging yourself teaches much more.
•  » » 16 months ago, # ^ |   +3 Too much code
•  » » » 16 months ago, # ^ |   0
•  » » » » 16 months ago, # ^ |   -8 Qumeric please have a look!!Thanks in advance..
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 double sum=(double)((double)(e)*(double)(e+1))/2;This may be the problem
 » 16 months ago, # | ← Rev. 2 →   0 Submission no: 25513626 It won't work for the following test case, but it is passed in system test. Test Case: 2 1 1 3 3 2 1 1 3 3correct output:2 but the solution output will be 0
 » 16 months ago, # |   +5 Apparently O(10^9) is enough for problem C: 25509756
 » 16 months ago, # | ← Rev. 2 →   0 Problem C : What is wrong in this approach ?if(m >= n){ cout<
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 i could be near to 1000*1000*1000 (sqrt(2*(n-m)).and your solution is O(i)
 » 16 months ago, # |   0 i did casework based on the index of the last '(', and then got a binomial formula. My code is here: http://codeforces.com/contest/785/submission/25528358does anyone know how to do the binomial thingies more elegantly, as these take quite a long time to implement. I tried checking others' solutions but I think that most didn't use explicit binomial formulas.
•  » » 16 months ago, # ^ |   +1
 » 16 months ago, # |   +3 In problem test case 16 999999998765257152 10 of problem C, my ans on ideone is showing correct but on CF it shows different answer why? http://ideone.com/mn2iXL
•  » » 16 months ago, # ^ |   0 I believe it's because the function pow will work differently depending on the compiler, since it's not supposed to work with large numbers like 10^18. Your code passes replacing it with powl. Check: http://en.cppreference.com/w/c/numeric/math/pow
 » 16 months ago, # | ← Rev. 2 →   +16 What does this means? http://prntscr.com/ekdcpv
 » 16 months ago, # |   0 same code giving ac with g++ 5.1 and wa with g++14 what's this ??? ac code wa code what's the problem
•  » » 16 months ago, # ^ |   0 Seems to be a double rounding issue here: sqrt(1 + 4 * q)). The result of this statement for the failing test case is 2828427123.0000000... , which is close to 'double' precision limits. So it might also be saved in memory as 2828427122.9999.... When implicitly casting this to int, it truncates downwards, so that's where the -1 of your answer comes from. The solution is described here. In short, add +0.5 , before downcasting to 'int'.
 » 16 months ago, # |   +1 Problem C:sqrt WAsqrtl AChow powerful is sqrtL?
•  » » 16 months ago, # ^ |   +3 sqrt ac in g++5.1
•  » » » 16 months ago, # ^ |   0 I think depends on how you've calculated:I did: (long long) ceil ((-1 + sqrtl (1 + 8*(n-m))) / 2);
•  » » » » 16 months ago, # ^ |   0 but same code is ac in g++5.1 and wa in g++ 14 i have given links in my comment above
 » 16 months ago, # |   +9 guys, help? What's the difference between addition and subtraction? first loop passed the worst case (1e18 1) in 904ms and got AC while the second got TLE.code with 1st while: here code with 2nd while: herealso, what other details can reduce running time? and thanks
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 ignore
•  » » » 16 months ago, # ^ |   0 What?
•  » » 16 months ago, # ^ |   +4 n-m is constant. I suppose it is a compiler optimization.
•  » » 16 months ago, # ^ |   0 In your code, "n-m" is constant through all the iterations of the loop, whereas "s+m" is not constant because the value of 's' changes in the loop. I believe, the compiler optimises the "n-m" case by avoiding recomputing the value of "n-m".
•  » » » 16 months ago, # ^ |   0 And what's about -faggressive-loop-optimizations? Is not the optimizer able to make simplification in such simple conditions?
•  » » » 16 months ago, # ^ |   0 Thanks
 » 16 months ago, # |   0 Hi! Tell me please what's wrong with this solution for B. Runtime eror. Can't find a mistake :( http://codeforces.com/contest/785/submission/25512453
•  » » 16 months ago, # ^ |   0 comparator(x, x) should return false
•  » » 16 months ago, # ^ |   0 Your comparator function should give false for equal parameters, which is the reason that your sort won't work well. Use '<' in place of '<=', that should suffice.
•  » » 16 months ago, # ^ |   0 to avoid mistakes like this, you can use std::stable_sort instead
•  » » 16 months ago, # ^ |   0 I was actually looking for exactly such a mistake during contest, but unfortunately (for me) everyone in my room got it correctly.
 » 16 months ago, # |   0 Auto comment: topic has been updated by alex256 (previous revision, new revision, compare).
 » 16 months ago, # |   0 Thanks for the contest.
 » 16 months ago, # |   0 Wow for problem C my code was #include #include #include #include using namespace std; int main(){ long long n,m; cin >> n >> m; if (m > n) m = n; long long k = ceil((double)(-1+sqrt(1+8*(n-m)))/2.0); cout << m+k << endl; return 0; } and I got a wrong result on system test (test case 16). But when I changed the code to long long k = ceil((long double)(-1+sqrt(1+8(n-m)))/2.0); I pass all system tests... I feel so sad :(
 » 16 months ago, # |   0 May I make one suggestion: in Division 2 contests, the updates should first list the Division 2 winners, and then the Division 1 winners.Great contest and very nice problems! Thanks.
 » 16 months ago, # | ← Rev. 5 →   0  int len=(int)sqrt(n); int cnt=1; for(int i=1;i<=n;i++){ belong[i]=(i+len-1)/len; vl[i]=i; if(belong[i]==cnt)r[cnt]=l[cnt++]=i; else if(belong[i]
•  » » 16 months ago, # ^ |   +3 r[cnt]=l[cnt++]=i; Isn't it an undefined behaviour?
•  » » » 16 months ago, # ^ |   0 Thanks
•  » » » » 16 months ago, # ^ |   0 You're welcome :)
 » 16 months ago, # |   0 My submission for C was off by one in some of the test cases. Can somebody help me with it? Here is my solution 25525973
•  » » 16 months ago, # ^ |   0 Your solution has wrong logic, please read the editorial.
•  » » » 16 months ago, # ^ |   +5 Thanks! Nice editorial
 » 16 months ago, # |   0 I tried to solve problemE with segment tree plus ordered multisets but I am getting TLE on test 7.The complexity of build function in my code in O(N * LOGN * LOGN * C). where C is the constant factor in segment tree.(C ≈ 4).http://codeforces.com/contest/785/submission/25568923Is there any way to optimize the build function.