humbertoyusta's blog

By humbertoyusta, history, 3 years ago, In English

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, ... i$$$), and the transitions are about how inserting the next element ($$$i + 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 $$$n$$$, count the number of permutations of length $$$n$$$.

Yes, you read it well, we are going to compute $$$n!$$$ with a complicated dynamic programming in $$$O(n^2)$$$, 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 $$$1$$$ to $$$n$$$ in increasing order, when we insert the number $$$i+1$$$, we will have some chunks or connected components of the permutation that will contain all numbers from $$$1$$$ to $$$i$$$, let's focus on this $$$i$$$-th stage:

For example if we are going to insert $$$4$$$, and we are counting the permutations of size $$$7$$$, we can have two components, like $$$(2)$$$ and $$$(3, 1)$$$, that means that the final permutation will look like $$$(2??31??)$$$ or $$$(?2?31??)$$$, that is, there will be some numbers between each component (greater than $$$i$$$, 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 $$$i$$$ to $$$n$$$ (maybe $$$0$$$), then the first component, then other numbers greater than $$$i$$$ (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 $$$i$$$. Note that the components should appear in order.

States:

Now, let $$$DP_{i, j}$$$ be the number of ordered sets of components formed by the numbers from $$$1$$$ to $$$i$$$, with $$$j$$$ components, for example if we are counting the permutations of size $$$7$$$ and we have two components, $$$(2)$$$ and $$$(3, 1)$$$, their ordered set is $$$( (2) , (3, 1) )$$$ and will be counted in $$$DP_{3, 2}$$$.

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

The final answer of the problem will be $$$DP_{n, 1}$$$, since that will store the number of single components of size $$$n$$$, that is, the number of permutations of size $$$n$$$.

Transitions:

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

  • We can create a new component that will contain only number $$$i+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 $$$DP_{i+1, j+1} += DP_{i, j} \cdot (j + 1)$$$ since we will end up with one new component, and we will have $$$j+1$$$ available places.

  • We can add the number $$$(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) )$$$, we can place the $$$6$$$ 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) )$$$. This transition will be $$$DP_{i+1, j} += DP_{i, j} \cdot (2 \cdot j)$$$, since we will end up with the same number of components, and we will have $$$(2 \cdot j)$$$ available places for $$$i+1$$$.

  • We can merge two components into a bigger one placing $$$i+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) )$$$, we can merge the first and the second components with $$$6$$$, which will lead to $$$( (1, 2, 6, 4), (3, 5) )$$$. This transition will be $$$DP_{i+1, j-1} += DP_{i, j} \cdot (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)$$$ choices.

Complexity

There are $$$O(n^2)$$$ states, and $$$O(1)$$$ transitions per state, each one can be done in $$$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(n^2)$$$ and the memory usage is $$$O(n)$$$ or $$$O(n^2)$$$ 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 $$$i$$$ elements of smallest value (i.e. the elements $$$1, 2, 3, ..., i$$$ by value, not by position) of any permutation $$$p$$$ is always an ordered set of components, it will be obviously true at $$$i = 0$$$, since it's just the empty set. Now, for each $$$i$$$, we claim that we have the ordered set of the first $$$i-1$$$ elements, let's denote $$$j$$$ as the position of $$$i$$$ in the permutation:

  • If $$$p_j < p_{j-1}$$$ and $$$p_j < p_{j+1}$$$ (remember that $$$p_j = i$$$), then we can add a new component with the element $$$(i)$$$ between the rightmost existing component before $$$j$$$, and the leftmost existing component after $$$j$$$.

  • If $$$p_j > p_{j-1}$$$ and $$$p_j < p_{j+1}$$$, then we can add $$$i$$$ at the end of the component that ends at $$$j-1$$$.

  • If $$$p_j < p_{j-1}$$$ and $$$p_j > p_{j+1}$$$, then we can add $$$i$$$ at the beginning of the component that starts at $$$j+1$$$.

  • If $$$p_j > p_{j-1}$$$ and $$$p_j > p_{j+1}$$$, then we can merge the component that ends at $$$j-1$$$ with the one that starts at $$$j+1$$$ by placing $$$i$$$ between them.

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

