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:↵
↵
1. 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|$.↵
2. All elements at the visited indices are removed from the array.↵
3. 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?
↵
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:↵
↵
1. 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|$.↵
2. All elements at the visited indices are removed from the array.↵
3. 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?
