На hackerrank.com решаю задачки по питону (вопрос не касается этого языка, потому прошу не переносить тему).
Ресурс английский, если что.
И там попалась интересна задача следующего содержания ( ссылка на оригинал ):

Дано
Вам дана функция f(X) = X^2
Также Вам даны K списков (массивов). Список под номером i состоит из Ni элементов
Вам надо выбрать по одному значению из каждого списка таким образом, что бы уравнение ниже принимало максимальное значение:
S = (f(X1)+f(X2)+f(X3)+...+f(Xk))%M, где Xi - элемент выбранный из списка под номером i, а % - деление по модулю (остаток от деления)


Входные данные
В первой строке 2 целочисленных значения K и M разделённые пробелом
Каждая из следующих K строк содержит целочисленное значение Ni сопровождаемое Ni целочисленными значениями, элементами списка, разделёнными пробелами

Выходные данные
Одно число Smax - максимальное возможное значение S

Ограничения (размерность)
1 ⩽ K ⩽ 7
1 ⩽ M ⩽ 1000
1 ⩽ Ni ⩽ 7
1 ⩽ элементы списка ⩽ 10^9

Пример
Вход
3 1000
2 5 4
3 7 8 9
5 5 7 8 9 10

Выход
206

Пояснение
Выборка 5 из 1-ого списка, 9 из 2-ого и 10 из 3-его даёт максимальное значение S:
S = (5^2+9^2+10^2)%1000 = 2016

Мой вопрос
Эта задача на ресурсе расположена в разделе itertools. Как я понимаю, автор задачи предполагает её решение "в лоб" полным перебором всех вариантов (используя соответствующую библиотеку языка). А вот мне стало интересно, возможно ли решение этой задачи более оптимальным способом?

Пробовал:
1. вывести упрощённую формулу для S математически - пока не получилось
2. подумывал об динамическом программировании - да тут тоже не подойдёт, потому что оптимальный вариант на шаге i может стать далеко не оптимальным для шага i+1. Так получается, что отсеять часть вариантов слёту не выйдет.

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

P.S. Можно, конечно, зайти и посмотреть решение этой задачи другими участниками, но мне это кажется очень неинтересным подходом, который ведёт не к освоению нового алгоритма (и получению связанных с ним знаний), а к банальному списыванию чужого решения :) Да и далеко не факт, что кто-то из них решал эту задачу не в лоб (судя по вкладке "дискуссии", так и есть - все решали "в лоб") :)

Вот что пока придумалось:
1. сокращаем сразу размерность элементов списка вычисляя на лету при считывании их значение (X % M)^2 % M
2. для каждого уровня вычисляем набор оптимальных сумм следующих уровней (что бы в итоге получилось число M-1, являющиеся максимально возможным значением указанной функции)
3. после нахождения "оптимальных сумм следующих уровней" для последнего уровня, ищем найменьший элемент и отнимаем его от M-1. Это и есть наша оптимальная сумма


так получаем следующую сложность:
1. O(Kmax*Nmax)
2. тут посчитаем... для первого уровня выполнится максимум Nmax итераций, для второго Nmax^2, для третьего Nmax^3 и так далее, но количество операций на каждом уровне не превысит Nmax*M, потому как всего возможно M оптимальных значений для не более чем Nmax элементов. Условно, около O(Kmax*Nmax*M)
3 O(M)

По сути имеем линейную зависимость от каждого из параметров, в то время как обычный перебор имеет сложность O(Nmax^K), что является экспоненциальной функцией и при увеличении как Nmax, так и K функция возрастает далеко не линейно. Полный перебор является оптимальным для случаев, когда M>(Nmax^(K-1))/Kmax.

С учётом наших максимальных значений получается что M = 1000, а (Nmax^(K-1))/Kmax = (7^6)/7 = 16807. На максимальных значениях в указанной задаче мой алгоритм должен отработать приблизительно в 16 раз быстрее чем полный перебор.

Итак, есть ли ещё что-то более оптимальное решение? :) Я почти уверен что оно есть...

Dima TDima T(X % M)^2 % M не равно (X ^ 2) % M
Засомневался, затестил. Похоже что равно, только не пойму почему.

Еще из массивов после приведения можно выкидывать одинаковые значения, т.е. чтобы в каждом оставались только уникальные значения.

X = k * M + b, где k и b - целые числа (в данном случае b - это остаток от деления x на M)

X^2 % M = (k * M + b)^2 % M = ((k^2 * M) * M + (2 * k * b) * M + b^2) % M = ((k^2 * M + 2 * k * b) * M + b^2) % M = ((k^2 * M + 2 * k * b) * M) % M + (b^2) % M

Если и k и b целые числа (а они целые), то результат следующей операции равен:
((k^2 * M + 2 * k * b) * M) % M = 0

Получаем, что
X^2 % M = (b^2) % M, где b, как мы помним, это остаток от деления X на M, то есть b = X % M
X^2 % M = (X % M)^2 % M

Вот так понятнее стало? :)

Вот реализация алгоритма на питоне. Все тесты прошло, значит алгоритм правильный.

Продолжаю думать над последующей оптимизацией.

P.S. С входными параметрами я как всегда схитрил, потому что при таких значениях их нет смысла читать по одному, а если читать построчно, то количество чисел в строке знать не обязательно. Можно просто разделить по пробелу :)

kealon(Ruslan),

Да.. точно... лишнее действие было. Прошло все тесты.
Только ничего более оптимального пока не придумывается.

Радует конечно, посмотрел вариант автора... проверил... на 7 списках по 7 элементов его решение отрабатывает за секунду, а моё за 0.02 секунды :)
Вот что значит подходить с умом.

kealon(Ruslan)Програмёрkealon(Ruslan),
Только ничего более оптимального пока не придумывается.
1. не совсем уверен в ленивом заполнении множества opt = set(...), может стоит развернуть циклы
2. при полном заполнении opt на любом этапе цикла ответ будет однозначно (M-1), можно выходить

PS: в реальной олимпиаде на такие выкрутасы вряд ли будет время

Знаем... участвовали... :)
Но на реальной олимпиаде и подход немного другой. Всё, что там требуется - это что бы программа работала и отрабатывала в срок. Как только эти требования выполнены работа над задачей завершается и следует переходить к следующей.

Но мы же не на олимпиаде... Нам тут и подумать можно... и потупить, если что :)