524 - Prime Ring Problem

[Heartattack!]

For n = 2, output should be

Code: Select all

1 2

For n=2, shouldn't the output be
1 2
2 1
?

I haven't tried this problem yet, but the prob desc. does say clockwise and anticlockwise. And the sample input consists of lines that mirror perfectly....

[Heartattack!]

Oops, sorry. The output for 2 should indeed be 1 2 and nothing else. "The first number has to be 1."

[Sedefcho]

I have an accepted Java program. Java is much slower as u know.
I've had cases in the past where I solve one problem
with Java for let's say time X. Then I rewrite my program in
C using absolutely the same algorithm.
And the C program gets runtime of about ( X / 50.0 ) meaning
that it is let's say 50 times faster.
Still I prefer Java as I am better in Java and as long as my prog
does not get TLE in Java and don't bother rewritting it in C.

So even with Java I get an ACC here and I use backtracking.

The reason my backtracking is reasonably fast is it that it does
quite some prunning.

1) I pregenerate the list of all possible successors of
a given number K. For example - suppose we are running
the program with N = 16 and we have currently an array
with 8 numbers already filled in:
1 2 3 4 / 7 6 5 12 / 0 0 0 0 / 0 0 0 0
So we want to put our 9th number.
We just scan the list of the possible successors of
12 ( let's say 12 = K ) .
The successors should be integers between
X = 1 and X = N and should
be such that X + 12 is prime.
N is 16 in our case.

More prunning: out of this list ( of successors ) we exclude also
those successors of 12 which are already in our array.
So we should exclude 7 for instance as it is already in
our array: see above that arr[4] == 7.

And of course 7 is a successor of 12 as 7 + 12 is prime
and 1 <= 7 <= N ( N is 16 ) .

Of course my java prog runs for quite some time - about
8 secs but still gets accepted.

Write me if you want to use the same algorithm but there's
something you dont understand in it.

[Sedefcho]

One more thing.

2) When you want to exclude a successor because it is already
in the array ( as with arr[4] in the above mentioned example )
do not scan your array up to the last number ( the 8th one).
Keep an array used[1...17] showing which of the numbers
1...N you have used so far.

And keep this array having accurate values during
the execution of your backtracking algorithm.

[Masud]

I dont know what is the wrong with my code..
My code generates
case 2: 1 output
case 4: 2 outputs
case 6: 2 outputs
case 8: 4 outputs
case 10: 96 outputs
case 12: 1024 outputs
case 14: 2880 outputs
case 16: 81024 outputs
please help me out of here...

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>

int n,j,x[17];
int prime[32]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1};
void NextValue(int k)
{
	do
	{
	 j=0;
	 x[k]=(x[k]+1)%(n+1);
	 if(x[k]==0)return;
     if((k==n-1)&&!prime[x[0]+x[k]])
		continue;
	 
	 if(prime[x[k]+x[k-1]])
	       for(j=0;j<k;j++)
		      if(x[k]==x[j]) break;
	 if(j==k) return;
	}while(1);
}


void prime_ring(int k)
{
 do
 {
  NextValue(k);
  if(x[k]==0) return;
  if(k==n-1)
	{
	 for(int i=0;i<n;i++)
			printf("%d ",x[i]);
	 printf("\n");
	}
   else prime_ring(k+1);

 }while(1);
}


void main()
{
 int cas=0,f=0; 
 while(scanf("%d",&n)==1)
	{
	 if(f=1)printf("\n");
	 memset(x,0,sizeof(x));
	 printf("Case %d:\n",++cas);
	 x[0]=1;
	 prime_ring(1);
	 f=1;
	}
}

[Johan]

Do you get time-out?

-edit: I have the same number of solutions -

[Masud]

I dont get TLE.
It is WA....

[Kallol]

Dear Masud,

Ur program is completely right from first to last. Just a very silly and disgusting error is there. U r printing a whitespace after printing n numbers in each line in ur output.Thats why u r getting WA.

instead of ;

Code: Select all

    for(int i=0;i<n;i++) 
         printf("%d ",x[i]); 
    printf("\n");

write:

Code: Select all

   for(i=0;i<n-1;i++)
        printf("%d ",x[i]);
   printf("%d\n",x[n-1]);

I think this will help u. Wish u good luck

[Shuvra(CSE-BUET)]

Hi .
I read all the previous posts and now have gone mad about this problem.
I tried all the inputs and found my answer ok( for 16 checked also).
Now I find no way but to do that disgusting job again ,post my code.
I used backtracking and got WA after about 1.143 sec always.
......................................................................................................
#include <stdio.h>
int a[20];
int pr[32];

void p(int k,int n){
int i,t;
if(k==n && pr[a[k]+a[1]]==1 && pr[a[k]+a[k-1]]==1)
{

for(i=1;i<=n-1;i++)
printf("%d ",a);
printf("%d\n",a);

}
else if(k==n)
return;
else{
for(i=k;i<=n;i++)
{

t=a[k];
a[k]=a;
a=t;
if(pr[ a[k]+a[k-1]]!=1)
{
t=a[k];
a[k]=a;
a=t;

continue;

}
p(k+1,n);
t=a[k];
a[k]=a;
a=t;
}

}


}

void main(){
int i,j;
long int cas;

for(i=1;i<=32;i++)
pr=1;
for(i=2;i<=32;i++)
{
if(pr==0)
continue;
for(j=2*i;j<=32;j+=i)
pr[j]=0;
}
cas=1;
while(scanf("%d",&i)==1){
for(j=1;j<=i;j++)
a[j]=j;
printf("Case %ld:\n",cas);
cas++;
if(i>=2)
{
p(2,i);

}
printf("\n");
}


}

[Kallol]

a little silly mistake
dont print a blank line after the last case .

[Shuvra(CSE-BUET)]

Thanks Kallol for ur reply. I have now tried with that possibility also. But I got WA after 1.143 secs again.

[Kallol]

cutt off

[Kallol]

Your recursion is wrong.
It does give u all the combinations , but doesnt give them is sorted order.

For example, for input : 16
both ur code and my ACC code give 81024 lines.
but the last line for my output is:

1 16 15 14 9 10 13 6 11 12 7 4 3 8 5 2

but urs is:

1 16 15 2 3 4 13 6 5 14 9 8 11 12 7 10

Few tips:
*every line will start with 1
*only even numbers will sit in even positions and odd ones in odd positions
*no but a blank line output for a odd input

happy trying

[vijay03]

Is backtracking the only way to solve the prime ring problem? In my program i found out all the permutations and checked whether a given one may satisy the conditions. When i tried out on my comp it gave the results reasonably fast but OJ is giving TLE. So is back tracking a must for this question?

[smilitude]

your code is too complicated to understand, plz use the code button from the top of the editing panel.