10830 - A New Function

[misof]

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]

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]

Simply nitpicking, so excuse me

- 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]

Simply nitpicking, so excuse me

- 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]

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!!!

[shahriar_manzoor]

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]

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

[helloneo]

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]

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]

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]

root(N) = sqrt(N)

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

[IRA]

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]

never mind..

[Timo]

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

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

[Timo]

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

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

I hope you understand