I used an optimized backtracking algorithm! I'm curious if anybody
else found a similar solution. Anybody?

dont backtracking

this is an exercise in dynamic programming.

#include <stdio.h>
#include <string.h>
#define min(x,y) ( (x)<(y)?(x):(y) )
#define max(x,y) ( (x)>(y)?(x):(y) )

int gcd( int a, int b ){
if ( !a ) return b;
return gcd(b%a,a);
}

int n, b, f;

int ways[51][51][51];

int getways( int d, int g, int last ){
if ( d==n ) return 1;

if ( ways[d][g][last] < 1000000 ) return ways[d][g][last];

int s=0, i,j;
for ( i=last; i<=b; i++ )
    if ( (j=gcd(i,g)) > 1 )
        s=min( 10000, s+getways(d+1,j,i+1) );

return ways[d][g][last]=s;
}

int main( void ){
memset( ways, 66, sizeof(ways) );

scanf( "%d %d", &n, &b );
printf( "%d\n", getways(0,0,2) );

return 0;
}


> I used an optimized backtracking algorithm! I'm curious if anybody
> else found a similar solution. Anybody?
how did you optimize a backtracking algorithm to be fast enough?

Hi
Just find number of set (with size k) which have a prime common
divisor such as for k=2 and prime=3 (s=12):
{3, 6}
{3, 9}
{3,12}
{6, 9}
{6,12}
{9,12}
so do it for all prime numbers in range [1..50] then
delete sets wich all number in it have 2 prime common divisor
together...
such delete sets which all have common divisor such as 6 (which is
multpy of just 2 prime number) because set (6,12)
both counted when prime was 2 and when prime was 3
and etc.
and we have no set which its numbers has 3common prime divisor because
first 3 primes are 2, 3 and 5 and 2*3*5=30 and at least 2*30>50
so it will get so simple :)
Best
Aidin_n7@hotmail.com

Dudes! I know how to solve it!!!! I just asked if anybody else
implemented a good enough backtracking to fit into the alloted time!
That was all!!!! :D

I made a DP exercise into a back optimization exercise!