Версия для печати темы

Автор: L0st 16.4.2017, 23:14

Нашел эту задачку на одном из англоязычных каналов ютуба (пардон, если баян).
В общем, оккупанты опять издеваются над Мегамозгом. На этот раз его поставили на краю обрыва: два шага назад - он упадет, два шага вперед - будет съеден голодными туземцами. Оккупанты сохранят Мегамозгу жизнь, если он составит алгоритм из определенного количества команд вперед/назад, последовательно выполнив которые он бы не упал и не был съеден. К тому же, подлые оккупанты могут заставит выполнять команды не последовательно, а, к примеру, каждую 2ую, либо каждую 3ью, либо каждую 4ую и т.д. Каково максимальное количество команд в наборе, с помощью которого Мегамозгу гарантированно выживание?
ЗЫ Кажется, более логично спросить "каково минимальное количество команд, выполнение которого наверняка бы погубило Мегамозга?", но это противоречит духу сайта

Автор: Owen 19.4.2017, 14:41

Каждую 2ю, 3ю и т.д. - начиная с первой?
Т.е. возможны наборы команд "1, 2, 3, 4, ...", "1, 3, 5, ...", "1, 4, 7, ..."? Или как-то иначе?

Автор: L0st 21.4.2017, 6:30

1 2 3 4...
2 4 6 8...
3 6 9 12...
4 8 12 16...
и т.п.

Автор: fiviol 21.4.2017, 7:20

11 получается.

Автор: L0st 21.4.2017, 20:43

Верно. Для трех шагов вперед/назад предлагать не буду - не хочу грех на душу брать

Автор: fiviol 25.4.2017, 9:16

А ответ для трех шагов известен? Уже больше 120 команд проскочил, конца пока не видно.

Автор: L0st 25.4.2017, 10:19

Да, для трех известен. Скажу лишь, что для четырех он уже выше 13000.
Могу даже сказать наименование обобщенной задачи. К слову, решение для общего случая было доказано в 2015.

Автор: fiviol 25.4.2017, 14:41

Нет, случай 4 шагов и уж тем более обобщенная задача - это заведомо грех на душу по отношению к работе.

Для трех шагов уперся в 164 команды.

Автор: Nikita146 7.5.2017, 16:14

В общем виде это гипотеза Эрдёша о расходимости, и, согласно https://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/ (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности.

Автор: VitalyKolobkov 12.5.2017, 22:01

Драма "Erdős discrepancy problem".

На форуме.
L0st: Нашел эту задачку на одном из англоязычных...
Я: Хмм, интересно, надо попробовать решить.

Через неделю.
Я: Эх, что-то я забыл, там же какая-то вроде забавная задачка была. Что там еще раз?
Открывается форум.
fiviol: 11 получается.
L0st: Верно. Для трех шагов вперед/назад предлагать не буду - не хочу грех на душу брать
Я: Да, на самом деле, получается 11. Все довольно просто, дерево небольшое. Надо бы сделать для трех шагов.
Через 10 минут, исписав целую страницу.
Я: Не, на бумаге слишком долго получается. Проще запрогать. Что-то лень с++ проект создавать, сделаю ка я прямо на джава скрипте, в браузере запущу.
Внутренний голос (ВГ): Ой, неужели! Там же надо будет хитрую структуру в памяти строить, возможно оптимизировать придется. В плюсах ты через указатели все раскидаешь, если что, а в джава скрипте справишься?
Я: Да, это хороший аргумент, ладно, так и быть, создам проект в плюсах.

После нескольких часов кодинга и отладок всех мелочей.
Я: Ага, вроде все работает, на двух шагах 11 получается, на деструктор пока наплевать, там памяти кот наплакал, запускаем для трех шагов.
ВГ: Ну-ну
Я: Пошло дело! Пойду домой.

На следующий день.
Я: Что? Кончилась память? Никогда такой ошибки не видел. Что значит, кончилась память.
ВГ: Лол, лошара
Я: Подожди, эта штука реально съела 12 гигов оперативы что ли?!
ВГ: А ты перед тем, как запускать хоть прикинул, как эта штука растет, сколько памяти надо, сколько операций на каждый шаг потребуется?
Я: Ок, щас все будет.
Запускается код с ограничение по количеству шагов, строится зависимость количества элементов в дереве от глубины, фиттится с очень хорошей точностью на exp(0.5*n).
Я: Эмммм...
ВГ: Ну, что дальше?
Я: Нда, экспоненту так просто не победишь. Ладно, придется переписать половину кода и сделать дерево, которое само себя удаляет на ходу, но запоминает самую длинную ветку.
ВГ: Го фор ит!

После нескольких часов кодинга и отладок.
Я: Ок, вроде работает. Смотри в таск менеджере: память не растет.
ВГ: Молодец! Посиди минут 20, посмотри, как эта музыка работает.
Я: Ок.
ВГ: Ну чё?
Я: Что-то оно заглохло как-то подозрительно на длине 258 шагов.
ВГ: Подожди еще.
Я: О! Новая длина 269, уже 272.
ВГ: На ночь оставь, может досчитает.

На следующий день.
Я: А ну ка! Чта? Всего 318? Что за фигня? А комп точно ночью пахал, а не спал?
ВГ: А сколько операций на каждый шаг тратится?
Я: Порядка exp(0.5n)*n^2, там проверка лобовая, то есть n/3 сумм считается каждый раз.
ВГ: Может n^2 можно как-то улучшить?
Я: Я об этом еще в самом начале думал, но... сложная какая-то задача уже становится. Я ее третий раз переписываю.
ВГ: А кто-то на джава скрипте вообще хотел в браузере запускать...
Я: Заткнись!

Через несколько часов кодинга.
Я: Все, теперь это, грубо говоря, exp(0.5n)*log(n). Ну, от экспоненты я никак не уйду. Мне же придется пройтись по всем веткам дерева.
ВГ: Запускай на ночь.
Утром:
Комп: Привет, тут ночью питание отключали, добро пожаловать, введи логин, пароль, все дела
Я: #%$%@#$@#$^%&^*$@
ВГ: Лол, лошара Может быть надо в файл делать вывод, а?
Я: Ок...
ВГ: Еще кое-что: запусти стразу на два ядра, пусть одно с +1+1 начнет, а второе с +1-1.
Я: Это хорошая мысль. Запускаю.

Примерно через сутки.
Я: Посмотрим, что там. Вы серьезно? Глубина 389 при количестве элементов 2861030146 при заходе от +1+1 и глубина 379 при количестве элементов 1079400871 при заходе +1-1. Нда, такими темпами он будет еще долго считать. Если там искомая глубина 500, например, то я и за месяц до нее не доберусь. Тут придется на 1000 процессоров раскидывать. Ладно, проверим форум, может там кто-нибудь уже решил.
На форуме.
Nikita146: В общем виде это гипотеза Эрдёша о расходимости, и, согласно этой статье (третий абзац), для радиуса в 2 шага известен пример на 1124 команды, но неизвестно, есть ли более длинные такие последовательности.
Я: 1124! Ничесе! А что скажет Википедия? А она говорит, что длина 1161 (https://arxiv.org/pdf/1402.2184.pdf). 1161, Карл!
ВГ: Все, приплыли на барже...
Я: Обидно, да?
ВГ: Обидно. Иди лучше работой займись.
Я: И то верно. Ушел

--------------------------------------------------
Мораль: если что-то делаете, то делайте сразу хорошо и правильно, а не кое-как на коленке... или не делайте вообще.

Автор: Nikita146 13.5.2017, 0:49

Да уж, темп роста функции впечатляет