Обсуждение @ 1815. Ферма в Сан-Андреасе @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

How to make use of the FOCs for this problem? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 1 мар 2011 02:15

We can write some FOCs which describe optimal point. But how to find point which satisfies these FOCs?

Re: How to make use of the FOCs for this problem? bsu.mmf.team 2 мар 2011 01:13

I suspect it is not necessary to find this point, you can get correct answer without knowing exact location of it. I haven't solved this problem yet, so it is a hypotesis only...

Re: How to make use of the FOCs for this problem? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 2 мар 2011 21:37

Haven't ACed yet, but it seems I found the algo which uses 2 binary searches only.

Re: How to make use of the FOCs for this problem? bsu.mmf.team 2 мар 2011 23:45

If you want to use BS, you should have a sorted structure. What is it? Do you serach this point on some fixed line?

Re: How to make use of the FOCs for this problem? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 3 мар 2011 00:00

Of course, I convert initial problem to some other problem, and there it is ordered structures =)

Re: How to make use of the FOCs for this problem? svr 4 мар 2011 11:51

Convex structure also gives O(lg n).
For example golden proportion search om segment.

Обсуждение задачи 1815. Ферма в Сан-Андреасе