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

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

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

For IRA

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;
}

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

don't use my snippet code to be part of your program,
my snippet code is wrong because I don't write the last operation that
consume O(1) before return out2.

Hope it help you

:D
"Life is more beautiful with algorithm"

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

Post by IRA » Sun Apr 23, 2006 5:24 am

Code: Select all

#define I long long

I CSOD(I n) 
{ 
   I i,out=0,j=sqrt(n),k=n/2;

   for(i=2;i<=j;i++) 
     out += (n/i)*i; // O(sqrt(n)) 
   
   j=n/(j+1); 
  
   for(;j>=2;j--) { out += (j*((i+n/j)*(n/j-i+1)/2)); i=n/j+1; } // O(sqrt(n)) 
   out=out-????????????????????????????????????????;

   return out; 
} } 
I think that I have know your method.
Thanks, Timo

========================================
I already got AC!

sethos
New poster
Posts: 2
Joined: Mon Nov 13, 2006 4:21 pm

still TLE

Post by sethos » Mon Jan 08, 2007 2:03 pm

Hi,
This is a very nice problem, but i thought it would be easier... :(

i came to allmost the same formula as mentioned here in the forum, but i allways get TLE

here is my code: where can i optimize it?

Code: Select all

#include <iostream> 
#include <math.h> 
#include<string> 
#include <stdlib.h> 
#include<algorithm> 
#define I long long 

using namespace std;

int main()
{
    long inp, n ; 
   
    for(int i=1; i<200; i++){
    cin >> n; 

    
    if(n == 0) break;
    I total = 0;
        for(I t=2; t<n; t++){
        
        total+=(n/t)*t-t;
        }

    cout <<"Case "<<i<<": "<< total << "\n";
 }
return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jan 08, 2007 11:47 pm

Your complexity is O(n), you can reduce it to O(sqrt(n)).
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 108 (10800-10899)”