Programming Forums > Application Development > Software Design and Algorithms

Sane · Jun 2nd, 2008, 4:21 PM

Attached to this post is the test data for Ranged Reach (Advanced).

This problem requires a brute forced solution with some careful optimizations.

Since the input is restricted to [a,b] = [1,100000] and k=50, it is okay to try every possibile n value, and count the number of n values which produce an nRk within the given range. But taking the solution from Junior and modifying it for just that is not enough. We need to be a little bit smarter.

The first optimization that we can use is the Prime Sieve of Eratosthenes. This is a relatively intuitive prime number generator that I'm sure you could come up on your own with a little bit of thought.

Essentially, you start by considering every number to be prime (except for 0 and 1). Since no multiples of 2 can be prime, you unmark all multiples of 2, starting at the first prime+2 (4). Since no multiples of 3 can be prime, you unmark all multiples of 3, starting at the next prime+3 (6). Since no multiples of 5 can be prime, you unmark all multiples of 5, starting at the next prime+5 (10).

And so on and so forth...

We repeat this process up until the square root of the maximum range (sqrt(100,000)), and what we end up with is a very efficient way of precalculating all potential prime numbers. From now on, all primality tests become a constant time operation involving indexing a location in an array.

Here is my implementation of the Sieve of Eratosthenes:

(Toggle Plain Text)

#define MAXP 100001
int isprime[MAXP];

void genprimes() {
    int i, p=2;
    for(i=0; i<MAXP; i++) primes[i] = 1;
    primes[0] = 0;
    primes[1] = 0;
    while(p*p < MAXP) {
        for(i=p*2; i<MAXP; i+=p) 
            primes[i] = 0;
        while(!primes[++p]) continue;
    }
}

Here is our new and improved primality test:

(Toggle Plain Text)

#define isprime(x) ((x)<0?0:primes[(x)])

And here is the Wikipedia article on the Sieve of Eratosthenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The other necessary optimization is a cache within the original reach function. Here is the original solution from Junior:

(Toggle Plain Text)

int reach(int n, int i, int k) {
    int r;
    if(i>k) return n;
    
    r = max(reach(n+i, i+1, k),   // Option #1
            reach(n-i, i+1, k));  // Option #2
    if(isprime(n))                // Option #3
        r = max(reach(n*2, i+1, k),  r);
    
    return r; // Return the maximum possible value from all 3 options
}

We now use a "trick" identical to that of Dynamic Programming. We solve repeated subproblems by never repeating the same function call twice. But since the numbers can be negative, and there are a couple restrictions on the limits, it's simpler to stick with recursion+caching rather than iterative DP. A recursive function with a cache will have the same run-time complexity as an iterative DP function, except it will be slowed down a fair bit due to the overhead of recursion. The difference is negligible in this case.

Observe that every time we call reach(n,i,k), the result will always be distinct for the parameters (n,i) (since k is constant). That means we can wrap the function with a cache which takes values (n,i) and returns the result if it has already been calculated.

(Toggle Plain Text)

int reach(int n, int i, int k) {
    int x, y, z;
    
    if(n<MIN)  return low-1;  // nRk will be outside range
    if(n>high) return high+1; // nRk will be outside range
    if(i>k)    return n;
    
    if(cache(n,i) != NIL) return cache(n,i);
    
    x = reach(n+i, i+1, k);
    y = reach(n-i, i+1, k);
    if(isprime(n)) z = reach(n*2, i+1, k);
    else           z = NIL;

    return cache(n,i) = max(max(x,y),z);
}

With the number of subproblems proportional to $O((max_n - min_n)(k))$ , that corresponds to about 5 million operations for the worst case, which should run in time.

The last thing that needs addressing is the maxmimum and minimum n values that could possibly produce an nRk within [a, b]. The purpose of this is three-fold: to determine where we should stop the reach function, to determine the constraints of our cache, and to determine over what range we need to test each n value.

Firstly, the lower bound of the range is always a >= 1. So, we only need to consider n values which can possibly achieve an nRk > 0.

If n is negative, its nRk will always be calculated by increasing n by 1, 2, 3, ... k, until it's positive. Why is this true? Because negative numbers are not prime, and the only other option would cause the number to become more negative.

Therefore, given k, the minimum n is the negative sum of the arithmetic sequence from 1 .. k, which is approximately -1,500 for k=50. Thus, any n<-1500 could never possibly have an nRk >= a.

The maximum n is always the value of b minus the arithmetic sequence from 1 .. k. But instead of wasting brain cells and risking off-by-1 errors by mathematically determining this value, it suffices to consider the maximum n to equal b. If n were any higher than b, its nRk would be > b (proof of this should be intuitive). Thus, any n>b could never possibly have an nRk <= b.

With the maximum and minimum n in place, the solution fits together nicely. It may be somewhat repulsive, but it gets the job done in time:

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <math.h>
 
#define MIN -1500
#define SIZE 105001
#define MAXP 100001
#define NIL -1000000
#define K 51
 
#define cache(n,i) (docache[(n)-MIN][(i)])
#define isprime(x) ((x)<0?0:primes[(x)])
#define max(a,b) ((a)>(b)?(a):(b))
 
int primes[MAXP];
int docache[SIZE][K];
int low, high;
 
int reach(int n, int i, int k) {
    int x, y, z;
 
    if(n<MIN)  return low-1;  // nRk will be outside range
    if(n>high) return high+1; // nRk will be outside range
    if(i>k)    return n;
 
    if(cache(n,i) != NIL) return cache(n,i);
 
    x = reach(n+i, i+1, k);
    y = reach(n-i, i+1, k);
    if(isprime(n)) z = reach(n*2, i+1, k);
    else           z = NIL;
 
    return cache(n,i) = max(max(x,y),z);
}
 
void genprimes() {
    int i, p=2;
    for(i=0; i<MAXP; i++) primes[i] = 1;
    primes[0] = 0;
    primes[1] = 0;
    while(p*p < MAXP) {
        for(i=p*2; i<MAXP; i+=p) 
            primes[i] = 0;
        while(!primes[++p]) continue;
    }
}
 
int main() {
    int a, b, i, x, k, c;
 
    freopen("ranger.in", "rt", stdin);
    freopen("ranger.out", "wt", stdout);
 
    scanf("%d %d %d", &low, &high, &k);
    for(a=0; a<SIZE; a++)
        for(b=0; b<K; b++) 
            docache[a][b] = NIL;
 
    genprimes();
    for(c=0, i=MIN; i<=high; i++) {
        x = reach(i, 1, k);
        if(x >= low && x <= high) c++;
    }
 
    printf("%d\n", c);
    return 0;
}
#include <stdio.h>
#include <math.h>

#define MIN -1500
#define SIZE 105001
#define MAXP 100001
#define NIL -1000000
#define K 51

#define cache(n,i) (docache[(n)-MIN][(i)])
#define isprime(x) ((x)<0?0:primes[(x)])
#define max(a,b) ((a)>(b)?(a):(b))

int primes[MAXP];
int docache[SIZE][K];
int low, high;

int reach(int n, int i, int k) {
    int x, y, z;
    
    if(n<MIN)  return low-1;  // nRk will be outside range
    if(n>high) return high+1; // nRk will be outside range
    if(i>k)    return n;
    
    if(cache(n,i) != NIL) return cache(n,i);
    
    x = reach(n+i, i+1, k);
    y = reach(n-i, i+1, k);
    if(isprime(n)) z = reach(n*2, i+1, k);
    else           z = NIL;

    return cache(n,i) = max(max(x,y),z);
}

void genprimes() {
    int i, p=2;
    for(i=0; i<MAXP; i++) primes[i] = 1;
    primes[0] = 0;
    primes[1] = 0;
    while(p*p < MAXP) {
        for(i=p*2; i<MAXP; i+=p) 
            primes[i] = 0;
        while(!primes[++p]) continue;
    }
}

int main() {
    int a, b, i, x, k, c;
    
    freopen("ranger.in", "rt", stdin);
    freopen("ranger.out", "wt", stdout);
    
    scanf("%d %d %d", &low, &high, &k);
    for(a=0; a<SIZE; a++)
        for(b=0; b<K; b++) 
            docache[a][b] = NIL;
        
    genprimes();
    for(c=0, i=MIN; i<=high; i++) {
        x = reach(i, 1, k);
        if(x >= low && x <= high) c++;
    }
    
    printf("%d\n", c);
    return 0;
}

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SMAC #1 [05-08] - Results	Sane	Software Design and Algorithms	6	Jun 2nd, 2008 4:56 PM
SMAC #1 [05-08] - Hurtles (Senior)	Sane	Software Design and Algorithms	0	Jun 1st, 2008 3:59 PM
Ideas for my Senior Project?	joshbax88	Java	1	Apr 26th, 2008 5:57 AM
Architect / Senior Programmer : Asp.net / C#	techsupport	C#	3	Mar 7th, 2006 9:47 AM
Senior Capstone-Spying Screen Saver	Hounder	Project Ideas	23	Dec 16th, 2005 7:00 PM

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Software Design and Algorithms

SMAC #1 [05-08] - Ranged Reach (Senior)