So, I came up with this problem:
You are given an array $$$a$$$ of length $$$N$$$. Additionally, you are given a set of $$$q$$$ operations, where each operation is defined by a pair $$$(s, p)$$$. You may perform any number of operations from this set in any order.
When you apply an operation $$$(s, p)$$$ to the current state of the array $$$a$$$, the following process occurs:
- You accumulate the sum of elements at indices $$$s, s+p, s+2p, \dots, s+kp$$$, where $$$s+kp$$$ is the largest valid index such that $$$s+kp \le |a|$$$.
- All elements at the visited indices are removed from the array.
- The remaining elements are re-indexed consecutively, preserving their original relative order.
Your goal is to perform a sequence of operations such that the total accumulated sum of all chosen elements does not exceed $$$maxW$$$, and this sum is as large as possible
Right now, there is no better solution than exponential, but I'm wondering is there some polynomial solution?
Auto comment: topic has been translated by GomerDoGo (original revision, translated revision, compare)
There's definitely no generalized solution for this (since if p = 10^9 for all operations it just boils down to knapsack), if a_i was limited I still don't think it's possible off the top of my head but I'll wait for an LGM to comment with an actual proof.
I feel like the subset sum reduction is not super trivial. Here's my attempt at it:
General setup. Subset sum problem, see if we can choose a sub-multi-set of $$$a$$$ that sums to exactly $$$maxW$$$.
If the subset sum problem has available numbers $$$b_1, b_2, ..., b_k$$$, then build $$$a$$$ like
Where you have $k$ 0s, then $$$b_1...b_k$$$, then a bunch more 0s. Your operations are $$$k+1, ..., 2k$$$ and $$$1...k$$$ (all with $$$p = \infty$$$). Basically, use the $$$k+1, ..., 2k$$$ operations to take any subset of numbers you'd like. Then use $$$1...k$$$ to move all the $$$b$$$ numbers "safely to the left", where taking the rest of the $$$k+1, ..., 2k$$$ will end up with zero value.
This problem I feel like is also way harder because $$$p \lt \infty$$$ makes things way more complicated in my opinion.