Best Way to Solve this LOC July Easy Problem?

help
, ,
1

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?

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

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

4

but every time equation is different,so quadratic also.

5

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?

6

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.

7

just one word arithmetic progression!!

8

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.

9

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!

10

so how can we use binary search? elaborate it

11

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

12

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

13

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

14

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
15

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)

16

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:

17

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
18

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

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