# Divide & Conquer - DP

Authors: Andi Qu, Benjamin Qi

### Prerequisites

Using Divide & Conquer as a DP Optimization.

Allows you to reduce $O(N_{2})$ to $O(NgN)$.

## Tutorial

Resources | |||
---|---|---|---|

cp-algo | |||

Jeffrey Xiao | |||

GCP |

## Example - Circular Barn

Focus Problem – read through this problem before continuing!

You should already be familiar with the CHT solution.

### This section is not complete.

Check the official editorial.

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CEOI | Normal | View Solution | ||||

COI | Normal | External Sol | ||||

CF | Hard | Check CF | ||||

CF | Hard | Check CF | ||||

POI | Very Hard | View Solution | ||||

IOI | Very Hard | External Sol | ||||

Plat | Very Hard | External Sol | ||||

JOI | Very Hard |

JOI Bubblesort English Statement: You are given an array of length $N$ $(1≤N≤100,000)$. You must choose two numbers in this array and swap them. After swapping these two numbers, you sort the array using a bubble sort algorithm. What is the minimum number of bubble sort swaps necessary, assuming you choose the two initial numbers to swap optimally? The two initial numbers that you swap do not count towards the minimum number of bubble sort swaps.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Divide & Conquer - DP!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.