Enlarging Enthusiasm
This problem gives us 12 point values, and wants us to add points to each of the 12 values such that
- the total number of points added sums to some x
- we add points to each value once, and the order we add them is from the SMALLEST number of points ADDED to the largest
- each time we add points, the new value is larger than any previous value
The end goal is to determine the number of different final orderings of the 12 values.
The first thing we realize is that we are limited to 11*11! final orderings, which we maybe could iterate over if we were fast enough. (450 million). These orderings must be determined by the order that we allocate points (since every subsequent value will be ahead in the final ordering)
Another thing to realize is it doesn't matter if we under-allocate points, since they can all be used up at the end without any issue. That means the only way one of the above given orderings is impossible is if we don't have enough points left.
That gives us two rules for every time we assign points:
- the number of points assigned must be at least 1 greater than the previous count of assigned points, or equal if the previously existing points increase.
- the points assigned plus the previously existing point values must be at least 1 greater than the best created in the previous assignment
Were we to try the most naive DP solution, we would have
- nodes remaining (2^12)
- value left to be allocated (700)
- value allocated last time (700)
- total sum from last time (700)
- note, from these, we can derive the previous value of the last time we allocated points, which may be necessary to break ties.
This is, of course, too large (1.4 trillion).
Can we think of an optimization, though?