Problem : Garland
Hello ! I have read the editorial, but i’ve noticed people using 4-D Dynamic Programming to solve this problem. There was no explanation about the Dynamic Programming approach on this problem. Can someone explain me the Dynamic Programming approach for this problem.
A Couple of submissions using 4D DP (got them from the leaderboard)
Okay so I am also one of the people using 4D dp in this.
The dp is as follows:
dp[position][odd count][even count][parity].
Over here position means the current position.
Odd count means the number of odd numbers which we still have not yet used in the garland
Even count means the number of even numbers which we still have not yet used in the garland
Parity is the last used element in the garland – odd or even.
So basically,
dp[i][odd_cnt][even_cnt][parity] is used to compute the minimum parity obtained till the ith position, will odd_cnt of odd numbers left, even_cnt of even numbers left, and the last parity(odd or even).
So, it is dp[N][N][N][2], which equals O(N ^ 3), passing the test cases.
Okay I’m getting the idea. Can you share your submission which implements this?.. If you don’t have a problem of course 
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long a[n + 1];
map<long long, long long> freqA;
for(long long i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] != 0)
freqA[a[i]]++;
}
long long odd_cnt = 0, even_cnt = 0;
for(long long i = 1; i <= n; i += 2) {
if(!freqA.count(i))
odd_cnt++;
}
for(long long i = 2; i <= n; i += 2) {
if(!freqA.count(i))
even_cnt++;
}
//cout << odd_cnt << " " << even_cnt << endl;
long long dp[n + 1][odd_cnt + 1][even_cnt + 1][2];
for(long long i = 0; i <= n; i++) {
for(long long j = 0; j <= odd_cnt; j++) {
for(long long k = 0; k <= even_cnt; k++) {
dp[i][j][k][0] = dp[i][j][k][1] = 0;
}
}
}
for(long long i = 1; i <= n; i++) {
for(long long j = 0; j <= odd_cnt; j++) {
for(long long k = 0; k <= even_cnt; k++) {
if(a[i] != 0) {
if(a[i] % 2 == 0) { //even
dp[i][j][k][1] = INT_MAX; //odd not possible
dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1); //take even, odd + 1
}
else { //odd
dp[i][j][k][0] = INT_MAX; //even not possible
dp[i][j][k][1] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][0] + 1); //take odd, even + 1
}
}
else {
dp[i][j][k][0] = (k == 0) ? (INT_MAX) : (min(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][1] + 1));
dp[i][j][k][1] = (j == 0) ? (INT_MAX) : (min(dp[i - 1][j - 1][k][0] + 1, dp[i - 1][j - 1][k][1]));
}
}
}
}
/*for(long long i = 1; i <= n; i++) {
for(long long j = 0; j <= odd_cnt; j++) {
cout << dp[i][j][2][0] << " " << dp[i][j][2][1] << " ";
}
cout << endl;
}*/
cout << min(dp[n][odd_cnt][even_cnt][0], dp[n][odd_cnt][even_cnt][1]) << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const long long N = 101;
long long dp[N][N][N][2], a[N], vis[N], n;
void ini() {
for(long long i = 0; i < N; i++) {
vis[i] = 0;
for(long long j = 0; j < N; j++) {
for(long long k = 0; k < N; k++) {
dp[i][j][k][0] = -1;
dp[i][j][k][1] = -1;
}
}
}
}
long long Compute(long long pos, long long odd, long long even, long long last) {
if(pos > n)
return 0;
if(dp[pos][odd][even][last] != -1)
return dp[pos][odd][even][last];
dp[pos][odd][even][last] = INT_MAX;
if(a[pos] != 0) {
dp[pos][odd][even][last] = Compute(pos + 1, odd, even, a[pos] % 2);
if(last != a[pos] % 2)
dp[pos][odd][even][last]++;
}
else {
if(odd > 0) {
dp[pos][odd][even][last] = Compute(pos + 1, odd - 1, even, 1);
if(last == 0)
dp[pos][odd][even][last]++;
}
if(even > 0) {
if(last == 1)
dp[pos][odd][even][last] = min(dp[pos][odd][even][last], Compute(pos + 1, odd, even - 1, 0) + 1);
else
dp[pos][odd][even][last] = min(dp[pos][odd][even][last], Compute(pos + 1, odd, even - 1, 0));
}
}
return dp[pos][odd][even][last];
}
int main() {
cin >> n;
ini();
for(long long i = 1; i <= n; i++) {
cin >> a[i];
vis[a[i]] = 1;
}
long long odd_cnt = 0, even_cnt = 0;
for(long long i = 1; i <= n; i ++) {
if(vis[i] == 0) {
if(i & 1)
odd_cnt++;
else
even_cnt++;
}
}
//cout << odd_cnt << " " << even_cnt << endl;
long long ans1 = 0, ans2 = INT_MAX;
if(a[1] != 0) {
ans1 = Compute(2, odd_cnt, even_cnt, a[1] % 2);
}
else {
ans1 = Compute(2, odd_cnt - 1, even_cnt, 1);
ans2 = Compute(2, odd_cnt, even_cnt - 1, 0);
}
// cout << ans1 << " " << ans2 << endl;
/*for(long long i = 1; i <= n; i++) {
for(long long j = 0; j <= odd_cnt; j++) {
for(long long k = 0; k <= even_cnt; k++) {
cout << dp[i][j][k][0] << " " << dp[i][j][k][1] << endl;
}
cout << endl;
}
cout << endl;
}
cout << endl;*/
cout << min(ans1, ans2) << endl;
return 0;
}
Here you go, you may check both of them if you want 
Thanks a lot!