Abridged Problem Statement : Given a1, a2, ..., an, find the number of permutations of these numbers such that |a1 - a2| + |a2 - a3| + ... + |an - 1 - an| ≤ L where L is a given integer.
The editorial given is quite brief and the sample code is nearly unreadable. I have no idea how to do the dp.
Can anyone explain the solution? Thanks.
UPD : Thanks to ffao for the hint! I finally got how the dp works. The unobfuscated code with comments is here.
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
I_love_Tanya_Romanova
If you wanted to notify him, he won't receive any notification (as far as I know).
Not giving the full solution, but a few extra hints:
The main idea is to place the values ai in the array from the smallest to the largest. Consider some permutation in which a1, ..., ai have been placed.
Let's make an optimistic estimation of the cost of this permutation by saying that all empty spaces are equal to ai (clearly, the cost of any real permutation can't be smaller than this).
Now suppose you add a new value ai + 1 into this array in some empty position. How does your optimistic cost change? Try writing a few examples if it helps to see the formula for this.
Hmm after you said this, the source code's recurrence makes sense now. I'll see if I can understand it now.
UPD : I finally got the DP. I'll post the whole thing later.
"Abridged Problem Statement: Given ...."
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).