Consider these three questions:
1- Find the number of sequences of length 𝐿 made of numbers from 1 to 𝑛, such that number 1 appeared at least one time in each substring of length 𝑛.
2- Find the number of sequences of length 𝐿 made of numbers from 1 to 𝑛, such that number 1 appeared at least one time in each substring of length 𝑘.
3- Find the number of sequences of length 𝐿 made of numbers from 1 to 𝑛, such that each number from [1,n] appeared at least one time in each substring of length 𝑘. For example, if 𝑛==𝑘 and 𝐿>=𝑛, the answer will be 𝑘!.
For each of these questions, I want a polynomial time solution( not exponential) that computes it. Moreover, I want to have a good estimation of the answer of each of them based on the input variables.
Soroush Vahidi
Approaches to tackle these questions.
1. Number of sequences of length L made of numbers from 1 to n, such that number 1 appeared at least one time in each substring of length n:
- **Polynomial-time solution**: One way to solve this problem in polynomial time is to use a dynamic programming approach. Let's define a function `f(L, n)` that represents the number of valid sequences of length L made of numbers from 1 to n, such that number 1 appears at least once in each substring of length n.
- **Recurrence relation**: We can express `f(L, n)` using the following recurrence relation:
- `f(L, n) = n * f(L-1, n) - (n-1) * f(L-n, n)` for L >= n, and `f(L, n) = n^L` for L < n.
- **Time complexity**: The time complexity of this solution is O(L*n).
- **Estimation of the answer**: A good estimation of `f(L, n)` can be obtained using the following formula:
- `f(L, n) ≈ n^L * (1 - (n-1)^(L-n+1) / n^(L-n+1))`.
2. Number of sequences of length L made of numbers from 1 to n, such that number 1 appeared at least one time in each substring of length k:
- **Polynomial-time solution**: Similar to the first problem, we can use a dynamic programming approach to solve this problem in polynomial time. Let's define a function `g(L, n, k)` that represents the number of valid sequences of length L made of numbers from 1 to n, such that number 1 appears at least once in each substring of length k.
- **Recurrence relation**: We can express `g(L, n, k)` using the following recurrence relation:
- `g(L, n, k) = n * g(L-1, n, k) - (n-1) * g(L-k, n, k)` for L >= k, and `g(L, n, k) = n^L` for L < k.
- **Time complexity**: The time complexity of this solution is O(L*n*k).
- **Estimation of the answer**: A good estimation of `g(L, n, k)` can be obtained using the following formula:
- `g(L, n, k) ≈ n^L * (1 - (n-1)^(L-k+1) / n^(L-k+1))`.
3. Number of sequences of length L made of numbers from 1 to n, such that each number from [1, n] appeared at least one time in each substring of length k:
- **Polynomial-time solution**: This problem can be solved using a combination of dynamic programming and combinatorial techniques. Let's define a function `h(L, n, k)` that represents the number of valid sequences of length L made of numbers from 1 to n, such that each number from [1, n] appears at least once in each substring of length k.
- **Recurrence relation**: We can express `h(L, n, k)` using the following recurrence relation:
- `h(L, n, k) = n * h(L-1, n, k) - (n-1) * h(L-1, n-1, k-1)` for L >= k, and `h(L, n, k) = n^L` for L < k.
- **Time complexity**: The time complexity of this solution is O(L*n).
- **Estimation of the answer**: A good estimation of `h(L, n, k)` can be obtained using the following formula:
- `h(L, n, k) ≈ n^L * (1 - (n-1)^(L-k+1) / n^(L-k+1))`.
These are high-level descriptions of the solutions
Hope it helps. Partial credit AI
- Badges
- Science topic