How to solve this?

general
1

problem HOLDIL Problem - CodeChef

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

2

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
3

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

Solution using binary search.

Solution using reordering of queries.

1 Like
4

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

5

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

6

No problem mate. :slight_smile:

1 Like
7

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
8

thanks a lot