Почему-то никто опять не пишет отчётов, а ведь это тоже интересно. В таких случаях принято начинать с себя, поэтому начну.
Собственно, задача решалась мной самым тупым образом - перебором, а оптимизации делались только для того, чтобы поднять скорость перебора. Ни одной умной идеи не удалось довести до ума, поэтому можно считать мой результат - верхом того, чего можно было достичь тупым ремесленным подходом.
А достичь удалось 15-го места, и первого из тех, у кого в графе страна стояло "Россия". Это самое высокое место, которое мне удавалось взять в конкурсах Al Zimmerman's. Поэтому, с одной стороны я рад, с другой - огорчён отсутствием плодотворных идей в моей голове. Хотя Herbert в июне уже разжевал для таких как я интересные подходы, я их не стал использовать, отчасти из-за нехватки времени, отчасти из-за того что не увидел насколько это сузит перебор.
До начала конкурса я немного подготовился.
Во-первых, попытался написать среду для запуска потоков с расчётной задачей. Но потом понял что это неправильный подход. Нужна простая база данных с заданиями, пусть даже в виде текстового файла, и независимые программные модули, которые не завершают работу сами, а берут и берут задания из базы. Нет заданий - выбирают его случайно. Таким способом можно избежать длительного простоя, который может составлять до 30% времени.
Во-вторых, я купил процессор Ryzen 5 2600, который при цене в 6300 руб. на момент покупки, прекрасно держит многопоточную нагрузку в 12 потоков.
Начало конкурса удачно выпало на время, когда у меня было по 4-5 часов, которые я мог посвящать задаче.
Первая моя версия программы на Java с использованием библиотеки java.math.BigInteger для работы с большими числами. Как выяснилось, она потребляла массу памяти и работала крайне медленно. Стало понятно что проблем две: 1 - при работе с BigInteger Java постоянно создаёт новые объекты, а неиспользуемые копятся в памяти; 2 - неоптимальные функции работы с большими числами очень тормозят программу.
Ассемблерный код основных функций я написал за минут 20, но последующие 2 дня попыток вставить ассемблерный блок в современные студии для программ на C/C++ не увенчались успехом.
Пришлось согласиться на компромиссный вариант, программу на C#, в которой числа хранились в двух 64-разрядных полях, а вычисления делались с помощью 64-разрядной арифметики C#.
Это сразу решило проблему memory leak и подняло быстродействие примерно до 50% от оптимизированного по скорости ASM/C++ аналога.
Сам алгоритм перебора был довольно простым, я бы сказал интуитивным. Вычислялось N^K, а затем, начиная с N-1 проверялось, если остаток больше I^K, то отнимаем от остатка I^K. Затем идём обратно и, если элемент J при исключении из решения оставляет остаток меньше чем сумма всех чисел от 1 до J-1 в степени K, то считаем это новым базовым решением, и запускаем алгоритм снова "вниз". И так пока не дойдём до N.
Естественно, сразу использовались оптимизации в виде массивов частичных сумм.
Большие степени я не просчитывал, так как это было практически бессмысленно, а вот со степенями 16..21 я поработал.
Через некоторое время стало понятно что если все суммы записать в память в отсортированном виде, то решение можно найти за очень маленькое время. Проблема была только в том, что столько памяти нет ни у одного суперкомпьютера. Тогда решено было использовать разбиение на блоки по 22..25 числа, чьи суммы в порядке возрастания вполне умещались в ОЗУ. Поиск по такому упорядоченному массиву занимал на первое число чуть больше времени чем просто перебор, но поиск последующих чисел становился не нужным - достаточно было брать числа из блока по возрастанию индекса. Таким способом быстродействие удалось поднять ещё в несколько раз.
Легко заметить, что самые маленькие числа в степени K возрастают быстрее чем сумма степеней K чисел 1..(K-1). Это означало что нижние K чисел не нужно было брать в блок, так как это только уменьшало скорость перебора. Но алгоритм был уже написан, и я не стал его переписывать ещё раз. Теоретически такая оптимизация могла дать выигрыш в скорости ещё до 1.5 раз.
Были попытки поиграться с разложением степеней вида
но стало понятно что для понижении степени на 2 нужно добавлять минимум по 4 числа. Теоретически это могло привести к некоторым оптимизациям или даже решениям, но не привело. :)
Также я тщательно анализировал каждое найденное приближённое решение, стараясь уловить в них закономерности. Выяснилось что некоторые числа присутствуют в решениях с большой вероятностью, а некоторые с очень маленькой. Также видно как у двух приближённых решений для одного N и одинакового максимального члена (N-M) остальные слагаемые устраивают массовые перестановки, которые кажутся не совсем хаотическими, но меняется почти каждое число.
Достаточно многое дал анализ решений для низших степеней (4..15). Стало понятно что с увеличением степени для одинакового N число вариантов перебора меньше, причём в разы.
Также сформулровалась гипотеза что у первого найденного точного решения N взаимнопросто с (K+1), которую, к сожалению, не удалось проверить. Но и приближённых решений у таких N также субъективно больше.
Если рассматривать процесс поиска с точки зрения теории вероятностей, то ситуация такая. Увеличение N на 1 даёт число вариантов для перебора в SQRT(2) раз больше. Что, в свою очередь, даёт более близкое решение на в среднем LN(SQR(2)).
Маленькие N обсчитывались очень быстро. Например, для степени 16 первые 80 чисел обсчитываются за несколько минут. А если взять слишком большое N, например 150, то прямой алгоритм перебора может не закончиться за время вашей жизни.
В любом случае, я получил свою порцию эмоций от этой задачи, и преклоняюсь перед интеллектом тех, кто смог найти хотя бы одно точное решение, чего мне, к сожалению, не удалось.
