×

Best Way to Solve this LOC July Easy Problem?

 0 Problem link-https://www.codechef.com/LOCJUL17/problems/BOSSLOSS my approach-is 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 1★vivek96 518●2●20 accept rate: 7%

 2 This will give TLE because of this constraint 1 ≤ N,M ≤ 10^18. There are two solutions I am thinking right now: use simple inequality method and solve this quadratic as i(i+1)/2 <= m => i^2+i-2m <= 0 ; You can follow my solution here. Second approach can be using binary search over [1,10^18] for n. Assume you answer is n (mid value in range) then simply calculate n*(n+1)/2 if it's less than m then move lower pointer if greater then move upper pointer, then choose mid point again, until lower and upper value are equal are equal. I hope this will help. answered 31 Jul '17, 09:32 1.1k●1●9 accept rate: 19% 10^18 array is possible? so i think u can't use binary search,thats why i dont (31 Jul '17, 09:35) vivek961★ but every time equation is different,so quadratic also. (31 Jul '17, 09:35) vivek961★ 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) vivek961★ 1 Here is sample code: lower = 1 upper = 10^18 mid = None while(upper - lower > 1): mid = (lower+upper)/2 if mid*(mid+1)/2 < m: lower = mid elif mid*(mid+1)/2 > m: upper = mid else: break print mid  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
 1 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 20●2 accept rate: 0%
 0 just one word arithmetic progression!! answered 31 Jul '17, 10:18 94●4 accept rate: 0%
 0 On my case, i used semi-brute though... First, I tried to get the maximum value by using:  total = n(1+n)/2  if total is less than given M, then I'll return -1. Else, I use quadratic formula to find the middle:  x = round((-1 + sqrt(1 + 8M))/2)  Then, I'll check within the range of max(0, x-2) to x+2 and apply the summation of arithmetic progression. If the result matches, i'll return the said value. The time complexity will be O(N) i guess? There! Hope this helps! answered 31 Jul '17, 10:47 65●4 accept rate: 9% how u find range of min(0,x-2) to x+2,please elaborate (31 Jul '17, 11:06) vivek961★ It's Time complexity is O(1) not O(n) (31 Jul '17, 11:07) You don't have to check within a range if you use ceil() function. Then the answer is just: ceil(-0.5 + sqrt(1 + 8*m)/2) (31 Jul '17, 11:57) But during contest some times it's hard(atleast for me) to see if we have to take ceil or floor, and even after that it will cover it all.. so I will suggest to better take range approach rather than submitting wrong solution by chance.. :) (31 Jul '17, 12:05)
 0 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 0★nano28 1 accept rate: 0%
 0 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+i-2m <= 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 1★mranjan 1●1 accept rate: 0% 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) mranjan1★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,698
×2
×2

question asked: 31 Jul '17, 09:18

question was seen: 545 times

last updated: 01 Aug '17, 23:05