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
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
can u solve the same ques and send