Page 2 of 5
Posted: Mon Jan 27, 2003 1:18 pm
by 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..
524 Prime Ring Problem - Presentation Error
Posted: Fri Nov 07, 2003 12:55 pm
by 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
Re: 524 Prime Ring Problem - Presentation Error (solved)
Posted: Fri Nov 07, 2003 1:50 pm
by CDiMa
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
Posted: Thu Nov 27, 2003 1:10 pm
by 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
Posted: Thu Nov 27, 2003 2:59 pm
by CDiMa
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
Use a 2D array to mark for primes...
Posted: Thu Dec 18, 2003 7:42 am
by 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.
Posted: Mon Jan 26, 2004 8:41 pm
by 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 ?
Posted: Tue Jan 27, 2004 12:03 am
by 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.
Posted: Tue Jan 27, 2004 9:42 pm
by 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]
524
Posted: Fri Feb 13, 2004 4:02 pm
by 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.
Posted: Sun Feb 15, 2004 1:50 pm
by 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. ':)'
Posted: Thu Jun 17, 2004 8:26 pm
by jagadish
to Ibelieve:
no output for n=2 ..?
Posted: Sat Jun 19, 2004 12:22 pm
by Sanny
For n = 2, output should be
Posted: Mon Jun 21, 2004 9:24 am
by 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...
Posted: Mon Jun 21, 2004 9:26 am
by 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...