How to solve this problem? (-)

Re: How to solve this problem? (-)

Does binary search work?

Re: How to solve this problem? (-)

Yes, you can solve this problem using 2 binary searches.

Or, applying advanced geometry, this problem can be solved with 1 binary search...

Re: How to solve this problem? (-)

Posted by

KAV 24 Aug 2006 13:04

I tried to use 2 binary searches, but WA :(

Re: How to solve this problem?

to use binary search function must be monotonic. why will the function be monotonic ?

And what advanced :) geometry do u mean?

*Edited by author 24.08.2006 22:55*

Re: How to solve this problem?

to use binary search function must be monotonic. why will the function be monotonic ?

And what advanced :) geometry do u mean?

*Edited by author 24.08.2006 22:55*

To use binary search to find minimum/maximum function is not obliged to be monotonic. And it will not be monotonic, really.

Re: How to solve this problem?

Posted by

svr 30 Jun 2007 11:32

I got Ac very very easy without binary search.

I used sequentul optimization on rectangle [0,2*pi][0,2*pi]

by angle variables s,t . At beggining dt=pi -

size of window for search,s0=pi,t0=pi-it's centre.

Use N=100 steps by each variable.

Let sRec,tRec- point of Record on first step.

For next step we do: s0=sRec;t0=tRex,dt=dt/10- moving

and diminishing search-window.

And so on while dt>0.000001.

*Edited by author 30.06.2007 11:32*

Re: How to solve this problem?

Binary search is applicable only to monotonic functions and functions having one minimum. Otherwise you are not protected against falling into local minimum pit. Same stands for gradient slide. Yes, you can protected yourself with a lot of small ranges (up to TL), but that's a "lucky way".

Re: How to solve this problem? (-)

Comment from my source:

/*

* Using the law of cosines set to point O, A, B

* any valid coords on the plane. Build circle C1 around

* point A and C2 - around B. Consider all points from C1

* with a some small step. For each such point A' find

* corresponding point B' on C2 that minimize distance

* OA' + A'B' + B'O. For finding it we can also iterate

* all points from C2 with certain step and compute

* final distance for such pair (A', B'). But if we set

* enough precision (a very small step) to attain a correct

* answet - then obviously would earn "time limit".

* We can avoid it e.g. in next way:

* Instead of making only one pass with very small step

* throug both circles we can make several passes recursively -

* first will be over all points with big step, second - over

* some small range near the local minimum obtained on previous

* pass and so one...

*/

Maybe this will help to anyone...

P.S.: in test 7 OA = 0, in test 8 - OB = 0. Or vise versa. On test >= 10 problems with precision can appear everywhere :)

Re: How to solve this problem?

Thanks to svr very lot. AC!!!!

*Edited by author 31.03.2012 10:44*

*Edited by author 31.03.2012 10:44*