StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There's probably a way to analyze it analytically and come up with an O(1) solution. However, that will take someone much smarter than me to figure out :) Here is a dynamic-programming solution.</p> <p><em>I am assuming for this solution that all values must be positive. Further, I assume that all values in the sequence must be unequal to the prior value. Both of these conditions seem implied, but never explicitly stated, in the question.</em></p> <hr> <p>First, let's alter the problem slightly so that, in addition to <code>N</code>, <code>M</code>, <code>K</code>, and <code>L</code>, we are also given the value of the last term in the sequence, a<sub>n</sub>. Let's also add <em>yet another</em> variable <code>I</code>, which represents whether that last term was part of an increasing or decreasing sequence. Then we'll define a function <code>F</code> to return the number of possible sequences given <em>all</em> of those values.</p> <pre>N = number of values in sequence M = number of "runs" in the sequence K = max value allowed L = max difference between adjacent sequence terms I = whether the last term is increasing or decreasing a<sub>n</sub> = last term in the sequence F<sub>K,L</sub>(N,M,I,a<sub>n</sub>) = number of possible sequences, given all these values</pre> <p>Now if we had a way to calculate <code>F</code>, we could just sum over all possible values of a<sub>n</sub> <em>(from 1 to K)</em> and <code>I</code> to get the answer to your problem.</p> <hr> <p>Let's assume I = "increasing." We want to express <strong>F<sub>K,L</sub>(N,M,"increasing",a<sub>n</sub>)</strong> in terms of a "smaller" value of <code>F</code>, so we can recursively calculate values of <code>F</code> to obtain the final value. We'll do this by summing the value of <code>F</code> over all possible values of <strong>a<sub>n-1</sub></strong>; that is, we essentially say that <code>F</code> is equal to the number valid sequences of length <code>N-1</code> that <em>could</em> end in <strong>a<sub>n</sub></strong>, then we imagine appending <strong>a<sub>n</sub></strong> to each of them.</p> <p>Because we know <strong>a<sub>n</sub></strong> is part of an increasing sequence <em>(I = "increasing")</em>, we know that <strong>a<sub>n-1</sub> < a<sub>n</sub></strong> <em>(we'll get to the other case soon)</em>. We also know that <strong>a<sub>n-1</sub></strong> must be within <code>L</code> of <strong>a<sub>n-1</sub></strong>; thus <strong>max(1, a<sub>n</sub> - L) <= a<sub>n-1</sub> < a<sub>n</sub></strong>.</p> <p>We now have two cases to consider, depending on whether the previous term <strong>a<sub>n-1</sub></strong> was increasing or decreasing:</p> <ol> <li><strong>a<sub>n-1</sub></strong> was <em>increasing</em>. Then we are still increasing, so the value of <code>F</code> we're interested in is<br> <strong>F<sub>K,L</sub>(N-1,M,"increasing",a<sub>n-1</sub>)</strong>.</li> <li><strong>a<sub>n-1</sub></strong> was <em>decreasing</em>. <strong>a<sub>n</sub></strong> is now <em>increasing</em>, so there's now going to be one more "run" of values. Thus, the value of <code>F</code> we're interested in is<br> <strong>F<sub>K,L</sub>(N-1,M-1,"decreasing",a<sub>n-1</sub>)</strong>.</li> </ol> <p>We sum all these cases for all possible values of <strong>a<sub>n-1</sub></strong> to get the value of <strong>F<sub>K,L</sub>(N,M,"increasing",a<sub>n</sub>)</strong>. We can find <strong>F<sub>K,L</sub>(N,M,"decreasing",a<sub>n</sub>)</strong> in a similar manner, only we limit <strong>a<sub>n-1</sub></strong> to <strong>a<sub>n</sub> < a<sub>n-1</sub> <= min(K, a<sub>n</sub>+L)</strong>, and we subtract 1 from <code>M</code> in case #1 rather than case #2.</p> <hr> <p>Finally, we state the base cases. <strong>F<sub>K,L</sub>(N,M,I,a<sub>n</sub>): 0 if M < 1 or M > N; 1 if N = 1</strong>.</p> <p>Then, as I mentioned above, just sum over all values of <code>I</code> and <strong>a<sub>n</sub></strong> in <strong>F<sub>K,L</sub>(N,M,I,a<sub>n</sub>)</strong> to get the answer to your original problem. The runtime complexity is <code>O(KMN)</code></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