Permutation Descent Counts: Difference between revisions
imported>Kmk21 Created page with "IN PROGRESS This problem asks us, if we iterate over all the permutations of N distinct integers, how many those permutations have exactly v times in which the kth element is..." |
imported>Kmk21 No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
This problem asks us, if we iterate over all the permutations of N distinct integers, how many those permutations have exactly v times in which the kth element is greater than the k+1th element of the permutation. | This problem asks us, if we iterate over all the permutations of N distinct integers, how many those permutations have exactly v times in which the kth element is greater than the k+1th element of the permutation. | ||
We know that we can calculate the number of permutations of distinct integers (n!) or arbitrary integers (see DP solution in notebook). But how do we combine them for this solution here? | We know that we can calculate the number of permutations of distinct integers (n!) or arbitrary integers (see DP solution in notebook). But how do we combine them for this solution here? n is too large, of course to generate all permutations and count. | ||
The DP solution | The "natural" DP solution is calculating the solution for all dp[n<N][v<V] for the input N and V. The issue, however, is combining them. | ||
A first "guess" would be to iterate over each leading digit and do some "magic" recursion where we look for v in some cases, and v-1 in others depending on how large that leading digit is. The problem, then, is how do we get ONLY the n-1 permutations which have a leading digit SMALLER than our selected one (in which case we want v-1), or larger (in which case we want v). This is DP, though...so we can just include that in our DP state! | |||
Now the relation is simple! | |||
dp(n,v) = | dp(n,v,d) = number of permutations of n digits which have a descendency of v but which also start with a digit at most d. | ||
# loop from x = 1->d | |||
# add dp(n-1,v-1,x-1) to account for cases where where there would be a descendency from x to the sub-permutation | |||
# account for cases where there is NO descendency. To do this, we take the total number with descendency v, and subtract off those which have a start digit equal to or less than ours (remember, it can be "equal" since the subproblem thinks it's taking permutations of, say, 1-2-3-4, when in reality, if we removed 3, it could be taking them of 1-2-4-5. The answer is the same either way, though, so long as we adjust the parameters correctly). the recurrence becomes: add dp(n-1, v, 10) - dp(n-1,v,x) | |||
This makes our runtime 100*100*10 for the DP array * 10 for each iteration, which is plenty fast. We can actually demonstrate the the runtime is faster. since a given d value will only be called when x ==d or d+1, it means there is a constant number of times it will be invoked. In most cases where we have to iterate in the relation, this is linear. Here it's constant, so that falls out of the complexity. Understanding that proof is not important though, as the 100^2 * 10 * 10 is still fast enough. | |||
Note: This explanation is somewhat convoluted! Make it better if you want! | |||
[[Category:ICPC Problems]] | |||
[[Category:Gnyr2016]] | |||
[[Category:Algorithm Hard]] | |||
[[Category:Implementation Medium]] | |||
[[Category:Dynamic Programming]] | |||
[[Category:Big Numbers]] | |||
[[Category:Combinatorics]] | |||
[[Category:State Explosion]] | |||
Latest revision as of 02:01, 5 November 2017
IN PROGRESS
This problem asks us, if we iterate over all the permutations of N distinct integers, how many those permutations have exactly v times in which the kth element is greater than the k+1th element of the permutation.
We know that we can calculate the number of permutations of distinct integers (n!) or arbitrary integers (see DP solution in notebook). But how do we combine them for this solution here? n is too large, of course to generate all permutations and count.
The "natural" DP solution is calculating the solution for all dp[n<N][v<V] for the input N and V. The issue, however, is combining them.
A first "guess" would be to iterate over each leading digit and do some "magic" recursion where we look for v in some cases, and v-1 in others depending on how large that leading digit is. The problem, then, is how do we get ONLY the n-1 permutations which have a leading digit SMALLER than our selected one (in which case we want v-1), or larger (in which case we want v). This is DP, though...so we can just include that in our DP state!
Now the relation is simple!
dp(n,v,d) = number of permutations of n digits which have a descendency of v but which also start with a digit at most d.
- loop from x = 1->d
- add dp(n-1,v-1,x-1) to account for cases where where there would be a descendency from x to the sub-permutation
- account for cases where there is NO descendency. To do this, we take the total number with descendency v, and subtract off those which have a start digit equal to or less than ours (remember, it can be "equal" since the subproblem thinks it's taking permutations of, say, 1-2-3-4, when in reality, if we removed 3, it could be taking them of 1-2-4-5. The answer is the same either way, though, so long as we adjust the parameters correctly). the recurrence becomes: add dp(n-1, v, 10) - dp(n-1,v,x)
This makes our runtime 100*100*10 for the DP array * 10 for each iteration, which is plenty fast. We can actually demonstrate the the runtime is faster. since a given d value will only be called when x ==d or d+1, it means there is a constant number of times it will be invoked. In most cases where we have to iterate in the relation, this is linear. Here it's constant, so that falls out of the complexity. Understanding that proof is not important though, as the 100^2 * 10 * 10 is still fast enough.
Note: This explanation is somewhat convoluted! Make it better if you want!