11490 - Just Another Problem

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

11490 - Just Another Problem

Post by Naani » Mon Sep 15, 2008 1:21 am

My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.
TIA
Vinay Emani
I am signing an important document!

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11490 - Just Another Problem

Post by baodog » Tue Sep 16, 2008 4:22 am

Hi Robert,

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

bleedingeyes
New poster
Posts: 9
Joined: Thu Aug 21, 2008 3:08 am
Location: IUT

Re: 11490 - Just Another Problem

Post by bleedingeyes » Tue Sep 16, 2008 2:56 pm

can anyone give me some hint how to solve the problem quickly

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11490 - Just Another Problem

Post by Robert Gerbicz » Tue Sep 16, 2008 10:09 pm

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

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11490 - Just Another Problem

Post by Khongor_SMCS » Thu Jul 02, 2009 4:56 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”