Page 1 of 1

11490 - Just Another Problem

Posted: Mon Sep 15, 2008 1:21 am
by Naani
My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.
TIA
Vinay Emani

Re: 11490 - Just Another Problem

Posted: Tue Sep 16, 2008 4:22 am
by baodog
Hi Robert,

How did you solve it in 10ms :-). Is it possible to construct the solutions
directly without searching? Thanks!

Re: 11490 - Just Another Problem

Posted: Tue Sep 16, 2008 2:56 pm
by bleedingeyes
can anyone give me some hint how to solve the problem quickly

Re: 11490 - Just Another Problem

Posted: Tue Sep 16, 2008 10:09 pm
by Robert Gerbicz
baodog wrote:Hi Robert,

How did you solve it in 10ms :-). Is it possible to construct the solutions
directly without searching? Thanks!
The problem is equivalent to factorize n (it is a little algebra to figure out the factors) for this I've used Pollard rho method (by Brent's modification).

Re: 11490 - Just Another Problem

Posted: Thu Jul 02, 2009 4:56 pm
by Khongor_SMCS
Naani wrote:My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.
TIA
Vinay Emani
My O(sqrt(S)) algorithm got AC in 1.3s :D