1
$\begingroup$

If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \cdots < x_r = n\}$ such that $f(r,X) := \displaystyle\max_{j=0}^{r-1} \sum_{i = x_j}^{x_{j+1}-1} a_i$ is minimized over all possible $X$.


I can think of a brute force approach, that is, generate $\Theta ({{n-1} \choose {r-1}})$ sets $X$ and calculate the $\max$ for each $X$, each of which takes as many as $r$ steps. This is a very inefficient approach. How do I make it better? I feel like there is a way using DP. (Please feel free to edit the title if this is not DP).

This seems like a possible solution. What if we pre-compute $\displaystyle\Sigma_{i=j}^{j+k} {a_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function $$\text{best}(p,q) = \text{best way of having } q \text{ intervals such that we end at } [p-x,p] \text{ for some } x \geq 0$$ Our goal is to find $\text{best}(n,r)$ and backtrack to find the intervals.

$\text{best}(p,q) = \min \{ \text{best}(p,q-1), \ \max(\text{best}(p-1,q-1), \text{dist}(p-1,p)), \ \max(\text{best}(p-2,q-1), \text{dist}(p-2,p)), \dots) \}$

where $\text{dist}(x,y)$ = $\displaystyle\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult and time-hungry.

I tried greedy and I could generate counter-examples right away. Was not very helpful.

$\endgroup$
14
  • $\begingroup$ Hint: First prove that there is always an optimal solution with a very simple structure. $\endgroup$ – j_random_hacker Nov 16 '20 at 20:28
  • $\begingroup$ (A way to do this is to consider an arbitrary solution that does not have this structure, and show that by moving it "towards" this structure, you never make the solution worse. It follows that repeated steps will eventually get you to a solution with the structure, and it will be no worse than what you started with.) $\endgroup$ – j_random_hacker Nov 16 '20 at 20:31
  • $\begingroup$ I understand that that is the approach. Still, I fail to see how the proceed. Can you give me a possible construction? $\endgroup$ – oldsailorpopoye Nov 16 '20 at 22:28
  • $\begingroup$ What simple structure did you decide on? $\endgroup$ – j_random_hacker Nov 16 '20 at 23:48
  • $\begingroup$ How about pre-computing the $\Sigma_{i=j}^{j+k} {a_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function best(p,q) = best way of having $q$ intervals such that we end at $[p-x,p]$ for some $x \geq 0$. Our goal is to find best(n,r) and backtrack to find the intervals. best(p,q) = min(best(p,q-1), max(best(p-1,q-1),dist(p-1,p)), max(best(p-2,q-1), dist(p-2,p)), $\cdots$)) where dist(x,y) = $\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult. $\endgroup$ – oldsailorpopoye Nov 17 '20 at 8:35
2
$\begingroup$

Main idea: Instead of finding $X$ itself, find the minimum value for $f(r,X)$. After you do this, it is easy to find a minimal $X$. Simply greedily add elements to an interval until the sum of the interval is too large - once this happens, create a new interval at that position.

Finding the minimal value for $f(r,X)$ is a classic (maybe prototypical) binary search problem. The algorithm is as follows: binary search over the answer. Within your binary search, greedily add elements to an interval until the sum of the interval is higher than the answer - once this happens, create a new interval. (Note that this is the same method as is used to construct $X$.) At the end, check how many intervals you have formed - if it is $\leq r$ then it is possible to divide the array into $r$ intervals such that $f(r,X) \leq ans$. The time complexity is $O(NlogS)$, where $S$ is the sum of all $a_i$.

Although binary search does work for all practical values, your statement does state $\mathbb{N}$ as the possible size of elements. If elements can be arbitrarily large, we can use DP as you mentioned, fairly similar to the DP that you use. $best(p,q)$ can be the minimum $f(\cdot)$ taking $q$ intervals from the first $p$ elements. By transitioning in the same way as your statement, we get a trivial $O(N^3)$ solution.

We can also optimise this DP. One optimisation: $best(x,q)$ is monotonically increasing as $x$ increases, but $dist(x,p)$ is monotonically decreasing. So, we can use binary search to find the intersection of the two lines. The transition is now $O(logN)$ and the overall complexity is $O(N^2logN)$.

Important thing to note: this DP avoids the issues with your DP because it doesn't store the actual $X$ within the DP itself.

$\endgroup$
7
  • $\begingroup$ Binary search $\text{ans}$ over the interval $\left[\frac{\sum a_i}{n}, \sum a_i \right]$. And when we have $\leq r$ intervals while greedy searching, then it is NOT necessarily possible to divide it into $r$ intervals such that $f(r,X) \leq \text{ ans}$. Take $r=3, S = \{2,3,1,5,7\}$. When $\text{ans}=8$, we have $(2+3+1+5,7+6)$ form the initial intervals. Then we need to break it such that 7,6 gets separated. It isn't possible to break into intervals such that each sum is $\leq \text{ ans}$. $\endgroup$ – oldsailorpopoye Dec 3 '20 at 5:45
  • $\begingroup$ As for the "breaking", we can use break[x][y] that returns the proper break in O(1) or we can use something similar to Kadane's algorithm to compute the break in O(N). But pre computing this saves time. $\endgroup$ – oldsailorpopoye Dec 3 '20 at 5:46
  • $\begingroup$ @oldsailorpopoye Greedy must work (why? because each interval in the greedy has sum $\leq ans$, since we create a new interval if the sum would become greater than $ans$). For your example, we would get $(2,3,1)$,$(5)$,$(7)$,$(6)$. Since we have 4 intervals, we can't divide into 3 intervals, so $f(r,X) > 8$. $\endgroup$ – shgr1092 Dec 3 '20 at 9:31
  • $\begingroup$ @oldsailorpopoye At the end, greedy will produce a division into $\leq r$ intervals s.t. each interval has sum $\leq f(r,X)$ where $f(r,X)$ is the answer found from binary search. We can transform this into a solution with exactly $r$ intervals by splitting some of the intervals up (can be done arbitrarily). $\endgroup$ – shgr1092 Dec 3 '20 at 9:32
  • $\begingroup$ I misunderstood your solution in that case. I was treating $\text{ans}$ as the upper bound instead of answer and the resulting ans will be the min of all these ans for which we get a proper partitioning into $r$ intervals. Yours is a neater approach now that I realize it. $\endgroup$ – oldsailorpopoye Dec 4 '20 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.