1
$\begingroup$

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as:

  • $s_i < s_{i+2}$, for $1 \leq i \leq N-2$
  • $s_i < s_{i+3}$, for $1 \leq i \leq N-3$
  • $s_i \in \{1,\dots, N\}$

Given $N$, calculate all the possible sequences of length $N$ given above formula.

I have already come up with a solution in $\mathcal{O}(N^3)$, but that's too slow for $N=1000$. For my solution I used dynamic-programming, but I cannot come up with a recursion which would allow me a better complexity. As far as I've discussed it with others, there is a $\mathcal{O}(N^2)$ dynamic programming algorithm.

Example: For $N=3$ we have $9$ such sequences, i.e: 112, 113, 122, 123, 132, 133, 213, 223, 233

$\endgroup$
1
  • 5
    $\begingroup$ 1. What are the restrictions on the allowed values of each $s_i$? Can it be any arbitrary integer? Must it be restricted to be within some range, e.g., [1,N]? Please edit the question to specify this clearly. 2. I suggest you edit the question to show the recursion and dynamic programming algorithm you've come up with. 3. Also, can you share the source of this exercise/problem? $\endgroup$
    – D.W.
    Aug 12, 2016 at 17:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.