11526 - H(n)

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

11526 - H(n)

Post by zobayer » Fri Oct 17, 2008 5:13 pm

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 :D :D :D
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!!!
Last edited by zobayer on Sat Nov 29, 2008 3:43 pm, edited 6 times in total.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Fri Oct 17, 2008 5:21 pm

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
}
Last edited by zobayer on Sat Nov 29, 2008 3:38 pm, edited 2 times in total.
You should not always say what you know, but you should always know what you say.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n) TLE

Post by abid_iut » Wed Nov 26, 2008 4:30 pm

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
Last edited by abid_iut on Tue Dec 23, 2008 11:52 am, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Fri Nov 28, 2008 10:15 pm

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
You should not always say what you know, but you should always know what you say.

Fluffymoo
New poster
Posts: 7
Joined: Wed Oct 15, 2008 5:05 pm

Re: 11526 - H(n)

Post by Fluffymoo » Sat Nov 29, 2008 12:22 am

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

Fluffymoo
New poster
Posts: 7
Joined: Wed Oct 15, 2008 5:05 pm

Re: 11526 - H(n)

Post by Fluffymoo » Sat Nov 29, 2008 2:51 pm

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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Sat Nov 29, 2008 3:41 pm

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

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n)

Post by abid_iut » Sun Nov 30, 2008 7:36 am

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.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Sat Dec 06, 2008 5:09 pm

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"
You should not always say what you know, but you should always know what you say.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11526 - H(n)

Post by Obaida » Thu Dec 18, 2008 10:36 am

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

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;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n)

Post by abid_iut » Thu Dec 18, 2008 12:11 pm

trying
Last edited by abid_iut on Thu Dec 18, 2008 3:23 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11526 - H(n)

Post by Obaida » Thu Dec 18, 2008 12:31 pm

I got TLE and thinking of a good method. I want someone to help me. :-?
try_try_try_try_&&&_try@try.com
This may be the address of success.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11526 - H(n)

Post by helloneo » Thu Dec 18, 2008 1:36 pm

Obaida wrote: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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11526 - H(n)

Post by Articuno » Thu Dec 18, 2008 6:26 pm

Thanks to helloneo. Your hint was very useful for me.
Thanks a lot again. :D
May be tomorrow is a better day............ :)

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n)

Post by abid_iut » Fri Dec 19, 2008 8:23 pm

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...
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Post Reply

Return to “Volume 115 (11500-11599)”