Re: Did anybody else solve this problem using 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?

Inclusion relation...

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

Re: Did anybody else solve this problem using backtracking?

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!