Colin and Ryan

Let's talk about algorithms!

Moderator: Board moderators

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

Colin and Ryan

Post by temper_3243 »

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.

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

Post by Cho »

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.

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

Post by sharpobject »

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

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

Post by abishek »

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”