tsvk's blog

Wave Generation
By tsvk, history, 3 months ago, In English

Recently I had been trying to solve a question :

I have come up with the following approach :

#include "bits/stdc++.h"
using namespace std;
const int MOD = 1000000007;
vector<int> getValidRep(const vector<int>& arr, int i, int m) {
    vector<int> vec;
    if (i == 0) {
        for (int i = 1; i <= m; i++) {
            if (i != arr[i + 1]) 
                vec.push_back(i);
        }
    } 
    else if (i == arr.size() - 1) {
        for (int i = 1; i <= m; i++) {
            if (i != arr[i - 1]) 
                vec.push_back(i);
        }
    } 
    else {
        for (int i = 1; i <= m; i++) {
            if (i != arr[i - 1] && i != arr[i + 1])
                vec.push_back(i);
        }
    }
    return vec;
}

int f(const vector<int>& arr, int n, int m) {
    int totWays = 1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == -1) {
            vector<int> vec = getValidRep(arr, i, m);
            totWays = (static_cast<long long>(totWays) * vec.size()) % MOD;
        }
    }
    return totWays;
}

int main() {
    int n = 5;
    vector<int> v(n);
    for(auto &it : v) cin>>it;
    int m = 5;
    cout << f(v, n, m) << endl; 
    return 0;
}

The thing is that , I cannot submit to test for the test cases as it was part of an OA and I can't find it on any online judge and I am not able to think of anythinf better. All kinds of inputs will be appreciated... Thanks

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you look closely you can see that the question can be essentially boiled down to this :

Count the number of ways to create a wave array of size $$$i$$$ where the last element is either a peak or a valley and the first element belongs to some range $$$[l_1,r_1]$$$ and last element belongs to some range $$$[l_2,r_2]$$$

For this we can create a dp array $$$dp[n][m][2]$$$ where
$$$dp[i][j][0]$$$ = Number of ways to create an array of size $$$i$$$ where last element is $$$j$$$ and it is a peak
$$$dp[i][j][1]$$$ = Number of ways to create an array of size $$$i$$$ where last element is $$$j$$$ and it is a valley
The transition functions will be:
$$$dp[i][j][0] = \sum_{k=1}^{j-1} dp[i-1][k][1]$$$
$$$dp[i][j][1] = \sum_{k=j+1}^{m} dp[i-1][k][0]$$$
You can compute the dp array in $$$O(nm)$$$ using prefix sum and can solve the subproblem using it

→ Reply