Задачка.

[thesz]

Сегодня к нам на собеседование привели паренька. Мы побеседовали и в процессе он задал нам задачку: ножество (от одной и больше) одинаковых комнат соединены в кольцо одинаковыми коридорами. В самом начале в комнатах свет или зажжён или потушен, это единственное их отличие. Свет можно гасить и включать по желанию. Как определить количество комнат

Comments

Ня.

[_winnie]

1) отходит вправо(условное название направления) на Ni, запоминая состояние всех комнат.

2) возвращается налево обратно в ту же комнату на Ni команта, меняет в ней состояние света на противоположное.

3) отходит вправо(условное название направления) на 2*Ni, отмечая не изменился ли в какой-то комнате свет, через который отошёл на шаге. Этот шаг одновременно является шагом 1) с N(i+1) == 2*Ni.

Re: Ня.

[thesz]

Да, похоже, работает и логарифмический по времени.

У меня был тупее и квадратичный по времени, но всего с одним битом памяти комнат. ;)

Re: Ня.

[_winnie]

Ага. Не совсем логарифмический. LogN мотаний туда-сюда, линейное время (N + N/2 + N/4 + ...)

Re: Ня.

[_winnie]

>но всего с одним битом памяти
С учетом того, что на хранение числа N надо log N битов? ^_^

[dizzy57]

Можно за 4*(N*(N+1)/2) переходов между комнатами. Гася и зажигая свет в начальной, проверять, изменилось ли освещение в комнате, которая через i++ шагов по кольцу.
Стандартный алгоритм вычисления числа элементов дека, пользуясь только push_(front|back) и pop_(front|back).

[thesz]

Угум. Это как раз предложенный мной вариант. ;)

[zhurs]

в первой комнате включить свет.
Пройти во 2-ю, выключить, вернуться в первую и проверить, изменилась ли там ситуация.
Пройти в 4-ю выключая по пути свет и запоминая номер последней комнаты, где свет горел. Вернуться в первую - если там свет погас - запомненный номер и есть число комнат, если нет - идти до 8-й комнаты.

по памяти константа, по времени n

а логарифмический алгоритм принципиально не возможен

[thesz]

Там да, NlogN. Как и у тебя.

Свет может гореть в любой комнате, поэтому явно не константа по памяти.

[zhurs]

всего получается переходов :
4n, если сильно не повезёт - дойти до последней комнаты и обратно
2n - предыдущая итерация
n - перед этим
n/2 - ещё раньше
...

количество итераций - логарифм, а суммарная сложность 8n

а по памяти - нужно помнить на сколько комнат вперёд мы прошли, и номер *последней* освещённой комнати.
Если точно считать, то действительно не константа, а 2*log(2n) бит

[pinkbagheera]

Вы явно были не квестеры. Надо было оставить в первой комнате шляпу и идти их считать по кругу :)))

[thesz]

Ну, из квестов - только Space Quest N (N<=5) и Leisure Suit Larry, тоже не очень великие.

А! Ещё Full Throttle.

В общем, да, не квестовик. Но про шляпу в задании не было. Но идея хорошая. ;)

[mjr_blayne]

Можно глаз оставить. Если глаза нет, то задачу всё равно не решить.

[thesz]

А как тогда комнаты считать?

[black_wolf_ltd]

> Сегодня к нам на собеседование привели паренька. Мы побеседовали и в процессе он задал нам > задачку

Кто к кому ходил на собеседование ? =))))

Кстати, а вы это кто =) ? (контора т.е., конечно)

[thesz]

http://www.ipmce.ru/research/hpc/

Мы обменивались вопросами. Мы ему про программирование задавали, а он (сперва с нашей подачи) про общее положение дел, а затем в конце задал вот про эту задачку. ;)