10830 - A New Function

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

Moderator: Board moderators

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Mar 23, 2005 12:25 pm

Andrey: You solve the small cases correctly. However, if you try the larger test case above, your results won't be correct. I wonder why didn't you try this out before posting.

Moreover, I wonder that the code you posted here does even compile on the judge. Are you sure that your WA wasn't acutally a Compile error?

Is your code supposed to be C or C++? If C++, then IMHO you need at least:
- use the std namespace
- main() must return int
- the return value of main() must be zero
- typecast the n in sqrt(n) to double

In C there is IMHO no iostream.h header file... and the part about returning zero (i.e. terminating correctly) remains the same.

Please explain.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Mar 23, 2005 12:50 pm

To Andrey:

if you change this line

Code: Select all

long n,t,i,s=0;
by this

Code: Select all

long long n,t,i,s=0;
you will obtain AC.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 23, 2005 12:59 pm

Simply nitpicking, so excuse me
misof wrote: - main() must return int
strictly speaking yes ... actually otherwise the compiler will take it up and add some code before and after main().
- the return value of main() must be zero
Well not exactly, the fact remains that main is just about as normal as any
other C function save and except its polymorphic forms(dont start a war on this now) .So it can return any value.A return value of zero is usually the programs way of saying to the OS - `yep!i didn't screw up'.Non zero return codes are sort of signals as what went wrong.

I forgot which one C99 perhaps, and dont shoot me if its otherwise, the braces at the begining and end of main are enough (so that a `return 0;' statement is not explicitly required ) for a compiler that conforms to that standard.
- typecast the n in sqrt(n) to double
Not required in C, though most C++ compilers will make you do it by sheer muscle.
And did we stop? Why we can still go on ...

Code: Select all

 int main() 
should be replaced by

Code: Select all

 int main(void) 
if that is what you indeed - a null list of parameters, otherwise it means that the parameter list is unspecified etc etc.

Suman.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed Mar 23, 2005 2:34 pm

sumankar wrote:Simply nitpicking, so excuse me
misof wrote: - main() must return int
strictly speaking yes ... actually otherwise the compiler will take it up and add some code before and after main().
- the return value of main() must be zero
Well not exactly, the fact remains that main is just about as normal as any
other C function save and except its polymorphic forms(dont start a war on this now) .So it can return any value.A return value of zero is usually the programs way of saying to the OS - `yep!i didn't screw up'.Non zero return codes are sort of signals as what went wrong.

I forgot which one C99 perhaps, and dont shoot me if its otherwise, the braces at the begining and end of main are enough (so that a `return 0;' statement is not explicitly required ) for a compiler that conforms to that standard.
These two points were not about the C language standard, they were an advice about programming contests. Most of the judges (and I think that the judge at UVa is no exception) require the tested program to end with exit code 0 as a sign that it terminated correctly. Any other return value is considered to be a runtime error.

Thus it is recommended to have int main() and to finish your program by return 0; If you have void main(), you cannot guarantee that the exit code will be 0.

(In fact, most probably will the return value be somehow connected to result of the last statement executed before the program ended. E.g. if the last statement was a printf(), the return value will be the number printf returned [the number of elements it printed].)
- typecast the n in sqrt(n) to double
Not required in C, though most C++ compilers will make you do it by sheer muscle.[/quote]

Yes, but that's exactly what I was saying :) As you can probably see from my post, this was indeed in the "C++" set of comments. The g++ compiler does strict type checking and it won't compile the code Andrey posted.

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

Post by Andrey » Wed Mar 23, 2005 2:48 pm

I change line

Code: Select all

long  n,t,i,s=0; 
to line

Code: Select all

long long n,t,i,s=0;
And got AC!!!

Thank's Emilio !!
And others!!

Sorry for my English!!! :oops:

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Wed Mar 23, 2005 3:27 pm

Andrey,
Then you should remove your code from the message board. I have lost my right to delete any post after the board have been upgraded. Otherwise I would have done it.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Mar 24, 2005 7:34 am

Maybe the fault is mine.
I would must have sent a Private Message.

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

