PROBLEM LINK:
Author - xenon_shivam
tester - imranasuman
DIFFICULTY:
MEDIUM.
PREREQUISITES:
DP, Math.
PROBLEM:
There are two type of bacterias X and Y. X will always reproduce and Y can’t. Given a string consist of X and Y only, task is to guess the all possible valid generations of bacteria. Bacteria can also come on the slit from an external source.
EXPLANATION:
This problem can be solved using dynamic programming.
First thing that is very clear, if a string ends with bacteria X at it last then it is considered to be a wrong data set and you have to print -1 for that.
Now, let’s consider all possible generations which end with a certain type of bacteria at a certain depth from its root. Dynamic programming state will be an array dp [ i ][ j ] which stores the number of such generations ending with bacteria i at depth j .
The starting state is a one-dimensional array for i = 0. There is exactly one generation which consists of the first bacteria only, and its last bacteria has depth 0. Depth 0 refers that it is a bacteria from an external source.
The recurrent formula can be figured out from the description of the statements. When we add bacteria i + 1, its possible depths depend on the possible depths of bacteria i and on the type of bacteria (X or Y) i . If bacteria i is a X, bacteria i + 1 must have depth one greater than the depth of bacteria i , so dp [ i + 1][0] = 0 and dp [ i + 1][ j ] = dp [ i ][ j - 1] for j > 0. If bacteria i is a Y, bacteria i + 1 can belong to the family of any X before it, and have any depth from 0 to the depth of bacteria i . If we denote the depth of bacteria i (type Y) as k , the depth of bacteria i + 1 as j , we need to sum over all cases where k ≥ j :
dp[i+1][j] = Summation of k (from j to N-1) dp[i][k]
The answer to the task is the total number of generations which end with the last bacteria (Y of course)at any depth: Summation of k (from 0 to N-1) dp[N-1][k]
The complexity of this solution is O ( N^2).
SOLUTIONS:
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int mod = 1000000007;
void solve() {
ll n, i, j, m, q, type, l, r, x, k;
string s;
cin >> s;
n = s.size();
if (s[n - 1] == ‘X’) {
cout << -1 << “\n”;
return;
}
vector<vector> dp(n + 5, vector(n + 5, 0)), S(n + 5, vector(n + 5, 0));
dp[0][0] = 1;
for (i = 1; i <= n; i++) {
for (j = n; j >= 0; --j) {
S[i - 1][j] = S[i - 1][j + 1] + dp[i - 1][j];
S[i - 1][j] %= mod;
}
for (j = 0; j <= n; j++) {
if (j > 0 && s[i - 1] == ‘X’) {
dp[i][j] = dp[i - 1][j - 1];
} else {
if (s[i - 1] == ‘X’)
continue;
dp[i][j] = S[i - 1][j];
}
}
}
cout << dp[n][0] << "\n";
}
bool imp = true;
int main() {
fio;
int t = 1;
if (imp)cin >> t;
int m = t;
while (t–) {
solve();
}
return 0;
}