Best Way to Solve this LOC July Easy Problem?

help
, ,
1

Problem link-CodeChef: Practical coding for everyone

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?

2

This will give TLE because of this constraint 1 ≤ N,M ≤ 10^18.

There are two solutions I am thinking right now:

  1. use simple inequality method and solve this quadratic as i*(i+1)/2 <= m => i^2+i-2*m <= 0 ; You can follow my solution here.

  2. 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.

2 Likes
3

just one word arithmetic progression!!

4

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 + 8*M))/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!

5

do we have to put long long int some where?. as my approach was wright but answer came out to be wrong.

6

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 :slight_smile:

1 Like
7

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

8

10^18 array is possible? so i think u can’t use binary search,thats why i dont

9

but every time equation is different,so quadratic also.

10

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?

11

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.

12

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.

13

so how can we use binary search? elaborate it

14

how u find range of min(0,x-2) to x+2,please elaborate

15

It’s Time complexity is O(1) not O(n)

16

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…

1 Like
17

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)

18

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… :slight_smile:

19

We cannot access your code since solutions arent visible. Please copy your code on ideone.com and give us link :slight_smile:

20

Ideone link:
http://ideone.com/e.js/xECbIx