You are not logged in. Please login at www.codechef.com to post your questions!

×

Best Way to Solve this LOC July Easy Problem?

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

vivek96's gravatar image

1★vivek96
518220
accept rate: 7%

edited 31 Jul '17, 09:22


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

link

answered 31 Jul '17, 09:32

kauts_kanu's gravatar image

5★kauts_kanu
1.1k19
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) kauts_kanu5★

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) kauts_kanu5★

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) kauts_kanu5★

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) kauts_kanu5★
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 :)

link

answered 31 Jul '17, 12:11

icpc_finalist's gravatar image

6★icpc_finalist
202
accept rate: 0%

edited 31 Jul '17, 12:14

just one word arithmetic progression!!

link

answered 31 Jul '17, 10:18

phantomhive's gravatar image

4★phantomhive
944
accept rate: 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!

link

answered 31 Jul '17, 10:47

seraphwedd_17's gravatar image

2★seraphwedd_17
654
accept rate: 9%

edited 31 Jul '17, 11:03

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) kauts_kanu5★

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) c_utkarsh5★

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) kauts_kanu5★

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

link

answered 31 Jul '17, 11:41

nano28's gravatar image

0★nano28
1
accept rate: 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

link

answered 01 Aug '17, 22:11

mranjan's gravatar image

1★mranjan
11
accept rate: 0%

edited 01 Aug '17, 23:04

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) vijju123 ♦♦4★
(01 Aug '17, 23:05) mranjan1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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