[Tutorial] Dp with connected components, a simple way to understand it.

[Tutorial] Dp with connected components, a simple way to understand it.

Inspired by Tutorial Non-trivial DP Tricks and Techniques, by zscoder, This is actually a well known DP trick, and has appeared in some problems, but I have not found a detailed tutorial to easily understand it from scratch, me and some friends had troubles to learn this trick, so I will try to explain in a simple and detailed way.

What is dp with connected components:

The main idea of this trick is building permutations inserting the elements in increasing order, and storing as a state of the dynamic programming the number of chunks or components that represents some prefix of elements (i.e elements 1,2,...i1,2,...i), and the transitions are about how inserting the next element (i+1i+1), will affect this chunks or components. (note that these are the values of the elements, not their position in the permutation)

This trick can be useful to count the number of permutations with some characteristics or constraints and to find permutations that maximize or minimize some functions.

The simplest problem that can be solved with this:

Given a number nn, count the number of permutations of length nn.

Yes, you read it well, we are going to compute n!n! with a complicated dynamic programming in O(n2)O(n2), isn't that amazing? (Do not be afraid, with this trick you will solve problems that can not be solved with basic combinatorics)

Basic Insights:

We will try to build all the permutations.

We will insert the numbers from 11 to nn in increasing order, when we insert the number i+1i+1, we will have some chunks or connected components of the permutation that will contain all numbers from 11 to ii, let's focus on this ii-th stage:

For example if we are going to insert 44, and we are counting the permutations of size 77, we can have two components, like (2)(2) and (3,1)(3,1), that means that the final permutation will look like (2??31??)(2??31??) or (?2?31??)(?2?31??), that is, there will be some numbers between each component (greater than ii, because all others are already placed), that will be placed in some later operation, the components will appear in order, and the adjacent numbers in the components will be adjacent in the final permutation.

In the final permutation there will be some numbers from ii to nn (maybe 00), then the first component, then other numbers greater than ii (at least one, since otherwise the first and the second component would be only one bigger component), the second component, and so on, finally after the last component there may be some numbers greater than ii. Note that the components should appear in order.

States:

Now, let DPi,jDPi,j be the number of ordered sets of components formed by the numbers from 11 to ii, with jj components, for example if we are counting the permutations of size 77 and we have two components, (2)(2) and (3,1)(3,1), their ordered set is ((2),(3,1))((2),(3,1)) and will be counted in DP3,2DP3,2.

Here in an ordered set, the order of elements matters, not just their values, set (a,b)(a,b)≠≠ set (b,a)(b,a), and set (a,b)(a,b)≠≠ set (a,c)(a,c).

The final answer of the problem will be DPn,1DPn,1, since that will store the number of single components of size nn, that is, the number of permutations of size nn.

Transitions:

Now, for the transitions think how inserting the i+1i+1-th number will affect the set of components formed by numbers from 11 to ii:

• We can create a new component that will contain only number i+1i+1, we can place this new components in any place between two already existing components, before the first one, or after the last one. This transition will be DPi+1,j+1+=DPi,j⋅(j+1)DPi+1,j+1+=DPi,j⋅(j+1) since we will end up with one new component, and we will have j+1j+1 available places.

• We can add the number (i+1)(i+1) at the beginning or the end of any existing component, let's say, we have this set of components ((1,2),(4),(3,5))((1,2),(4),(3,5)), we can place the 66 at the beginning or the end of any component, if we put at the beginning of the first one, we will end up with ((6,1,2),(4),(3,5))((6,1,2),(4),(3,5)). This transition will be DPi+1,j+=DPi,j⋅(2⋅j)DPi+1,j+=DPi,j⋅(2⋅j), since we will end up with the same number of components, and we will have (2⋅j)(2⋅j) available places for i+1i+1.

