11411 - MiniMice

[t_sergiu]

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]

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.

[t_sergiu]

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]

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

[Jan]

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.