Кольцевой поезд - найти число вагонов.

[Legioner93]

Вы находитесь в поезде, вагоны которого закольцованы: последний вагон прицеплен к первому (кабина машиниста отсутствует). Все вагоны идентичны. Каждый вагон может быть либо освещен, либо не освещен.
Изначально свет в вагонах горит случайным образом. Вы можете свободно перемещаться между вагонами и включать-выключать свет в вагоне, в котором находитесь.
Вопросы:
1) Придумать алгоритм, который позволит определить количество вагонов в поезде.
2) Существует ли алгоритм со сложностью $O(N)$, где $N$ - число вагонов? Сложность алгоритма - это общее количество перемещений между вагонами.
3) Предлагаю побороться также за константу в $O(f(N))$, т.е. получить самое быстрое время не в виде $O(f(N))$, а в виде $f(N)+o(f(N))$, что куда сложнее.

Первые два вопроса авторские (их я решил), последний вопрос добавил лично я (пока открыт).
Задача взята с конкурса, который проводил один из российских банков.

[_Ivana]

Вперед на 1 включаем, назад на 1 гасим, вперед на 2 включаем, назад на 2 гасим и т.п. пока не встретим вдруг расхождение с тем, что мы уже включили/погасили по нашим данным.

[_Ivana]

В принципе, необязательно, чтобы приращения вперед-назад были равны единице, они даже не обязаны быть равны и постоянны - главное, чтобы мы знали закон их изменения, и чтобы на каждом шаге они были не больше реального количества вагонов (скорее всего, надо продумать этот момент поточнее, а может и половины вагонов...). Но т.к. количество вагонов нам заранее неизвестно, то начать лучше с единицы, а потом... надо подумать, или геометрическая прогрессия с коэффициентом 2 (и может минус 1), или какие-нибудь другие Фибоначчи

ЗЫ и, в частном случае, если не ошибаюсь, один длинный закольцованный в себя вагон определить нельзя

-- 05.05.2013, 02:53 --

Жаль спать хочется (4 часа ночи), очень хочу сам дорешать, но чувствую, до конца сейчас не добью, а завтра наверняка уже кто-нибудь другой умнее все доведет до конца и мне ничего не останется... А я пока баранов вагоны считать пойду...

[g______d]

Специально для _Ivana помещу в спойлер :)

Собственно, я так понял, что это примерно то же самое.

(Оффтоп)

2) Гасим первые 2 вагона. Потом возвращаемся назад и на обратном пути включаем. Если попался уже включенный, то мы нашли цикл. Потом повторяем то же со 4 вагонами, потом с 8 и т. д.

Количество операций будет не больше $2\cdot \sum\limits_{2^{k-1}\le n} \le 4n.$

[vorvalm]

Предлагаю сначала последовательно включить свет во всех вагонах, а затем
последовательно выключать.

[Shadow]

vorvalm в сообщении #719806 писал(а):

Предлагаю сначала последовательно включить свет во всех вагонах, а затем
последовательно выключать.

Во всех это во сколько?

[vorvalm]

Их же не бесконечно.

[Legioner93]

_Ivana в сообщении #719720 писал(а):

Но т.к. количество вагонов нам заранее неизвестно, то начать лучше с единицы, а потом... надо подумать, или геометрическая прогрессия с коэффициентом 2 (и может минус 1), или какие-нибудь другие Фибоначчи

Я тоже к этому пришёл. И далеко не факт, что геометрическая прогрессия $2^k$, до которой легко догадаться - самая "быстрая" из всех последовательностей вообще. С ней у меня получилось $\sim 7N$.

_Ivana в сообщении #719720 писал(а):

ЗЫ и, в частном случае, если не ошибаюсь, один длинный закольцованный в себя вагон определить нельзя

Конечно можно. Запоминаем свет в первом вагоне, идём во второй, там меняем, возвращаемся в первый. Если в первом тоже изменилось, то первый вагон=второй вагон.

g______d в сообщении #719727 писал(а):

Гасим первые 2 вагона. Потом возвращаемся назад и на обратном пути включаем. Если попался уже включенный, то мы нашли цикл. Потом повторяем то же со 4 вагонами, потом с 8 и т. д.

Количество операций будет не больше $2\cdot \sum\limits_{2^{k-1}\le n} \le 4n.$

Да, алгоритм верный. У меня примерно такой же алгоритм, только я шёл в $2^k$-ый вагон, менял там свет, возвращался в начальный и смотрел, поменялся ли где-нибудь ещё. Если поменялся, значит мы прошли поезд по кругу. Время получается $ \sim 8N$, если всегда возвращаться в первый и $\sim 7N$, если в последней итерации уже не возвращаться в первый.

А вот с количеством операций $4n$ вы ошиблись. В наихудшем случае $n=2^{k-1}+1$ получается как раз $7n$, как и у меня, посмотрите.

Итак, остаётся открытым третий вопрос: можно ли сделать быстрее, чем за $7N$ (или за $4N$, если я не прав и оценка g______d всё-таки верная).

Если шагаем по геометрической прогрессии со знаменателем $a$, то $T \sim N (2a+1+\frac{2}{a-1})$, минимум этой функции достигается как раз в точке $a=2$ (что довольно любопытно).

[g______d]

Да, про $8N$ Вы правы.

По-моему, можно сократить до $6N$. А именно, после $k$-го шага у нас есть $2^k$ вагонов, про которые мы точно знаем. Почему бы на следующем шаге это не использовать? Т. е. пойти в другую сторону и делать такие же вагоны, а потом пойти обратно и делать противоположные. Таким образом, на каждой итерации вместо $2\cdot 2^k$ будет $2^k+2^{k-1}$, т. е. мы сокращаем общее время на четверть.

[_Ivana]

Да, найденные варианты асимптотически гораздо суровее, чем придуманный мной алгоритм - ходить вперед/назад, вперед все включать, назад все выключать, до первого расхождения с нашими представлениями о том, что мы уже включили/выключили, от выбранного раздела вагонов на величины из последовательности $1, 1, 2, 3, 5, 8, 13, ...$, где каждое следующее значение является суммой двух предыдущих.

UPD а может и не гораздо, надо будет посчитать и сравнить длины пробега...

[TOTAL]

$2^0$ по, $2^1$ против, $2^2$ по, $2^3$ против. Найдем за $5N$

[_Ivana]

Построил по своему алгоритму график нормированного к числу вагонов числа шагов алгоритма - получилось не так плохо (если я не ошибся при расчетах)

[_Ivana]

Сравнил с количеством шагов по первому методу g______d (в одну сторону) - там получается диапазон от $4N$ до $7N$, максимумы и минимумы конечно в других точках, чем в моем алгоритме. Подтвердите уже или опровергните мои расчеты, кому интересна тема Могу дать количество шагов для любых (компьютерно рассчитываемых) значений $N$.

[g______d]

_Ivana в сообщении #720139 писал(а):

Построил по своему алгоритму график нормированного к числу вагонов числа шагов алгоритма - получилось не так плохо (если я не ошибся при расчетах)

А максимум -- это $3+\sqrt{5}$?

[_Ivana]

Не могу сказать, я моделировал на компьютере численно, в радикалах в общем виде сумму ряда не вычислял. Хотя наверное можно записать ряд в аналитическом виде и посчитать.
Кстати, в первых постах я и имел в виду этот мой алгоритм, но написал его непонятно, что он вполне оказался похож и на ваш, и на ТС