This way we have proven that each subset that contains the smallest $$$i$$$ numbers of a permutation of size $$$n$$$ 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 $$$n$$$, that don't have three consecutive elements increasing or decreasing, that is, there is no $$$i$$$ $$$(1 \leq i \leq n-2)$$$ such that $$$p_i > p_{i+1}$$$ and $$$p_{i+1} > p_{i+2}$$$, or $$$p_i < p_{i+1}$$$ and $$$p_{i+1} < p_{i+2}$$$, starts with a number $$$s$$$ and ends with a number $$$e$$$. 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 $$$a_1, a_2, ..., a_n$$$ find the number of permutations of these numbers such that $$$|a_1 - a_2| + |a_2 - a_3| + ... + |a_{n - 1} - a_n| ≤ L$$$ where $$$L$$$ is a given integer. Constraints : $$$n ≤ 100, L ≤ 1000, a_i ≤ 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:

  • Vote: I like it
  • +242
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I was solving/trying to understand the solution to Skyscrapers literally yesterday and had a tough time since the idea was not described well in the official editorial (didn't know there was an unofficial one). Thanks!

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Another problem that can be solved using this trick: SWERC 2020 F

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by humbertoyusta (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

This idea can be applied to solve a CSES problem: https://cses.fi/problemset/task/1075

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help in E. Phoenix and Computers . I am unable to understand the code mention in tutorial.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I guess you ask about how to solve with this technique, since the other way is explained in editorial and comments.

    For simplicity, let's imagine that the problem is about turning bits on in a bitmask, and a bit will turn on automatically when their adjacents are turned on.

    You will start with $$$000000$$$ and then you will turn on some bits, in each case you can choose any $$$0$$$ and turn it on, if you turn on the $$$i$$$-th bit and the bit $$$i-2$$$ is turned on, then the $$$i-1$$$ will be turned on, similarly for $$$i+2$$$ and $$$i+1$$$.

    Then we can think about $$$dp$$$ storing the number of bits that are already on, and the number of subsegments of $$$1$$$ 's, the components.

    Let $$$dp_{i,j}$$$ be the number of ways to turn on $$$i$$$ bits, with $$$j$$$ components of $$$1$$$s, the final answer will be $$$dp_{n,1}$$$, and the transitions are:

    • Turn on one bit at the beginning or the end of a component.

    • Turning on one bit which is adjacent to a $$$0$$$, and then after it there is one component, and the $$$0$$$ will turn on automatically.

    • Create a new component.

    • Merge two components with one $$$0$$$ that will be turned on automatically.

    • Merge two components with two $$$0$$$ 's that will be turned on automatically.

    The final complexity is $$$O(n^2)$$$.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry I didn't get what these transitions are doing . How they are actually letting us to right answer. Could you please help more in that part.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Maybe some examples can help you:

        First transition example: $$$00110001$$$ -> $$$0(1)110001$$$ -> $$$01110001$$$

        This is counted from $$$dp_{3,2}$$$ to $$$dp_{4,2}$$$.

        Second transition example: $$$00110001$$$ -> $$$(1)0110001$$$ -> $$$11110001$$$

        This is counted from $$$dp_{3,2}$$$ to $$$dp_{5,2}$$$.

        Third transition example: $$$01000001$$$ -> $$$0100(1)001$$$ -> $$$01001001$$$

        This is counted from $$$dp_{2,2}$$$ to $$$dp_{3,3}$$$.

        Fourth transition example: $$$0011001$$$ -> $$$0011(1)01$$$ -> $$$0011111$$$

        This is counted from $$$dp_{3,2}$$$ to $$$dp_{5,1}$$$.

        Fifth transition example: $$$00110001$$$ -> $$$00110(1)01$$$ -> $$$00111111$$$

        This is counted from $$$dp_{3,2}$$$ to $$$dp_{6,1}$$$.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why don’t we have to consider the case : Merge two component without any 0 between? For example : 01110110 -> 0111(1)110 -> 01111110

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        In that case according to the statement, that computer will turn on automatically, so you don't need to turn it on manually.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I see. Thanks:D

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem Can anyone give me some hints in above problem? How to represent state whether he is left side or right side? How to keep track of his current position using the above method? Thanks in advance.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I am iterating from 1 to n. There are three cases:-

    1) i==s

    • form new components then it will contribute -x[i] (because his neighbour will be bigger then current element) and d[i] (because from here we will jump to bigger index),
    • we will join this element to the starting of first component so it will + x[i](as its neighbour is smaller than him) and +c[i](jumping to smaller index).

    2) i==e

    • form new components( -x[i]+b[i]).

    • join to last component ends( x[i]+a[i]).

    3) i!=s and i!=e

    • merge two components ( 2*x[i] + a[i] + c[i]).

    • form new components if possible then it will contribute ( (-2*x[i]) + d[i] + b[i]).

    • join to start of components if possible then it will contribute( c[i] + b[i]).

    • join to end of components if possible then it will contribute( a[i] + d[i]).

    my solution . You can have look at my solution.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Adding more problem using this trick: TOKI Regular Open Contest #11 H

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have some doubts :

  1. In transitions :
    What happens if the first and last position(1 and n) were already occupied by the components till (1, 2, .... i — 1), then if I add i, will dp(i + 1, j) += 2 * j * dp(i, j) not overcount here.

  2. I can't understand the proof of correctness, can somebody explain it in simpler terms what it tries to explain.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To answer your questions:

    First, if the first position is already occupied and you add a new element, you will end up with some other permutation, which will be valid because of the way that the permutation is constructed, and the permutation that you was looking for, will be reached through other set of transition and states, similarly for the last one. The proof of correctness can help you to get this.

    If you don't get this, you can also add a new state which marks if the first and last position are already filled, then the states will be dp[number of elements placed][number of components][is the start occupied(boolean state)][is the end occupied], this will make transitions more complicated, but will be needed in some problems that you need to consider start and end separately, like CEOI 2016 Kangaroo.

    To the second question, The proof of correctness basically try to explain that for each one of the $$$n!$$$ permutations, there is exactly one way to get that permutation through some set of transitions and states of this dynamic programming, and it does by analizyng the structure of the prefixes (elements $$$1, 2, ... i$$$, by value, not position) and how they form a set of components.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I tried to understand your Dp State :

      DP(i,j) is the number of ordered sets of components formed by the numbers from 1 to i, with j components.

      Now I think, thinking about positions where elements land is not useful to think about as the Dp State never says anything about the positions where things will land.

      Is this correct? If yes, was my above question wrong ?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right, dp state never says anything about the positions, thinking about where elements land in the final permutation is only useful to proof the correctness, and maybe to understand a bit what the states represent.

