524  Prime Ring Problem
Moderator: Board moderators
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 :
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
This looks pretty reasonable to me.
Any hints or suggestions?
Ciao!!!
Claudio
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 :
Here is my output for the sample input:The output format is shown as sample below.
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
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
Any hints or suggestions?
Ciao!!!
Claudio
Re: 524 Prime Ring Problem  Presentation Error (solved)
Here is the key, "looks"...CDiMa wrote: Here is my output for the sample input:It looks precisely like the sample output...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
I put an extra space at the end of each line but blanks have the bad attitude of non being visible
Ciao!!!
Claudio
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
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
Basically this problem isn't about primality although it has to do with prime numbers.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.
The maximum prime number which comes into play is 31 so there's no big deal in generating prime numbers.
Avoid calls at alltechnobug wrote:2. Only do the recursive call when your number is prime
3. Avoid calls with too many parameters (does it really affect performance?)
6. Use an adiacency matrix to know which number you can put next... Try the numbers in lexicographic order and use backtracking.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)
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.
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.
Taking the example output for "6":
Basically, it's stating that the output is a description of a circular linked list, where each adjacent number sums to a prime.
It just means that the first number must always be 1. The "anticlockwise and clockwise" just means that 1+4 = 5 must be prime, and 1+6 = 7 must be prime (going the other way).1 4 3 2 5 6
1 6 5 2 3 4
Basically, it's stating that the output is a description of a circular linked list, where each adjacent number sums to a prime.
...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[i1]) 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]
[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[i1]) 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]
When people agree with me I always feel that I must be wrong.
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.
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
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. ':)'
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
For n = 2, output should be
Code: Select all
1 2
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 backtrack problem. You just check all the valid combinations and print them...
You should clear enough about the problem description too...
By the way, this is a very simple backtrack problem. You just check all the valid combinations and print them...
You should clear enough about the problem description too...