Задачки про деку и сферку

[sim0nsays]

Задачку про деку задал elephantum во времена, когда работал в Невале, кодал Героев5, вел перепалки за Петон и в общем и целом сколько-то относился к геймдев-тусовке (как это я забыл его зафрендить). Вот пусть расскажет о том, как ему тот геймдев и Невал видиццо столько времени опосля.
Задачка типа сложная и на просветление. Помнится, первый решил zemedelec минут

Comments

[captain_tylor]

Про деку - в общих чертах. Ну, можно, например, присобачить к одному концу (для определенности, голове) маркер из случайной последовательности нулей и единиц, прокрутить деку ( push_back(pop_front()) ), пока маркер не вылезет с головы, там его отрезать и прокрутить обратно. Если на хвосте не будет нашего маркера, то значит, что мы вырезали действительно его и длина известна. Если он остался как был, то это был не наш маркер, а другой такой же. Тогда возвращаем как было, и повторяем с другим маркером, например, подлиннее.

Насчет сферы - разве если перебрать всех пары, тройки и четверки точек, и построить по каждому набору сферу, то искомая не будет среди них? Если да, то не вижу перелома:)

[sim0nsays]

Первое решение близко к правильному, и наверное будет работать, но слижком уж утяжеленное. Сделай проще и поборись сложность?

Насчет сферы - йеп, это правильное решение. Расширение в том, что народ с опытом геометрических вычислений и вообще трехмерной геометрии очень тяжело соглашается на такой тупой перебор аж четвертой степени. Обе задачки - про то, чтобы заставить себя думать дальше, чем O(n).

[jakobz]

Странно что не соглашается на тупой перебор - известная же задача вроде.

[sim0nsays]

Ну, если ты эту задачу знал - то тебе нет смысла ее задавать. "Не соглашается" - имеется ввиду, что мозг не может смириться, что нет геометрического решения за O(N) или чуть больше. А его нет. Придется делать N^4.

[shader]

А когда вычислительная сложность для сферы стала N^4? Всё же хотим получить expected linear time, в трехмерном хотя бы случае.
Раз Welzl говорить нельзя, тогда:
http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf

Когда-то я мог наизусть рассказать, как это работает :) В принципе, если прочитать еще раз, снова смогу.

[sim0nsays]

Вот короче кто будет приводить таки линки - будет тоже объяснять как работает! ;)

[shader]

=)

[sim0nsays]

Я кстати только сейчас подумал, что это решение не с O(1) затратами памяти. Думаю вычоркивать :)

[captain_tylor]

Хм, действительно, О(ln N) получается :)