Собственно, расскажу о своей проблеме. SSP мне попалась в задаче J с финала ACM 2011 года. Я написал динамику по аналогии с рюкзаком за O(n) памяти и O(n * k) = O(n ^ (4/3)) времени (n - максимальное число, которое нужно разложить на слагаемые, k - количество элементов во множестве). Каким образом можно улучшить асимптотику? Можно ли как-то использовать две следующих вещи: а) множество состоит из квадратно-пирамидальных чисел, б) для разложения произвольного числа из промежутка [1; 1000000] требуется в худшем случае 6 чисел?

UPD. Буду особенно рад услышать финалистов :).

UPD2. От NEERC'а в прошлом году в финал вышли 13 команд, если не ошибаюсь, все они J решили. Почему такая гробовая тишина?

UPD3. По комментарию Артема я понял, что мое решение на финале бы прошло. Теперь буду рад услышать тех, кто загнали задачу на испанском сервере в ТЛ 3 секунды.

UPD4. Судя по топ20 решивших задачу на livearchive, наличие кого-то из русскоговорящих среди оставшихся 13 маловероятно. Придется загонять самому и/или с сокомандниками. Хотя если у кого-то есть идеи - буду очень благодарен, если этот человек ими поделится.

UPD5. Идея решения у меня появилась, скоро реализую, загоню, докажу асимптотику и отпишусь.

UPD6. Идея неверна, да и пытаться загнать такое решение на медленный сервер - дело бесполезное.

UPD7. Переписал динамику по вот этому разбору со следующими изменениями: а) искал не максимальную пирамидку, с которой возможен переход, а минимальную (максимальную находил при восстановлении ответа), б) отсек диапазон пирамидок, меньших n / count, где count - количество пирамидок в наборе. Решение зашло за 1 секунду. Вот код, спасибо Jokser'у за идею насчет минимальной пирамидки.