Page 2 of 3

Posted: Wed Mar 23, 2005 12:25 pm
by 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.

Posted: Wed Mar 23, 2005 12:50 pm
by 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.

Posted: Wed Mar 23, 2005 12:59 pm
by sumankar
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.

Posted: Wed Mar 23, 2005 2:34 pm
by misof
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.

Posted: Wed Mar 23, 2005 2:48 pm
by 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!!! :oops:

hmm

Posted: Wed Mar 23, 2005 3:27 pm
by 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.

Posted: Thu Mar 24, 2005 7:34 am
by Emilio
Maybe the fault is mine.
I would must have sent a Private Message.

Posted: Mon Apr 10, 2006 6:39 pm
by helloneo
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..?

Posted: Thu Apr 20, 2006 8:45 pm
by IRA
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....

Posted: Thu Apr 20, 2006 9:17 pm
by IRA
.. 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) ?

Posted: Fri Apr 21, 2006 10:19 am
by Timo
root(N) = sqrt(N)

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

:D

Posted: Fri Apr 21, 2006 2:01 pm
by IRA
.. 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 ?

Posted: Fri Apr 21, 2006 5:08 pm
by helloneo
never mind..

Posted: Sat Apr 22, 2006 5:13 am
by 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 :D

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

Posted: Sat Apr 22, 2006 5:15 am
by 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 :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