PrevNext
Rare
 0/11

Divide & Conquer - DP

Authors: Andi Qu, Benjamin Qi

Using Divide & Conquer as a DP Optimization.

Edit This Page

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 – try your best to solve this problem before continuing!

View Internal Solution

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 NameDifficultyTags
CEOI
2004 - Two Sawmills
Normal
Show TagsD&C, DP
COI
2015 - Nafta
Normal
Show TagsD&C, DP
CF
Bear and Bowling 4
Normal
Show TagsD&C, DP
AC
Yakiniku Restaurants
Normal
Show TagsD&C, DP
CF
Ciel and Gondolas
Hard
Show TagsD&C, DP
CF
Yet Another Minimization Problem
Hard
Show TagsD&C, DP
POI
2014 - Solar Lamps
Very Hard
Show TagsD&C, DP
IOI
2014 - Holiday
Very Hard
Show TagsD&C, DP
Plat
Mowing Mischief
Very Hard
Show TagsD&C, DP
JOI
2013 - Bubblesort
Very Hard
Show TagsD&C, DP

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