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
Location: Dhaka, Bangladesh
Contact:

524 - Prime Ring Problem

Post by Shahid » Fri Oct 04, 2002 6:30 am

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

Post by rury » Sun Oct 20, 2002 8:26 pm

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

Post by Robbie » Mon Oct 21, 2002 4:57 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Shahid » Mon Oct 21, 2002 9:35 pm

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

Post by rury » Tue Oct 22, 2002 3:21 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

Post by rury » Tue Oct 22, 2002 6:10 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:

Post by anupam » Tue Oct 22, 2002 6:12 pm

:oops: :oops: 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
-- :evil: :evil:
[/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

Post by Robbie » Tue Oct 22, 2002 7:09 pm

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 ! :roll:

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

Post by Shahid » Tue Oct 22, 2002 8:49 pm

did u think i post these messages without getting 524 accepted??? :roll:

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

Post by rury » Wed Oct 23, 2002 6:09 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

Post by jonas » Mon Nov 25, 2002 3:02 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 ! :roll:
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

Post by Robbie » Mon Nov 25, 2002 2:58 pm

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:

Post by pc5971 » Wed Dec 18, 2002 3:36 pm

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

Post by titid_gede » Fri Dec 20, 2002 6:52 pm

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.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Jan 27, 2003 12:36 pm

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

Post Reply

Return to “Volume 5 (500-599)”