Problem website:
https://www.hackerrank.com/contests/world-codesprint-5/challenges/longest-increasing-subsequence-arrays
Analysis from editorial:
Because we must use numbers from to fill each array and we must be able to build an -element LIS for each array, we know each number from to must appear in the array in increasing order.
We can select positions where to will be placed such that is placed in the first selected position, , is placed in the second position, , and so on. To avoid overcounting, we impose that there is no before , no between the position of and , and so on. Note that after , we are free to place any value we want.
For each chosen arrangement, how many ways are there to fill the remaining gaps? There are unfilled cells and there are values we can use to fill each position (except the segment from , which can accommodate until ). If we let , we can place .
If we loop over the values of from to , then:
Note that after we place the values in the last segment of length , we're left with an array of length in which the last element must be . That's why we can only choose integers.
This has a complexity of , provided you precalculate properly.
C# code to study:
No comments:
Post a Comment