Rare
0/10

Divide & Conquer - DP

Authors: Andi Qu, Benjamin Qi

Using Divide & Conquer as a DP Optimization.

Prerequisites

TutorialExample - Circular BarnProblems

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

Example - Circular Barn

Focus Problem – read through 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.

Check the official editorial.

Problems

StatusSourceProblem NameDifficultyTags
CEOINormal
Show TagsD&C, DP
COINormal
Show TagsD&C, DP
ACNormal
Show TagsD&C, DP
CFHard
Show TagsD&C, DP
CFHard
Show TagsD&C, DP
POIVery Hard
Show TagsD&C, DP
IOIVery Hard
Show TagsD&C, DP
PlatVery Hard
Show TagsD&C, DP
JOIVery Hard
Show TagsD&C, DP

JOI Bubblesort English Statement: You are given an array of length $N$ $(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.

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!