Colin and Ryan

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Colin and Ryan

Post by temper_3243 » Sun Jul 31, 2005 7:01 am

My idea is for input n,k is

factorize n-k and output all factors of n-k > k.

Btw how do you guys generate primes until 45000. Sieve or you put it in an array.

If any elegant methods please do post.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Jul 31, 2005 7:33 am

Oops... I've posted with the same topic in Volume108. And my solution is every bit the same as yours. WAs.
You got WA? or AC but looking or alternative solution?
Last edited by Cho on Sun Jul 31, 2005 7:34 am, edited 1 time in total.

sharpobject
New poster
Posts: 4
Joined: Sun Jul 31, 2005 6:37 am
Contact:

Post by sharpobject » Sun Jul 31, 2005 7:33 am

well one could just use a program to write a text array literal containing all primes up to 44711 (<5000 of them, so it's not rediculous) then copy the array literal into your program for submission. Alternately, my team ran a brute force with all numbers (not primes, just numbers) up to sqrt(n-k). For each one that was a factor, we added i and (n-k)/i and to a set, then output all members of the set >(n-k).

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Sun Jul 31, 2005 7:11 pm

amazing that worked, although even my overall complexity is O(sqrt(n-k)) (because the first step to generate prime numbers), your algorithm essentially does the same step thru every iteration and for every test case. you could have done the part of enumerating all the primes using a naive primality test by using all numbers till approximately 45000. and then could have used these primes to find all the divisors.
if the number of cases had been large, I guess the two methods would have made a difference between a TLE and an AC.

Post Reply

Return to “Algorithms”