Ниже приведены комментарии к решению задачи, некоторых участников соревнования.
Stanislav Markevich: В итоге решил так. Нашел цепь длинною 1056 и 6 элементов вставил руками. Цепь из 1056 нашел поиском в глубину. В качестве первого элемента брал все числа, а следующим в цепи выбирал то число, которое дает меньше вариантов перебора. Поиск обрывал после определенного числа найденных цепей. Такое решение заняло около часа.
Sergey Kreys: Находим перебором гамильтонов путь в заданном графе, и выводим его. Стартовую вершину мы знаем - у нее степень равна 1. При ~хорошей реализации все находится примерно за 5 минут. Вручную можно было ничего не делать. Под "хорошей" реализацией понимается реализация перебора, построенная на основе хорошо известных предположений о порядке просмотра смежных с данной вершин на очередной итерации. К примеру, на очередном шаге "выгоднее" пытаться сначала пойти в вершину с наименьшей степенью; пройдя ребро, "удаляем" его из графа. При равенстве степеней выбирается вершина, исходя из каких-нибудь других соображений (здесь, как выяснилось, большой простор для творческих идей).
DAle: Сначала проанализировал степени вершин, нашлась одна вершина со степенью 1. С нее начинал поиск. Далее, на каждом шаге выбирал из соседних вершин вершины с минимальной степенью, делал их случайную перестановку и по очереди просматривал, пересчитывая степени при этом. В общем-то, пришлось не сильно долго подбирать seed для генератора случайных чисел, чтобы нашелся ответ. Хотя идей еще была масса. На все ушло часа полтора.
astapoff: Для каждого числа я находил количество других чисел, в которые может быть преобразовано это число. вот. оказалось, что есть одно число, которое может быть преобразовано только в два других числа. вот с этого числа и начинал строить последовательность. после каждого нового добавления, я для всех чисел пересчитывал вот это количество чисел, в которые могут они быть преобразованы... ведь я же добавил число в последовательность, значит некоторые числа, которые раньше могли в него преобразоваться, уже не смогут этого сделать... так я нашел 1055 чисел... оставшиеся числа тоже составили из себя цепь, но эту цепь нужно было впихнуть в середину готовой цепи из 1055 чисел...
|
