CD
единичную subset sum конструктивно я умею решать (относительно) быстро. Т.е. могу найти какое-то одно решение за O(S) памяти и (кажется) за O(n*S) времени
вам в институт Клея
Size: a a a
2020 July 09
CD
а, S это общая сумма. Тогда норм
AT
угу)
AT
не. Это таргет
CD
не важно
CD
это неполином от n
CD
сжатие будет ограничивать фактическую S только на порядках 2^N
CD
единичную subset sum конструктивно я умею решать (относительно) быстро. Т.е. могу найти какое-то одно решение за O(S) памяти и (кажется) за O(n*S) времени
Я, кстати, вроде легко одну в другую перекодирую. Действительно, каждое число si кодирует возможность выбрать один из трех векторов (si, 0, 0), (0, si, 0), (0, 0, si)
Любой вектор может быть записан на базисе 10^(2n), 10^(n), 1
Выбор одного из трёх может быть записан умножением всего множества на 3^n с последующей записью 1 в соответствующий трит
Любой вектор может быть записан на базисе 10^(2n), 10^(n), 1
Выбор одного из трёх может быть записан умножением всего множества на 3^n с последующей записью 1 в соответствующий трит
CD
S = (10^(2n)) * 3^(n), добро пожаловать :)
CD
там не 10 а max(si) наверное, не суть
AT
сейчас, погоди, пелена тупости сойдёт и я врублюсь)
CD
ну SUBSET-SUM умеет конвертировать вектора за счёт записи в виде a*x^2 + b*x + c
AT
ну n == 100, max(si) == 100
CD
и умеет конвертировать выбор одного из трех за счет остатка
AT
ну или 30 и 30
CD
ну или 30 и 30
я к тому, что это одна и та же задача
CD
как и всегда для всего NPC
AT
да. Просто уже для маленьких размерностей начинается жесть жестяная
CD
Я бы, кстати, попробовал от этого числа взять остаток на 1e9+7 и порешать subset
CD
А, надо подгонять ложные срабатывания под множество возможностей