Post by helloneo » Mon Apr 10, 2006 6:39 pm

Eduard wrote:Hello.
I dont think it's hard to find this formula.
CSOD(n)=P-n+1 P=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n
But for calculating it I must do N operations,it is too slow.Can this formula calculated faster?
Eduard
I'm sorry but..
could anybody explain how we can get that formula..?

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Thu Apr 20, 2006 8:45 pm

helloneo wrote:
Eduard wrote:Hello.
I dont think it's hard to find this formula.
CSOD(n)=P-n+1 P=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n
But for calculating it I must do N operations,it is too slow.Can this formula calculated faster?
Eduard
I'm sorry but..
could anybody explain how we can get that formula..?
like this....

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12...
   x   2    2    2     2       2
     x       3      3           3
        x          4             4
           x             5
              x                   6
so... CSOD(12)= ([12/2]-1)*2+([12/3]-1)*3+([12/4]-1)*4+([12/5]-1)*5+([12/6]-1)*6 ........
and find the formula....

I have a problem...
How could i find the sum of the folloing S function?
S= [n/2]*2+[n/3]*3+...+[n/(n/2)]*(n/2)
Please help me....

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Thu Apr 20, 2006 9:17 pm

.. wrote:In my previous post I don't want to give too much detail as I don't want to write spoiler..... Here is the detail:

Code: Select all

CSOD(n)=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n 
       =(n div 2)*2 + (n div 3)*3 + ..... + (n div n)*n - sum(2,n)
The value of "n div x" will repeat when x becomes larger, and when x > root(N), n div x <= root(N), and I just try all such n div x as value K.

And so the complexity is root(N)
What is root(N) ?

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Fri Apr 21, 2006 10:19 am

root(N) = sqrt(N)

root(25) = 5
root(36) = 6

:D
"Life is more beautiful with algorithm"

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Fri Apr 21, 2006 2:01 pm

.. wrote:In my previous post I don't want to give too much detail as I don't want to write spoiler..... Here is the detail:

Code: Select all

CSOD(n)=((n div 2)-1)*2+((n div 3)-1)*3 +...+((n div n)-1)*n 
       =(n div 2)*2 + (n div 3)*3 + ..... + (n div n)*n - sum(2,n)
The value of "n div x" will repeat when x becomes larger, and when x > root(N), n div x <= root(N), and I just try all such n div x as value K.

And so the complexity is root(N)
>>>And so the complexity is root(N)
I don't know why the complexity is sqrt(N) ?

Who can explain it ?

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

Post by helloneo » Fri Apr 21, 2006 5:08 pm

never mind..
Last edited by helloneo on Sun Apr 23, 2006 4:46 am, edited 1 time in total.

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Apr 22, 2006 5:13 am

Code: Select all

#define I long long
I CSOD(I n)
{
	I i,out2=0,j=sqrt(n);
	for(i=2;i<=j;i++) out2 += (n/i)*i; // O(sqrt(n))
	for(i--;j>=1;j--) { out2 += (j*sum(i+1,n/j)); i=(n/j); } // O(sqrt(n))
        // last operation before return only take O(1)
	return out2;
}

maybe you can understand why the time complexity is O(sqrt(n))
if see my snippet code :D

my snippet code is wrong because I don't write the last operation that
consume O(1) before return out2.
"Life is more beautiful with algorithm"

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Apr 22, 2006 5:15 am

Code: Select all

#define I long long
I CSOD(I n)
{
	I i,out2=0,j=sqrt(n);
	for(i=2;i<=j;i++) out2 += (n/i)*i; // O(sqrt(n))
	for(i--;j>=1;j--) { out2 += (j*sum(i+1,n/j)); i=(n/j); } // O(sqrt(n))
        // last operation before return only take O(1)
	return out2;
}

maybe you can understand why the time complexity is O(sqrt(n))
if see my snippet code :D

my snippet code is wrong because I don't write the last operation that
consume O(1) before return out2.

I hope you understand
:D
"Life is more beautiful with algorithm"

Post Reply

Return to “Volume 108 (10800-10899)”