Question

Atlassian | OA | INTERN | Coding Questions and Solutions | 2023 | Set-13

Answer 1

images of ques

Answer 2

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);
}

Answer 3

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;

}

Answer 4

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;
    }