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:
Contact Naani

11490 - Just Another Problem

Post by Naani »

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!
Top
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11490 - Just Another Problem

Post by baodog »

Hi Robert,

How did you solve it in 10ms :-). Is it possible to construct the solutions
directly without searching? Thanks!
Top
bleedingeyes
New poster
Posts: 9
Joined: Thu Aug 21, 2008 3:08 am
Location: IUT

Re: 11490 - Just Another Problem

Post by bleedingeyes »

can anyone give me some hint how to solve the problem quickly
Top
Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
Contact Robert Gerbicz

Re: 11490 - Just Another Problem

Post 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).
Top
Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:
Contact Khongor_SMCS

Re: 11490 - Just Another Problem

Post 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
Top
Post Reply

Return to “Volume 114 (11400-11499)”