## 524 - Prime Ring Problem

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### 524 Prime Ring Problem - Presentation Error

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 524 Prime Ring Problem - Presentation Error (solved)

CDiMa wrote: 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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
technobug wrote: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.
technobug wrote: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
technobug wrote: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

Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

### Use a 2D array to mark for primes...

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.
Last edited by Zyaad Jaunnoo on Thu Aug 14, 2014 5:28 pm, edited 1 time in total.

IBelieve
New poster
Posts: 14
Joined: Sun Nov 16, 2003 7:40 pm
"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 ?
When people agree with me I always feel that I must be wrong.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
New poster
Posts: 14
Joined: Sun Nov 16, 2003 7:40 pm
...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;
var nr:integer;
begin
nr:=1;
while not eof(input) do
begin
writeln('Case ',nr,':');
x[1]:=1;
fillchar(visited,sizeof(visited),false);
visited[1]:=true;
backtrack(2);
nr:=nr+1;
end;
end;

begin
end.
[/pascal]
When people agree with me I always feel that I must be wrong.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 524

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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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. ':)'
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
to Ibelieve:
no output for n=2 ..?
Last edited by jagadish on Sat Jun 19, 2004 7:34 pm, edited 2 times in total.
if u can think of it .. u can do it in software.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
For n = 2, output should be

Code: Select all

``````1 2
``````

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am