jeffreyxiao
Hi! I'm a student at the University of Waterloo studying software engineering. I have an interest in large scale distributed algorithms and infrastructure for data analytics. I also enjoy working with low level systems.

# Divide and Conquer Optimization

#### Monday, December 14, 2015

Dynamic ProgrammingProgramming

## Introduction

This optimization for dynamic programming solutions uses the concept of divide and conquer. It is only applicable for the following recurrence:

$\text{dp}[i][j] = \min_{k < j}\{dp[i-1][k] + \text{C}[k][j]\}$ $\text{min}[i][j] \leq \text{min}[i][j+1]$ $\text{min}[i][j] \text{ is the smallest k that gives the optimal answer}$

This optimization reduces the time complexity from $O(KN^2)$ to $O(KN log \ N)$

## Example Problem: Codeforces Round 190: Div. 1E

There are $N$ people at an amusement park who are in a queue for a ride. Each pair of people has a measured level of unfamiliarity. The people will be divided into $K$ non-empty contiguous groups. Each division has a total unfamiliarity value which is the sum of the levels of unfamiliarity between any pair of people for each group.

Determine the minimal possible total unfamiliarity value.

## Sample Input

8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

## Sample Output

7

## Sample Explanation

One optimal division is $\{1, 2, 3\} | \{4, 5, 6\} | \{7, 8\}$ which sum to $7$

## Analysis

First let us notice the $O(KN^2)$ solution:

for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = 1 << 30;

dp = 0;

for (int i = 1; i <= k; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= j; k++)
dp[j][i] = Math.min(dp[j][i], dp[k-1][i-1] + cost(k, j));

For each iteration of $j$, we are looping from $1$ to $j$, but if we use the observation that $\text{minK}[j][i] \leq \text{minK}[j+1][i]$, we can reduce that left and right bounds for each iteration.

Let us define function $\text{compute}(g, i, j, l, r)$ that computes $\text{dp}[i...j][g]$ knowing that $l \leq k \leq r$

We first call the function with the following parameters: $\text{compute}(g, 1, n, 1, n)$. This step will take $O(N)$ time. For each call, if we compute the value of $\text{dp}[g][{i+j\over 2}]$, we can essentially divide the function into two:

$\text{compute}\left(g, i, {i+j\over 2} - 1, l, k\right)$ $\text{compute}\left(g, {i+j\over 2} + 1, j, k, r\right)$

At each depth of recursion, there are only $2N$ computations to be done. The total depth of recursion will be $log\ N$. Thus, for each value of $g$, the running time is $O(Nlog\ N)$. We then call the function for all values of $g$, so the final running time is $O(KNlog\ N)$

## Code

import java.util.*;
import java.io.*;

public class main {

static PrintWriter out;
static StringTokenizer st;

static int n, k;
static int[][] a;
static int[][] dp;

public static void main(String[] args) throws IOException {
out = new PrintWriter(new OutputStreamWriter(System.out));

a = new int[n + 1][n + 1];
dp = new int[n + 1][k + 1];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = readInt() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = 1 << 30;

dp = 0;

for (int i = 1; i <= k; i++)
compute(i, 1, n, 1, n);

out.println(dp[n][k] / 2);
out.close();
}

static void compute(int g, int i, int j, int l, int r) {
if (i > j)
return;
int mid = (i + j) / 2;
int bestIndex = l;
for (int k = l; k <= Math.min(r, mid); k++) {
int val = dp[k - 1][g - 1] +
(a[mid][mid] - a[mid][k - 1] - a[k - 1][mid] + a[k - 1][k - 1]);
if (val < dp[mid][g]) {
dp[mid][g] = val;
bestIndex = k;
}
}
compute(g, i, mid - 1, l, bestIndex);
compute(g, mid + 1, j, bestIndex, r);
}

static String next() throws IOException {
while (st == null || !st.hasMoreTokens())
return st.nextToken();
}

static int readInt() throws IOException {
return Integer.parseInt(next());
}
}

This post is a part of a series of three posts on dynamic programming optimizations:

Previous Post
Knuth's Optimization
Next Post
UofT Hacks