How to solve this?

problem https://www.codechef.com/problems/HOLDIL

Can anyone tell me a nice approach with a example to solve this problem

In this problem, we basically need to find N, such that S = 1^2 + 2^2 + 3^2 … N^N such that S <= Given Value and N is maximized.

Now, above summation can also be written as S = N*(N+1)(2N+1)/6.

So we need maximum value of N such that N*(N+1)(2N+1)/6 <= Given volume.

Now, we can do a simple binary search and get the answer in O(logN) time.

For binary Search, you may take left bound as 0 and right bound as 1e6. (because above expression is cubic and for values of N > 1e6, expression may overflow long range.)

I’ll post the solution soon.

A simple mathematical solution also exist, using above expression, but i won’t tell you. :slight_smile:

Enjoy.

1 Like

Give problems a try before rushing to solutions. :slight_smile:

Solution using binary search.

Solution using reordering of queries.

1 Like

Another solution exist using reordering queries if you are not fond of binary search.

Access denied on the link to your solution.I had already solved this problem using brute force but i wanted to know some better approach and thanks a lot for the help

No problem mate. :slight_smile:

1 Like

Anyways, Here’s binary search function. (Take l = 0, r = 1e6)

static long ans(long value, long l, long r){
    long mid = (l+r)/2;
    long sum = (mid*(mid+1)*(2*mid+1))/6, sum2 = ((mid+2)*(mid+1)*(2*mid+3))/6;
    if(value >= sum && value < sum2)return mid;
    if(value >= sum2)return ans(value, mid+1, r);
    return ans(value,l,mid-1);
}
1 Like

thanks a lot