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:

Post by Heartattack! » Thu Nov 25, 2004 3:24 pm

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.... :D
We will, We will BREAK LOOP!!!!

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

Post by Heartattack! » Fri Nov 26, 2004 8:41 am

Oops, sorry. The output for 2 should indeed be 1 2 and nothing else. "The first number has to be 1." :oops: :oops: :oops: :oops:
We will, We will BREAK LOOP!!!!

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

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

Post by Sedefcho » Mon Feb 07, 2005 4:29 pm

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.

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

one more thing about the backtracking algorithm

Post by Sedefcho » Mon Feb 07, 2005 4:34 pm

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

Post by Masud » Sat May 06, 2006 1:56 am


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

Post by Johan » Sat May 06, 2006 2:35 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

Post by Masud » Tue May 09, 2006 12:42 am


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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 17, 2006 6:09 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

Post by Shuvra(CSE-BUET) » Sun Aug 13, 2006 12:30 pm

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Aug 17, 2006 11:21 am

a little silly mistake :lol:
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

Post by Shuvra(CSE-BUET) » Thu Aug 17, 2006 6:58 pm

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Aug 17, 2006 8:06 pm

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Aug 17, 2006 8:06 pm

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?

Post by vijay03 » Wed Sep 20, 2006 5:32 pm

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?

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Fri Oct 06, 2006 11:38 pm

your code is too complicated to understand, plz use the code button from the top of the editing panel.
fahim
#include <smile.h>

Post Reply

Return to “Volume 5 (500-599)”