Problem linkhttps://www.codechef.com/LOCJUL17/problems/BOSSLOSS my approachis to calculate n*(n+1)/2 then run reverse loop and check where m satisy the sum,but this approach give me tle. please explain your approach? asked 31 Jul '17, 09:18

This will give TLE because of this constraint 1 ≤ N,M ≤ 10^18. There are two solutions I am thinking right now:
I hope this will help. answered 31 Jul '17, 09:32
10^18 array is possible? so i think u can't use binary search,thats why i dont
(31 Jul '17, 09:35)
but every time equation is different,so quadratic also.
(31 Jul '17, 09:35)
You don't have to make an array of 10^18 size. You are realising that in question it's just asking a lowest value of n such that sum(1+2+3+...+n) >= m. Right?
(31 Jul '17, 10:10)
And why quadratic will be different every time for 1 test case (particular pair of n and m). You have to solve inequality and from there it will say i <= some number then some number is your answer because you have find first value of for which i*(i+1)/2 <= m. Here i is not iterating over [1,10^18] it's just representing a value for n.
(31 Jul '17, 10:16)
And I am not asking to make an array of 10^18 and search in that. I am just saying to search value in this range for n. with initial lower value = 1 and upperValue 10^18. Please read it carefully.
(31 Jul '17, 10:18)
so how can we use binary search? elaborate it
(31 Jul '17, 11:05)
1
Here is sample code:
I am not sure if this code is taking some corner cases.. But it's pretty much gist of what I was saying..
(31 Jul '17, 11:49)
showing 5 of 7
show all

This problem has a very simple solution. (O(1) complexity for a single test case) Our aim basically, is to find the least i such that i(i+1)/2 >= m. In other words, i(i+1) >= 2m. Let x= ceil (sqrt(2m) (You can do this by x= (long int) pow(2*m,0.5) ) Thus, x^2 <= 2m and (x+1)^2 > 2m Now you can convince yourself that the minimum required value of i will either be x or x+1 only. This is because, if i=x, then i(i+1)= x*(x+1) which *may or may not be greater than 2m (Since x^2 <= 2m) BUT if i=x+1, then i*(i+1)= (x+1) * (x+2) is definitely greater than 2m. So,all you have to do this is calculate x = (long int) pow (2*m, 0.5), check if x *(x+1)>=2m. If yes, then answer will be x, otherwise answer will be (x+1). At the end obviously, do check if the final answer (x or x+1) is less than or equal to n. Hope it helped :) answered 31 Jul '17, 12:11

do we have to put long long int some where?. as my approach was wright but answer came out to be wrong. answered 31 Jul '17, 11:41

Please tell me what's wrong with my code. I used the same approach i.e. finding sum of all and then using i^2+i2m <= 0 , but my solution gives WA, not even one subtask ran successfully. https://www.codechef.com/viewsolution/14740353 My code's ideone link: http://ideone.com/e.js/xECbIx answered 01 Aug '17, 22:11
We cannot access your code since solutions arent visible. Please copy your code on ideone.com and give us link :)
(01 Aug '17, 22:56)
Ideone link: http://ideone.com/e.js/xECbIx
(01 Aug '17, 23:05)
