11526 - H(n)

[zobayer]

This code wants me to optimize the given function. I'm getting wa.. Help!
I've checked many small inputs & my program generates correct outputs pretty quickly.
For some large values my program generates following:

Now I've got AC
I wasn't taking care of inputs < 1. Following IO seems to be correct

Inputs:

Code: Select all

10
2147483647
2147483646
2147463645
2147463644
2147463643
2147463642
2147463641
2147463640
2147463639
2147463638

Output

Code: Select all

46475828386
46475828384
46475375550
46475375518
46475375512
46475375504
46475375472
46475375470
46475375406
46475375394

Thanks in advance.

GOT AC, DID A SILLY MISTAKE. MY SOLUTION WAS CORRECT!!!

[zobayer]

Oh, I didn't think about n<1...
I got AC;


Is there any O(lg n) solution? My O(n) solution took 0.400 s to pass Some one solve it in 0.280 seconds, can any one tell. what is the Idea.
Mine is as follows:

sum = n;
last_denominator = 1;
start_point = n;

for(i=2 to .., step 1)
{
end_point = n/i;
for all values in range after end_point to start_point will produce n/i = last_denominator
so , sum += (star_point - end_point) * lest_denominator;
now sum += n/i itself
last_denominator = current i;
start_point = end_point
}

[abid_iut]

to zubayer
i've done it as u said it gives me TLE, so i changed a bit but still TLE can u pls fix where is the problem
others also pls help

here is the code:

Code: Select all

Removed

[zobayer]

Hi Abid, I'm from CSE-DU

I think you are not much experienced in coding cause you tried to run a loop up to 2147483647 !!!!! This is insane, this should not run even in your PC, and look at the array of size [2147483647], some gigabyte are needed to hold this. No need to precalculate here (not possible I think), take one in ant put that out, its enough for this problem. Never try to run a loop up to a 7 digit (or more) number unless there is no other way. And always look for the memory you killing. Most problems have only 32 to 65 MB. and always use big sized arrays as global. Improve your coding by solving simply easier problems first, this is the way to excel in programming.

I'm still looking for a better algo for this.....
zobayer_1@live.com

[Fluffymoo]

From my analysis there may be a logn solution...i will post again soon

[Fluffymoo]

Well, it seems this problem has O(n)solution at best - > number of sums = n/x, where x is a product of function F(n), F(n) is not linear, more of a combination of linear and logarithmic function.

There might be a faster solution, but cba to find it :p

[zobayer]

@Fluffymoo you're right, this function is not quite linear. Can anybody post his algo who had it in less 0.350s ? please...

[abid_iut]

Thankx Zubayer,
Really I am not that good in coding, but I know what I did about the array size, actually I was angry. it was giving me trouble.
anyway thankx again and i will follow your suggestion. please give me a better algorithm if possible.

Zubayer pls help me about this:

I don't understand what does it menas:

Code: Select all

for(i=2;.....step1)

what is step 1.
please forgive me if there is a foolish question.

[zobayer]

Ha ha ha, nothing to be sorry here, actually I wanted to write in a pseudo code style, cause posting actual code is a spoiler here. BTW, for(i=2...step1) stands for ==> for(i=2; ; i++), got it? And there is a breaking condition somewhere, which I didn't mentioned, cause if you understand the logic, & try with some pen and paper, you will find it easily. I don't know any better algo than mine yet, mine is pretty good, but I think you didn't understand. Can you mail me so that I can give you the code, I think you will understand how it works.
zobayer_1@live.com
"love to do meaningless programming"

[Obaida]

can someone help me with logic. My 1 got TLE.

Code: Select all

#include<stdio.h>
int main()
{
	long long int n,res,mid,i;
	int m;
	scanf("%d",&m);
	while(m--)
	{
		scanf("%lld",&n);
		mid = n/2;
		res=0;
		for(i=1;i<=mid;i++)
		{
			res += n/i;
			res += n/(n-i+1);
		}
		if(n%2!=0)res+=n/(mid+1);
		printf("%lld\n",res);
	}
	return 0;
}

[abid_iut]

trying

[Obaida]

I got TLE and thinking of a good method. I want someone to help me.

[helloneo]

I got TLE and thinking of a good method. I want someone to help me.

You can solve this problem in O(sqrt(n))
For example, let n = 20

1 * 20 = 20
2 * 10 = 20
3 * 6 = 18
4 * 5 = 20
--------------------- the process below is not necessary
5 * 4 = 20
6 * 3 = 18
7 * 2 = 14
8 * 2 = 16
9 * 2 = 18
10 * 2 = 20
11 * 1 = 11
12 * 1 = 12
13 * 1 = 13
14 * 1 = 14
15 * 1 = 15
16 * 1 = 16
17 * 1 = 17
18 * 1 = 18
19 * 1 = 19
20 * 1 = 20

Try to find a formula or something..

[Articuno]

Thanks to helloneo. Your hint was very useful for me.
Thanks a lot again.

[abid_iut]

hey helloneo
I am not very clear about ur post
can U pls explain a bit more
what is the output for input 20 pls explain...