11411 - MiniMice

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

Moderator: Board moderators

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

11411 - MiniMice

Post by t_sergiu » Thu Apr 17, 2008 3:41 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 11411 - MiniMice

Post by Jan » Fri Apr 18, 2008 2:04 am

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

Post by t_sergiu » Sun Apr 20, 2008 1:14 am

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

Post by t_sergiu » Sun Apr 20, 2008 6:03 am

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
Location: Dhaka, Bangladesh
Contact:

Re: 11411 - MiniMice

Post by Jan » Sun Apr 20, 2008 12:50 pm

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?
About the sieve idea:
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

Post by MRH » Tue Nov 25, 2008 1:55 pm

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

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

Re: 11411 - MiniMice

Post by sohel » Wed Nov 26, 2008 7:21 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”