Page 1 of 5

524 - Prime Ring Problem

Posted: Fri Oct 04, 2002 6:30 am
by Shahid
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?

524 Prime Ring Problem

Posted: Sun Oct 20, 2002 8:26 pm
by rury
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]

Re: 524 Prime Ring Problem

Posted: Mon Oct 21, 2002 4:57 pm
by Robbie
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

Posted: Mon Oct 21, 2002 9:35 pm
by Shahid
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!!!!!!!!

Posted: Tue Oct 22, 2002 3:21 pm
by rury
My program gives 81024 lines in number 16, too.
But.. I got reply - "output limit exceeded".
Why?

Posted: Tue Oct 22, 2002 6:10 pm
by rury
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~

Posted: Tue Oct 22, 2002 6:12 pm
by anupam
: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]

Posted: Tue Oct 22, 2002 7:09 pm
by Robbie
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:

Posted: Tue Oct 22, 2002 8:49 pm
by Shahid
did u think i post these messages without getting 524 accepted??? :roll:

Posted: Wed Oct 23, 2002 6:09 pm
by rury
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..

Posted: Mon Nov 25, 2002 3:02 am
by jonas
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.

Posted: Mon Nov 25, 2002 2:58 pm
by Robbie
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.

Posted: Wed Dec 18, 2002 3:36 pm
by pc5971
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?!?

Posted: Fri Dec 20, 2002 6:52 pm
by titid_gede
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.

Posted: Mon Jan 27, 2003 12:36 pm
by hank
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