Hello Codeforces,↵
↵
Is anyone familiar with this problem:↵
↵
Consider an array of items with labels $1, \dots, n$ the $i$th of which has a weight $W_i$ and a cost $C_i$. The array must be partitioned into disjoint subarrays. The weight of a subarray from $i$ to $j$ is the sum $W_i + W_{i+1} + \dots + W_{j}$ and the cost is the maximum $\max(C_i, C_{i+1}, \dots, C_{j})$. No subarry in the partition can exceed a given maximum weight $W_\max$. Subject to this contraint, we wish to minimize the sum of subarray costs, i.e. the sum of maximums.↵
↵
I have devised a solution that is $O(n \log n)$. I wonder if this is a well known problem and if a linear time solution exists. Also, are there any published results in the literature?↵
↵
I am also curious about the extension of this problem to trees. Partition a tree into paths subject to the same constraints.
↵
Is anyone familiar with this problem:↵
↵
Consider an array of items with labels $1, \dots, n$ the $i$th of which has a weight $W_i$ and a cost $C_i$. The array must be partitioned into disjoint subarrays. The weight of a subarray from $i$ to $j$ is the sum $W_i + W_{i+1} + \dots + W_{j}$ and the cost is the maximum $\max(C_i, C_{i+1}, \dots, C_{j})$. No subarry in the partition can exceed a given maximum weight $W_\max$. Subject to this contraint, we wish to minimize the sum of subarray costs, i.e. the sum of maximums.↵
↵
I have devised a solution that is $O(n \log n)$. I wonder if this is a well known problem and if a linear time solution exists. Also, are there any published results in the literature?↵
↵
I am also curious about the extension of this problem to trees. Partition a tree into paths subject to the same constraints.
