Chx_ini's blog

Help needed in Atcoder Educational DP task T permutations.
By Chx_ini, history, 10 months ago, In English

I wanted help in atcoder educational DP contest Task T. I understand the whole idea of task and i had a confusion in the transition when the sign is > then according to editorial then are summing all the values will n including the j itself.

awoo comented on this which is

here

img But i still dont get it how it is going to stop double counting. and whats the use of including the current digit j.When there is inequality.

thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If we just take greater in case of < and vice versa there will surely be excess counting of digits where the digits are going to get used in munltiple places. So please help me.

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

You chose a pretty cool problem to explore. I guess I can answer better now with all the experience I didn't have 5 years ago.

Generally, there are two ways of building a permutation iteratively (i.e. making a change to a permutation of size $$$i$$$ to turn it into a permutation of size $$$i+1$$$ until you reach the required size).

  1. The one I prefer calling ’’bottom up''. If you have a permutation of size $$$n$$$, you can choose some position $$$i$$$ from $$$1$$$ (before all elements) to $$$n+1$$$ (after all elements) and insert $$$n+1$$$ there. If you draw a graph such that OX are indices and OY are values, then the operation basically inserts the new highest point, moving the points with indices from $$$i$$$ to $$$n$$$ to the right by $$$1$$$.

  2. The one I prefer calling ’’left to right''. This is kinda orthogonal to the ’’bottom up'' approach. Instead of choosing a position $$$i$$$ and inserting a value $$$n+1$$$, you choose a value $$$i$$$ and insert it in a position $$$n+1$$$. Think about the graph. You now insert the new rightmost point, and the graph should expand accordingly. That accordingly is actually up. In order to preserve the permutation, you take all existing elements greater than or equal to $$$i$$$ and increase them by $$$1$$$.

Turns out, ’’left to right'' construction works great for this problem. $$$\mathit{dp}_i$$$ counts the number of permutations of size $$$i$$$ that correspond to the first $$$i-1$$$ signs. If you insert a new value to the right and increase all prior greater or equal values by $$$1$$$, then none of the prior signs break.

However, since you also want to satisfy the $$$i$$$-th sign, you want to remember what the $$$i$$$-th value was. So we save it in a state and check against the new value.

That gives you an $$$O(n^3)$$$ solution. I think the transition to $$$O(n^2)$$$ with the prefix sums is described well already.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    This is some holy grail of knowledge. Thank you very much . I understood it clearly.And yes I do have to apply prefix sum for an O(n^2) time complexity.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "In order to preserve the permutation, you take all existing elements greater than or equal to i and increase them by 1"

    I did not fully get this statement. How this never breaks the permutation? If we for example are going to build a permutation of length 5 and the first element is 5 so according to the statement when choosing the second element we have to increase the previous elements by 1 but we can not increase 5 to be 6 because the permutation is of length 5

    → Reply