• We can merge two components into a bigger one placing i+1i+1 at the end of a component and at the beginning of the next one at the same time, let's say, we have this set of components ((1,2),(4),(3,5))((1,2),(4),(3,5)), we can merge the first and the second components with 66, which will lead to ((1,2,6,4),(3,5))((1,2,6,4),(3,5)). This transition will be DPi+1,j−1+=DPi,j⋅(j−1)DPi+1,j−1+=DPi,j⋅(j−1), since we will end up with one less component (we merged two into one), and we can merge any two consecutive components, so there are (j−1)(j−1) choices.

Complexity

There are O(n2)O(n2) states, and O(1)O(1) transitions per state, each one can be done in O(1)O(1) time complexity, also we can get rid of storing all states in memory only storing the current and the previous one, so the total time complexity is O(n2)O(n2) and the memory usage is O(n)O(n) or O(n2)O(n2) depending on the implementation.

Proof of correctness:

First, we will prove that any permutation can be counted with this dp, and after that, that each one will be counted exactly once.

First, let's show by induction that the subset of the ii elements of smallest value (i.e. the elements 1,2,3,...,i1,2,3,...,i by value, not by position) of any permutation pp is always an ordered set of components, it will be obviously true at i=0i=0, since it's just the empty set. Now, for each ii, we claim that we have the ordered set of the first i−1i−1 elements, let's denote jj as the position of ii in the permutation:

• If pj<pj−1pj<pj−1 and pj<pj+1pj<pj+1 (remember that pj=ipj=i), then we can add a new component with the element (i)(i) between the rightmost existing component before jj, and the leftmost existing component after jj.

• If pj>pj−1pj>pj−1 and pj<pj+1pj<pj+1, then we can add ii at the end of the component that ends at j−1j−1.

• If pj<pj−1pj<pj−1 and pj>pj+1pj>pj+1, then we can add ii at the beginning of the component that starts at j+1j+1.

• If pj>pj−1pj>pj−1 and pj>pj+1pj>pj+1, then we can merge the component that ends at j−1j−1 with the one that starts at j+1j+1 by placing ii between them.

So for any case we can obtain a new ordered set from the previous one by adding ii.

This way we have proven that each subset that contains the smallest ii numbers of a permutation of size nn corresponds to a ordered set of components, and, since for a fixed permutation, in each stage we will only have exactly one option that can end up in that permutation after all stages are done, each permutation will be counted exactly once.

Code

Problems that can be solved with this trick:

Building the permutations in this way can be used to count the number of permutations with some properties, Now I will share some problems that can be solved with this trick, in relative increasing order of dificulty:

• Count the number of permutations of length nn, that don't have three consecutive elements increasing or decreasing, that is, there is no ii(1≤i≤n−2)(1≤i≤n−2) such that pi>pi+1pi>pi+1 and pi+1>pi+2pi+1>pi+2, or pi<pi+1pi<pi+1 and pi+1<pi+2pi+1<pi+2, starts with a number ss and ends with a number ee. This problem is actually CEOI 2016 Kangaroo. You can see the solution explained here.

• B. Ant Man

• E. Phoenix and Computers , editorial doesn't mention that can be solved with this, but you can see a code with comments here.

• JOI 2016 Open Contest — Skyscrapers, Given a1, a2, ..., ana1,a2,...,an find the number of permutations of these numbers such that |a1 − a2| + |a2 − a3| + ... + |an − 1 − an| ≤ L|a1−a2|+|a2−a3|+...+|an−1−an|≤L where LL is a given integer. Constraints : n ≤ 100, L ≤ 1000, ai ≤ 1000n≤100,L≤1000,ai≤1000. You can see the solution explained here in "Connected Component" DP section.

• UTS Open '21 P7 — April Fools, editorial notes can be found here

I would be grateful if you discuss about the topic in comments, let me know if there is any mistake in the blog, or share other problems that can be solved with this trick.

UPD: Here I will list the problems shared by community members, Thanks to everyone who contributed, note that these problems are not sorted by any particular order: