524 - Prime Ring Problem

[Larry]

if you get OLE, then perhaps you're reading input in wrong, and go into an endless loop, which prints too much..

just a possibility..

[CDiMa]

Hi,
I got my solution accepted for this prob, but I'm pretty puzzled by the P.E.
The problem statement doesn't specify precisely the output format :

The output format is shown as sample below.

Here is my output for the sample input:

Code: Select all

Case 1:
1 4 3 2 5 6 
1 6 5 2 3 4 

Case 2:
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2 

It looks precisely like the sample output...
Maybe the error comes with two cyphers numbers?
I don't align cyphers, like this snippet from the output for n=10

Code: Select all

Case 1:
1 2 3 4 7 6 5 8 9 10 
1 2 3 4 7 10 9 8 5 6 
1 2 3 4 9 8 5 6 7 10 
1 2 3 8 5 6 7 4 9 10 
1 2 3 8 5 6 7 10 9 4 
1 2 3 10 7 4 9 8 5 6 
1 2 3 10 7 6 5 8 9 4 
1 2 3 10 9 8 5 6 7 4 
1 2 5 6 7 4 3 8 9 10 
1 2 5 6 7 4 9 8 3 10

This looks pretty reasonable to me.
Any hints or suggestions?

Ciao!!!

Claudio

[CDiMa]

Here is my output for the sample input:

Code: Select all

Case 1:
1 4 3 2 5 6 
1 6 5 2 3 4 

Case 2:
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2 

It looks precisely like the sample output...

Here is the key, "looks"...
I put an extra space at the end of each line but blanks have the bad attitude of non being visible

Ciao!!!

Claudio

[technobug]

I just got it in .592.... i will run through my code today to improve it (c++ --> c with scanf/printf)

1. I did not generate the prime numbers during runtime but cached them.
2. Only do the recursive call when your number is prime
3. Avoid calls with too many parameters (does it really affect performance?)
4. Use a bool matrix to keep track of used numbers
5. Use a char matrix to keep track of the current circle (i believe this is the point on huge improvements)

Guilherme Silveira

[CDiMa]

I just got it in .592.... i will run through my code today to improve it (c++ --> c with scanf/printf)

1. I did not generate the prime numbers during runtime but cached them.

Basically this problem isn't about primality although it has to do with prime numbers.
The maximum prime number which comes into play is 31 so there's no big deal in generating prime numbers.

2. Only do the recursive call when your number is prime
3. Avoid calls with too many parameters (does it really affect performance?)

Avoid calls at all

4. Use a bool matrix to keep track of used numbers
5. Use a char matrix to keep track of the current circle (i believe this is the point on huge improvements)

6. Use an adiacency matrix to know which number you can put next... Try the numbers in lexicographic order and use backtracking.
7. Once the algorithm is fine tuned there's only one thing left to improve times...

Ciao!!!

Claudio

[Zyaad Jaunnoo]

One thing you can do is to calculate the primes and mark it as a boolean value (1 = true) if ever the comination of the two numbers results in a prime number. A sample is shown below.

1 2 3 4 5 ...
---------------
1 | 0 1 0 1 0
2 | 1 0 1 0 1
3 | 0 1 0 1 0
4 | 1 0 1 0 0
5 | 0 1 0 0 0
.
.
.

That will prevent you from calculating the sum of the numbers when your program runs and rather use the indexes to directly know whether the combination results in a prime number or not.

[IBelieve]

"Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. "

Can anybody explain what this means ?

[UFP2161]

Taking the example output for "6":

1 4 3 2 5 6
1 6 5 2 3 4

It just means that the first number must always be 1. The "anti-clockwise and clockwise" just means that 1+4 = 5 must be prime, and 1+6 = 7 must be prime (going the other way).

Basically, it's stating that the output is a description of a circular linked list, where each adjacent number sums to a prime.

[IBelieve]

...why does my program get WA?
[pascal]
program primering;
var x:array [1..1000] of integer;
n:integer;
visited:array [1..1000] of boolean;

function prim(x:integer):boolean;
var i:integer;
begin
prim:=true;
for i:=2 to x div 2 do
if x mod i =0 then begin prim:=false; break end;
end;

procedure writecircle;
var i:integer;
begin
for i:=1 to n do
write(x,' ');
writeln;
end;
procedure backtrack(i:integer);
var k:integer;
begin
if (I=N+1) then if (prim(X[n]+X[1])) then writecircle else begin end
else
for k:=1 to n do
begin
x:=k;
if not visited[k] then
begin
visited[k]:=true;
if prim(x+x[i-1]) then backtrack(i+1);
visited[k]:=false;
end;
end;
end;
procedure ReadNSolve;
var nr:integer;
begin
nr:=1;
readln(input,n);
while not eof(input) do
begin
writeln('Case ',nr,':');
x[1]:=1;
fillchar(visited,sizeof(visited),false);
visited[1]:=true;
backtrack(2);
readln(input,n);
nr:=nr+1;
end;
end;

begin
ReadNSolve;
end.
[/pascal]

[Eduard]

I write a backtrecking for this problem and it works fast for n<=15 and
round 15 seconds for test case n=16.
Can someone tell me how can i solve this problem faster.I thing i can't get Accepted for this problem by pascal.
And tell me please why some people are getting Accepted during 20 second.

[Eduard]

Finaly I got Accepted but after writing my program by C++.
The same program is getting Accepted by C++ during 1.4 second and
getting TLE by Pascal.
I really don't recomend someone to write solution of this problem by Pascal if he(she) is using backtracking. ':)'

[jagadish]

to Ibelieve:
no output for n=2 ..?

[Sanny]

For n = 2, output should be

Code: Select all

1 2

[Rajib]

Most people are masterfull in C/C++. Very few poeple use Pascel. It is better to discuss about your problem rather send the code .

By the way, this is a very simple back-track problem. You just check all the valid combinations and print them...

You should clear enough about the problem description too...

[Rajib]

Sorry about the riply. I am a new poster and do mistake to send my post to 'Believe'. The mistake is occured because of more then one page...