Dragon Delivers | Editorial by racsosabe

#### Dragon Delivers Editorial

##### Prerequisites

- DP Divide and Conquer Optimization

##### Analysis

First of all, let's notice that if we want to delay some orders, then the optimal way to do so is by using a **complete interval** [L,R] and the deliver time **must** be some t[i] for a given interval.
It's easy to see that such optimal i is R for [L,R].

Then, our problem reduces to get the **minimum cost subarray partitioning** for the times, considering that the cost function of the interval [L,R] would be computed by:

```
cost(L,R) = d + c(sum(t[R] - t[i]) for i = L, ... R)
```

The former expression was deduced by the statement, d for sending the order and the other part is the count of delay cost.

Now, we see that we need a Dynamic Programming solution like:

```
DP(i,k) = min( DP(j-1,k-1) + cost(j,i) ) for all j <= i
```

where DP(i,k) is the minimum cost for partitioning elements from 1 to i in k subarrays.

If we did a Naive DP, we would get a O(n^3) complexity, since k goes from 1 to n and we would need to get the minimum of every DP(n,k) possible.

Fortunately, Divide and Conquer optimization helps us to solve these kind of problem **if the quadrangle inequality holds for the cost function**.

Now, let's see that quadrangle inequality holds for **minimum**:

```
Let A < B < C < D, then:
cost(A,D) + cost(B,C) >= cost(A,C) + cost(B,D)
After some arithmetic direct manipulation, we end up with:
0 >= (B-A)(t[C]-t[D])
Which is true since t[i] is strictly increasing, so
0 >= (some negative value)
```
Thus, we can apply Divide And Conquer Optimization to the problem:
```
Let prefix[i] be the sum of t[1..i]
getCost(id,L,R) function computes the value of using interval [L,R] as the id-th interval in the partition
until R.
getIntervalCost(L,R) function computes the cost of sending interval [L,R].
Our solve function will compute memo[id][i] for all i
The following is pseudocode mixed with Python :D

solve(id,L,R,optL,optR):
	if L > R: return
	mi = (L+R)/2
	bestAns = inf
	bestMid = mi
	for i=optL to min(mi,optR):
		if getCost(id,i,mi) < bestAns:
			bestAns = getCost(id,i,mi)
			bestMid = i
	memo[id][mi] = bestAns
	solve(id,L,mi-1,optL,bestMid)
	solve(id,mi+1,R,bestMid,optR)

getSolution():
	for i = 1 to n:
		memo[1][i] = getIntervalCost(1,i)
	ans = memo[1][n]
	for k = 2 to n:
		solve(k,1,n,1,n)
		ans = min(ans,memo[k][n])
	return ans
```

Dragon Delivers | Editorial by racsosabe

Download submission

All caught up!

View submission

Is your resume even shortlisted?