PrevNext
Rare
 0/9

Divide & Conquer - DP

Authors: Andi Qu, Benjamin Qi

Prerequisites

Using Divide & Conquer as a DP Optimization.

Allows you to reduce O(N2)\mathcal{O}(N^2) to O(Nlog⁡N)\mathcal{O}(N\log N).

Tutorial

Resources
cp-algo
Divide and Conquer DP
Jeffrey Xiao
Divide and Conquer Optimization
GCP
15.4.2 - Divide & Conquer Optimization

Example - Circular Barn

Circular Barn

Plat - Hard

Focus Problem – read through this problem before continuing!

You should already be familiar with the CHT solution.

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Add analysis later.

Check the official editorial.

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CEOI
2004 - Two Sawmills
Normal
Show Tags

D&C, DP

View Solution
COI
2015 - Nafta
Normal
Show Tags

D&C, DP

External Sol
CF
Ciel and Gondolas
Hard
Show Tags

D&C, DP

Check CF
CF
Yet Another Minimization Problem
Hard
Show Tags

D&C, DP

Check CF
POI
2014 - Solar Lamps
Very Hard
Show Tags

D&C, DP

View Solution
IOI
2014 - Holiday
Very Hard
Show Tags

D&C, DP

External Sol
Plat
Mowing Mischief
Very Hard
Show Tags

D&C, DP

External Sol
JOI
2013 - Bubblesort
Very Hard
Show Tags

D&C, DP

Internal Sol

JOI Bubblesort English Statement: You are given an array of length NN (1≤N≤100,000)(1 \le N \le 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!

Join Forum
PrevNext