ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1091. Tmutarakan Exams

Did anybody else solve this problem using backtracking?
Posted by Victor Vernescu 13 Mar 2003 17:35
I used an optimized backtracking algorithm! I'm curious if anybody
else found a similar solution. Anybody?
i had solved it right now in 0.02
Posted by Locomotive 13 Mar 2003 18:04
dont backtracking
Re: Did anybody else solve this problem using backtracking?
Posted by Marcin Mika 14 Mar 2003 00:14
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...
Posted by Locomotive 14 Mar 2003 10:00
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?
Posted by Victor Vernescu 14 Mar 2003 11:16
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!