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

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### 524 - Prime Ring Problem

hi,
i recently solved problem 524, actually i am not satisfied with my timing at all. my first timing was 3.160...not it downs to 1.360....but the still its over 1.000....so give me some suggestion..

at first i used the brute force method of finding out primes(that is diving continously till square root of the number)..and got 3.160

then i decided to generate a list of primes at the begining of the program....in generating the list at first i used sieve of iratosthinis method...and got 1.400 timing
then i used the general mehod of prime fining, the difference is i only divide the number with the primes till that number's square root
and then i got 1:360

how can i do much better?

rury
New poster
Posts: 4
Joined: Sun Oct 20, 2002 8:19 pm

### 524 Prime Ring Problem

In my program..
when a input number is 16, long output lines are printed.
But.. I think it is correct.
Is there any body solved this problem?
How many output lines in 16 number?
[/b][/i]

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

### Re: 524 Prime Ring Problem

rury wrote:In my program..
when a input number is 16, long output lines are printed.
But.. I think it is correct.
Is there any body solved this problem?
How many output lines in 16 number?
[/b][/i]

My program gave 81024 lines.

GGG

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
i improve my code a bit and now the time is 1.190 sec....
i improved the code of prime generation and aslo improve time by cutting down some unnecessary recursive calls.......but still weird how people solved this problem in 0.210 sec!!!!!!!!

rury
New poster
Posts: 4
Joined: Sun Oct 20, 2002 8:19 pm
My program gives 81024 lines in number 16, too.
But.. I got reply - "output limit exceeded".
Why?

rury
New poster
Posts: 4
Joined: Sun Oct 20, 2002 8:19 pm
Did you accept 524 problem?
I got a reply - output limit exceeded..
I don't know why I got it.

I'm very curious to know answer..
Help~

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i have also got out. lim. ex..
but i am sure i controlled my counter and i have got right ans. for the highest input.
but sev times i have got the message.
please give some trics.
--thanks
--
[/img]
"Everything should be made simple, but not always simpler"

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam
What about other inputs ?
Here is outputs from my AC program :

Code: Select all

``````2   : 1
4   : 2
6   : 2
8   : 4
10  : 96
12  : 1024
14  : 2880
16  : 81024``````
May be this will help !

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
did u think i post these messages without getting 524 accepted???

rury
New poster
Posts: 4
Joined: Sun Oct 20, 2002 8:19 pm
Thanks..
I got same answer for you.
I'm not wrong answer reply but.. I got output limiit exceeded.

I send you my source.
Please tell me why did I get wrong reply..

jonas
New poster
Posts: 4
Joined: Mon Nov 25, 2002 2:59 am
Robbie wrote:What about other inputs ?
Here is outputs from my AC program :

Code: Select all

``````2   : 1
4   : 2
6   : 2
8   : 4
10  : 96
12  : 1024
14  : 2880
16  : 81024``````
May be this will help !
I have exactly this amount of output, but I get "Wrong answer" anyway. I don't understand what's wrong.

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam
May be some problems occur when you write your outputs. Please check it carefully again ....
If there exist problems, I think you should post your code here so that someone can find out your mistakes.
GGG

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
How did you solved this problem??? Did you use backtracking method? I think this method is too slow? I thought to generate the permutations of (1,2,...,n) using lexicografical order, and chek the conditions . . .

Can you give me some advice?!?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i use backtracking and got AC (P.E) in 1.701 second. it'q quite fast for this case, and also by using backtracking, they automatically generate result in lexicography order.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
rury wrote:My program gives 81024 lines in number 16, too.
But.. I got reply - "output limit exceeded".
Why?
I don't think there is the number "16" in the judge's test data.