OJ Board

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....

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

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.

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.

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...

Do you get time-out?

-edit: I have the same number of solutions -

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 ; write:
I think this will help u. Wish u good luck

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


}

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

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

cutt off

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

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?

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