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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Jan 27, 2003 1:18 pm

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

Post by CDiMa » Fri Nov 07, 2003 12:55 pm

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 :o :
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? :roll:

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)

Post by CDiMa » Fri Nov 07, 2003 1:50 pm

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:

Post by technobug » Thu Nov 27, 2003 1:10 pm

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

Post by CDiMa » Thu Nov 27, 2003 2:59 pm

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

Ciao!!!

Claudio

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

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

Post by Zyaad Jaunnoo » Thu Dec 18, 2003 7:42 am

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

Post by IBelieve » Mon Jan 26, 2004 8:41 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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Jan 27, 2004 12:03 am

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

Post by IBelieve » Tue Jan 27, 2004 9:42 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;
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.

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

524

Post by Eduard » Fri Feb 13, 2004 4:02 pm

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

Post by Eduard » Sun Feb 15, 2004 1:50 pm

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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Thu Jun 17, 2004 8:26 pm

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:

Post by Sanny » Sat Jun 19, 2004 12:22 pm

For n = 2, output should be

Code: Select all

1 2

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

Post by Rajib » Mon Jun 21, 2004 9:24 am

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

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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Post by Rajib » Mon Jun 21, 2004 9:26 am

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

Post Reply

Return to “Volume 5 (500-599)”