StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I would break the problem down as follows. The runs must alternate between increasing and decreasing, so the important numbers are where the direction turns around. For the example above, the important numbers are <code>1 - 7 - 2 - 4 - 2</code> as marked below:</p> <pre><code>(1,2,3,4,7,6,5,2,3,4,1,2) x x x x x x </code></pre> <p>Suppose you already have given the positions and values of these turning points, e.g. you have</p> <pre><code>(1,7,2,4,1,2) </code></pre> <p>Then we want to count the number of ways to pad in between numbers. This depends only on <code>N</code> and <code>L</code> because we're already using the constraints from <code>K</code> and <code>M</code> to make that skeleton. The rule here is that the missing numbers are monotone between the given numbers and don't jump by more than <code>L</code>. That's an easy counting problem (details to come later).</p> <p>Next count the number of skeletons, which depends only on <code>K</code> and <code>M</code> (the count for filling them out might be 0 based on <code>N</code> and <code>L</code>). What do we know about these? Without the gaps, this has to be an alternating sequence (up-down-up-down) of length <code>M+1</code> with values between <code>1</code> and <code>K</code>. Again, this is <a href="http://en.wikipedia.org/wiki/Alternating_permutation" rel="nofollow">well studied</a> and not hard to count.</p> <p>The only hesitation that I have for this approach is that there isn't an easy way to combine these two counts, so it won't give a clean formula. However, it's still a great improvement over enumerating solutions exhaustively, and perhaps the idea can be improved further to give a closed or cleanly recursive formula.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload