## 11411 - MiniMice

Moderator: Board moderators

t_sergiu
New poster
Posts: 12
Joined: Sun Mar 02, 2008 6:18 am

### 11411 - MiniMice

Hi,

I am currently working on the MiniMice problem. My strategy is to first find all primes from 1 to 5000000, then all divisors of n for 1 <= n <= 5000000, store all of these in arrays, and then proceed with finding what the question asks for.

My problem is that I can't seem to find an algorithm efficient enough to run in under 6 seconds to find all the divisors. I am finding the primes by checking to see if n is divisble by any primes up to sqrt( n ). Then I'm finding all divisors by dividing n by the same prime until it can no longer be divided by that prime. In other words using the fact that for b1^(c1)*b2^(c2)*...bn^(cn), that there are (c1+1)(c2+1)...(cn+1) divisors.

Now, either my algorithm isn't efficient, or I'm doing a lot of extra stuff that I don't need to be doing. I don't see any more efficient manner in which to find all the divisors, so it's probably that I don't need to do all of this, and there's another way.

Can anybody offer some help?

Thanks.

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

### Re: 11411 - MiniMice

My method is not very efficient, but managed to get accepted.

The fact is for any n we don't need all the divisors , but wee actually need the number of divisors. Number of divisors can easily be found using sieve (idea).

Then I took all the number of divisors for each i (for i = a to b). Sort them using counting sort (idea). Then used greedy.
Ami ekhono shopno dekhi...
HomePage

t_sergiu
New poster
Posts: 12
Joined: Sun Mar 02, 2008 6:18 am

### Re: 11411 - MiniMice

Code: Select all

``````#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main()
{
//find all primes;
vector< int > primes;
primes.reserve( 400 );

primes.push_back( 2 );

for( int i = 3; i * i <= 5010000; i += 2 )
{
bool a = true;
for( unsigned int j = 0; j < primes.size() && primes[ j ] * primes[ j ] <= i; ++j )
{
if( i % primes[ j ] == 0 )
{
a = false;
break;
}
}
if( a )
primes.push_back( i );
}

int num;
cin >> num;

for( int m = 0; m < num; ++m )
{
int a, b;
cin >> a >> b;

int divs[ 400 ];
for( int i = 0; i < 400; ++i )
divs[ i ] = 0;

//find all divisors in the range, using idea that
//a maximum of 2 of each number of divisors is
//needed because after that difference is 0
for( int i = a; i <= b; ++i )
{
int temp = i;
int total = 1;
int count = 1;
int index = 0;

for( int j = primes[ index ]; j*j <= temp; j = primes[ ++index ] )
{
/*	for( int temp2 = temp / j; temp2 * j == temp; ++count )
{
temp = temp2;
temp2 = temp / j;
}*/

while( temp % j == 0 )
{
++count;
temp /= j;
}
total *= count;
count = 1;
}

if( temp != 1 )
total *= 2;

if( divs[ total ] < 2 )
divs[ total ]++;
}

//finds the maximum difference, could be improved
//by getting rid of the deque but the time this takes
//to run is really insignificant since its a max of less
//than 800 pushes
deque< int > sorted;
bool inFront = true;
for( int i = 0; i < 400; ++i )
{
if( divs[ i ] == 2 )
{
sorted.push_back( i );
sorted.push_front( i );
}
if( divs[ i ] == 1 )
{
if( inFront )
{
sorted.push_back( i );
inFront = false;
}
else
{
sorted.push_front( i );
inFront = true;
}
}
}
sorted.push_back( sorted.front() );

int sortsize = sorted.size() - 1;
int maxt = 0;
for( int i = 0; i < sortsize; ++i )
{
int t = abs( sorted[ i ] - sorted[ i + 1 ] );
if( t > maxt )
maxt = t;
}
cout << maxt << endl;
}

return 0;
}``````
This is the way that I have it right now. I don't know what you mean by sieve (idea), counting sort (idea), and greedy in your post. Could you please explain?

t_sergiu
New poster
Posts: 12
Joined: Sun Mar 02, 2008 6:18 am

### Re: 11411 - MiniMice

Ok, I got it to work by using the sieve idea. This got rid of all the divisions and multiplications in my loops.

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

### Re: 11411 - MiniMice

t_sergiu wrote:This is the way that I have it right now. I don't know what you mean by sieve (idea), counting sort (idea), and greedy in your post. Could you please explain?
You don't have to store the primes. But when calculating the primes you can update the multiples.

Code: Select all

``````factor[i] = 1; // for all i
for(i=2;i<MAX;i++) if(i is a prime)
for(j = all multiples of i)
{
find x // x is the largest number, j is divisible by i^x
factor[i] = factor[i] * (x+1);
}``````
So, before taking the input you can find all the factors. (Of course a lot more optimizations can be done!)

Now for any input take all the factors from a to b and store them in another array say a[]. Then my method requires to sort them. Now since there can be so many numbers O(n*log(n)) sorting will give you TLE. But we can see that the range of factors is small. So, O(n) sorting is possible (this is the counting sort idea).

Then try to figure out how the numbers should be taken such that the maximum difference is minimized. Hope these help.
Ami ekhono shopno dekhi...
HomePage

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### 11411 - MiniMice

PLZ HELP .THIS CODE GIVE WA

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define max 5000000
long prime[max+1],lod[ max+1];
void facto()
{
long i,j,temp,ss,count;
for(i=2;i<=max;i++)
{
if(prime==0)
{
temp=i;
prime=2;
for(j=2*i;j<=max;j+=i)
{
count=1;
ss=j;
while(ss%temp==0)
{
ss/=temp;
count++;
}
if(prime[j] != 0)
{
prime[j]*=count;
}
else
{
prime[j]= count;
}
}
}
}
}
int main()
{
facto();
long i,j,test,a,b,f,s;
scanf("%ld",&test);
while(test--)
{
scanf("%ld %ld",&a,&b);
f=-1;
s=-1;
for(i=a;i<=b;i++)
{
if(f<prime)
{
s=f;
f=prime;
}
else
{
if(s<prime && f!=prime)
{
s=prime;
}
}
}
printf("%ld\n",(f-s));
}
return 0;
}

WHERE IS MY WRONG ????

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11411 - MiniMice

# Search the board first!
# Don't create a new thread for a problem for which one already exists.
# Use code tags when posting codes.