Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,206 views
in Online Assessments by Expert (46,090 points) | 1,206 views

4 Answers

0 like 0 dislike
Best answer

images of ques
image
image
image

by Expert (46,090 points)
0 like 0 dislike
const int mod = 1e9 + 7;
int cache[100005][202][2][4];

int dp(int i, int lst, int peak, vector<int> &a, int tot) {
  if (i == a.size()) return peak and tot >= 3;
  int &res = cache[i][lst][peak][tot];
  if (res != -1) return res;
  res = dp(i + 1, lst, peak, a, tot);
  if (a[i] < lst and tot >= 2) {
    res = (res + dp(i + 1, a[i], 1, a, min(3, tot + 1))) % mod;
  }
  if ((!peak) and a[i] > lst) {
    res = (res + dp(i + 1, a[i], peak, a, min(3, tot + 1))) % mod;
  }
  return res;
}

int countBiotonicSeqeunces(vector <int> a) {
  memset(cache, -1, sizeof cache);
  return dp(0, 0, 0, a, 0);
}
by Expert (46,090 points)
0 like 0 dislike
int dp[maxn][201][3];

 

int recur(int i, int j, int k, vi &v)

{

if (i == size(v))

return (k == 1);

if (dp[i][j][k] != -1)

return dp[i][j][k];

int &ans = dp[i][j][k] = recur(i + 1, j, k, v);

if ((k == 0 and v[i] > j) or (k == 1 and v[i] < j))

{

ans = (ans + recur(i + 1, v[i], k, v)) % mod;

if (k == 0 and j)

ans = (ans + recur(i + 1, v[i], 2, v)) % mod;

}

if (k == 2 and v[i] < j)

ans = (ans + recur(i + 1, v[i], 1, v)) % mod;

return ans;

}

 

void solve()

{

int n;

cin >> n;

vi v(n);

cin >> v;

MEM(dp, -1);

cout << recur(0, 0, 0, v) << endl;

}
by Expert (46,090 points)
0 like 0 dislike

Q4 (Bottom-Up DP - Java)

 

Let dp[i][j][k] be the number of strictly increasing subsequence currently up to index i that end with j, withk = 0 -> len = 1, k = 1 -> len >= 2.
We can then generate all the strictly increasing subsequence with DP forward from left to right.
Then, we do another pass backward that does the same thing above, except this time we only need a dp2 of dp2[201].

 

I tested my code against the other 2 people's solutions (@coderdhanraj && @Aman_j1) in this comment.
All 3 solutions produce the same results for the random testcases I generated (so all 3 solutions should be correct or all incorrect).
The constraint is tight for this problem, so I think bottom-up DP is more preferable because it runs faster than top-down.

 

Java

 

Time O(400N)
Space O(400N)

 

    private static int solve(int[] A){
        int n = A.length, M = (int)1e9+7, ans = 0;
        int[][][] dp = new int[n][201][2];
        int[] dp2 = new int[201];
        for (int i = 0; i < n; i++){ // forward 
            for (int j = 0; j <= 200 && i > 0; j++){
                dp[i][j][0] = dp[i-1][j][0];
                dp[i][j][1] = dp[i-1][j][1];
            }
            dp[i][A[i]][0]++;
            for (int j = 0; j < A[i] && i > 0; j++){
                dp[i][A[i]][1] += (dp[i-1][j][0] + dp[i-1][j][1]) % M;
                dp[i][A[i]][1] %= M;
            }
        }
        for (int i = n-1; i > 0; i--){ // backward
            int take = 1;
            dp2[A[i]]++;
            for (int j = 0; j < A[i] && i < n-1; j++){
                dp2[A[i]] += dp2[j];
                take      += dp2[j];
                dp2[A[i]] %= M;
                take      %= M;
            }
            for (int j = A[i]+1; j <= 200; j++){
                ans += 1L * take * dp[i-1][j][1] % M;
            }
        }
        return ans;
    }
by Expert (46,090 points)