Rare
0/11
Divide & Conquer - DP
Authors: Andi Qu, Benjamin Qi
Using Divide & Conquer as a DP Optimization.
Prerequisites
Allows you to reduce to .
Tutorial
Resources | ||||
---|---|---|---|---|
cp-algo | ||||
Jeffrey Xiao | ||||
GCP |
Example - Circular Barn
Focus Problem – read through this problem before continuing!
View Internal SolutionYou 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
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CEOI | Normal | Show TagsD&C, DP | |||
COI | Normal | Show TagsD&C, DP | |||
CF | Normal | Show TagsD&C, DP | |||
AC | Normal | Show TagsD&C, DP | |||
CF | Hard | Show TagsD&C, DP | |||
CF | Hard | Show TagsD&C, DP | |||
POI | Very Hard | Show TagsD&C, DP | |||
IOI | Very Hard | Show TagsD&C, DP | |||
Plat | Very Hard | Show TagsD&C, DP | |||
JOI | Very Hard | Show TagsD&C, DP |
JOI Bubblesort English Statement: You are given an array of length . 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.