## 524 - Prime Ring Problem

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:
Sanny wrote: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....
We will, We will BREAK LOOP!!!!

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:
Oops, sorry. The output for 2 should indeed be 1 2 and nothing else. "The first number has to be 1."
We will, We will BREAK LOOP!!!!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Backtracking + Some decent prunning -> ACC ( even in JAVA

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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### one more thing about the backtracking algorithm

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
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Location: Bangladesh
Contact:

### 524

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;
}
}

``````
Hi I am Masud...

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm
Do you get time-out?

-edit: I have the same number of solutions -

Masud
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Location: Bangladesh
Contact:

### i dont get TLE

I dont get TLE.
It is WA....
Hi I am Masud...

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

### 524(prime ring) but i am in WA ring

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");
}

}
Life is a challenge.

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
a little silly mistake
dont print a blank line after the last case .
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

### WA ring

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

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
cutt off
Last edited by Kallol on Thu Aug 17, 2006 8:12 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
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
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

vijay03
New poster
Posts: 33
Joined: Wed Sep 13, 2006 6:46 pm
Contact:

### 524 - The Prime Ring Problem - Is backtracking the only way?

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
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
your code is too complicated to understand, plz use the code button from the top of the editing panel.
fahim
#include <smile.h>