Боря программирует

Lambdaman. Решение.

Как многие предложили в комментариях, можно попробовать сгенерировать псевдослучайную строку длины миллион, а потом подбирать seed в надежде, что все клетки будут посещены.

Как сгенерировать случайную строку? Можно использовать линейный конгруэнтный генератор. Звучит страшно, но по сути мы просто фиксируем две константы (например, mult=16807, mod=2147483647) и какой-то изначальный seed. Каждый раз, когда нужно сгенерировать случайное число от 0 до N, делаем seed = (seed * mul) % mod, а потом возвращаем seed % N.

Дальше мы можем пытаться подобрать изначальный seed такой, который посетит все клетки. Как оценить вероятность того, что мы сможем подобрать такой сид? Математику я знаю плохо, но зато могу написать код и проверить :) Я перебрал миллион различных сидов, и самый лучший посетил 4694 из 4999 клеток лабиринта.

С одной стороны это говорит о том, что метод достаточно интересный. А с другой о том, что подобрать сид, который посетит совсем все, скорее всего будет сложно.

Посмотрим на то, как именно устроен конкретный тест. Можно заметить, что все клетки, которые имеют такую же четность как и стартовая клетка, проходимые. Поэтому давайте генерировать строку, где каждая буква на четной позиции просто повторяет предыдущее действие, а буквы на нечетных позициях все еще случайные. Заметим, что если этот алгоритм обойдет все клетки той же четности, что и старт, то и все "промежуточные" клетки он тоже обойдет. Поэтому мы свели задачу к тому, чтобы за 500_000 действий обойти лабиринт в два раза меньшего размера (а это проще).

Я нашел решение в таком формате где-то за 10 минут. Важно было перебирать не только разные стартовые seed, но и пробовать различные mult. В лучшем решении на контесте участники пошли еще дальше и вместо подcтрок "LL", "RR", "UU", "DD", нашли решение в виде конкатенации строк "LLUU", "LLDD", "RRUU", "RRDD", "UULL", "UURR", "DDLL", "DDRR" в случайном порядке. На практике такое решение можно найти быстрее чем за минуту. Видимо, идея в том, чтобы реже возвращаться обратно.

www.tgoop.com/bminaiev_blog/74

5.6K viewsJul 3 at 16:38

Lambdaman. Решение.

Как многие предложили в комментариях, можно попробовать сгенерировать псевдослучайную строку длины миллион, а потом подбирать seed в надежде, что все клетки будут посещены.

Как сгенерировать случайную строку? Можно использовать линейный конгруэнтный генератор. Звучит страшно, но по сути мы просто фиксируем две константы (например, mult=16807, mod=2147483647) и какой-то изначальный seed. Каждый раз, когда нужно сгенерировать случайное число от 0 до N, делаем seed = (seed * mul) % mod, а потом возвращаем seed % N.

Дальше мы можем пытаться подобрать изначальный seed такой, который посетит все клетки. Как оценить вероятность того, что мы сможем подобрать такой сид? Математику я знаю плохо, но зато могу написать код и проверить :) Я перебрал миллион различных сидов, и самый лучший посетил 4694 из 4999 клеток лабиринта.

С одной стороны это говорит о том, что метод достаточно интересный. А с другой о том, что подобрать сид, который посетит совсем все, скорее всего будет сложно.

Посмотрим на то, как именно устроен конкретный тест. Можно заметить, что все клетки, которые имеют такую же четность как и стартовая клетка, проходимые. Поэтому давайте генерировать строку, где каждая буква на четной позиции просто повторяет предыдущее действие, а буквы на нечетных позициях все еще случайные. Заметим, что если этот алгоритм обойдет все клетки той же четности, что и старт, то и все "промежуточные" клетки он тоже обойдет. Поэтому мы свели задачу к тому, чтобы за 500_000 действий обойти лабиринт в два раза меньшего размера (а это проще).

Я нашел решение в таком формате где-то за 10 минут. Важно было перебирать не только разные стартовые seed, но и пробовать различные mult. В лучшем решении на контесте участники пошли еще дальше и вместо подcтрок "LL", "RR", "UU", "DD", нашли решение в виде конкатенации строк "LLUU", "LLDD", "RRUU", "RRDD", "UULL", "UURR", "DDLL", "DDRR" в случайном порядке. На практике такое решение можно найти быстрее чем за минуту. Видимо, идея в том, чтобы реже возвращаться обратно.

BY Боря программирует