»
3 years ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

This tutorial has a major drawback in terms of writing. I have no idea what you mean by the title "dp with connected components" and you do not explain it in any concise way and additionally as an example you provide a problem which is trivial, but whose solution is very long when using your technique. It's just a terrible way to engage the reader. I have no way or checking whether I know what you are talking about without reading the whole thing, a short explanation or a more interesting example would definitely help. Ideally you should be able to express the main idea in a few sentences and the first provided example should be both intriguing and its solution should be simple when using presented technique

Nonetheless, I believe this is probably a good and interesting content and I appreciate the effort (i.e. I didn't wanna trash you, but rather provide constructive criticism)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Thanks for your feedback, It's constructive and I appreciate it very much.

    I added a section explaining what I mean with the title, it may be too late, but at least it can help future readers.

    About the example, I know that is not a good way to engage the reader, but I thought that it will be easier to understand without any extra constraints, so I went for simplicity instead of providing something more interesting, the technique is not very easy to come up with, and when I was learning about it, I couldn't understand it until I thought about this example, so I thought it will be better to start from it.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Your effort is really appreciable. I also was having very hard time understanding it. But you made it easy!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Thanks, I think this new added paragraph is very good! It indeed exactly served the purpose of what I think was lacking and encouraged me to read the whole thing :D Didn't know about this technique, very nice one

»
2 years ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

Sorry for necroposting, but I just wanted to point out that there is an easier way to solve 1515E - Phoenix and Computers using connected components dp than the linked solution in my opinion.

Hint 1
Hint 2
Hint 3
Hint 4
Solution
»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone explain the idea of this problem ARC 117 E: Zero-Sum Ranges using this trick?