524 - Prime Ring Problem

[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?

[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]

[Robbie]

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]

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]

My program gives 81024 lines in number 16, too.
But.. I got reply - "output limit exceeded".
Why?

[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~

[anupam]

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]

[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 !

[Shahid]

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

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

[jonas]

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]

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.

[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?!?

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

[hank]

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.