PROBLEM LINK: Eat Code Sleep Repeat
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Greedy, DP, Recursion
PROBLEM:
Given D days , you have to choose one of the three activities on each day such that total Points you can make after D days is maximum. The only restriction is that we cannot do the Same activity on two consecutive days. For example, if we did activity A yesterday, we cannot do activity A today but we can do it tomorrow.
QUICK EXPLANATION:
Think of a way to consider all the possible cases and then try to optimize it.
EXPLANATION:
Subtask #1:
Since the constraints in this subtask are very low we can easily implement Brute Force solution using recursion to solve this problem.
We will start by doing one of the three activities on 1st day , then for the next day we have two options before us. For ex. if we did Activity A today, tomorrow we can do either Activity B or Activity C. Hence, we can use recursion to consider all the possible options. Our Answer in the end will be maximum of three values:
- Maximum points we gained by choosing Activity A on first day, P_A
- Maximum points we gained by choosing Activity B on first day, P_B
- Maximum points we gained by choosing Activity C on first day, P_C
Ans = max(P_A, P_B, P_C).
Time Complexity of this approach → T (3*2^D ).
In our recursive function we will have two recursive calls which adds the factor of 2D and since we call this function 3 times so total complexity is T (3*2^D ), which is more than enough to pass this subtask.
Subtask #2:
To solve this version of subtask we will have to use Dynamic programming.
we will maintain a 2D array, dp[n][3].
Where dp[i][j] = maximum points gained by performing jth activity on ith day.
dp[i][0] will store the maximum points we can gain by doing activity A on day i.
dp[i][1] will store the maximum points we can gain by doing activity B on day i.
dp[i][2] will store the maximum points we can gain by doing activity C on day i.
Our base cases will be:
// If you watch netflix on the first day, you cannot get more than x[0] points.
dp[0][0] = x[0];
// If you play counter strike on the first day, you cannot get more than y[0] points.
dp[0][1] = y[0];
// If you sleep on the first day, you cannot get more than z[0] points.
dp[0][2] = z[0];
For every day i, as we cannot do the activity we did on the previous day,
// If we do activity A today, we have to have done activities B or C on the previous day.
dp[i][0] = x[i] + max(dp[i - 1][1], dp[i - 1][2]);
// If we do activity B today, we have to have done activities A or C on the previous day.
dp[i][1] = y[i] + max(dp[i - 1][0], dp[i - 1][2]);
// If we do activity C today, we have to have done activities A or B on the previous day.
dp[i][2] = z[i] + max(dp[i - 1][1], dp[i - 1][0]);
Simply by checking for each day i, we can calculate the best we can do by the end of our last day.
As we can end by doing activities A, B, or C, our answer will be the maximum points gained on doing activities A, B, or C on the last day.
Time complexity: O(n)
SOLUTIONS:
For Subtask #1:
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 20;
ll activity[mxn][3], D;
ll cal(ll day, ll act)
{
if (day > D)
return 0;
if (act == 0)
return activity[day][act] + max(cal(day + 1, 1), cal(day + 1, 2));
else if (act == 1)
return activity[day][act] + max(cal(day + 1, 0), cal(day + 1, 2));
else
return activity[day][act] + max(cal(day + 1, 0), cal(day + 1, 1));
}
int main()
{
ll t = 1;
while (t--)
{
ll i, j, k, n, m;
cin >> D;
for (i = 1; i <= D; i++)
{
cin >> activity[i][0] >> activity[i][1] >> activity[i][2];
}
ll ans = max({cal(1, 0), cal(1, 1), cal(1, 2)});
cout << ans;
}
return 0;
}
For Subtask #2:
Editorialist's Solution
//Using Memoization Recursion
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 1e5 + 5;
ll activity[mxn][3], D;
ll dp[mxn][3];
ll cal(ll day, ll act)
{
if (day > D)
return 0;
if (dp[day][act] != -1)
return dp[day][act];
if (act == 0)
return dp[day][act] = activity[day][act] + max(cal(day + 1, 1), cal(day + 1, 2));
else if (act == 1)
return dp[day][act] = activity[day][act] + max(cal(day + 1, 0), cal(day + 1, 2));
else
return dp[day][act] = activity[day][act] + max(cal(day + 1, 0), cal(day + 1, 1));
}
int main()
{
ll t = 1;
while (t--)
{
ll i, j, k, n, m;
cin >> D;
memset(dp, -1, sizeof(dp));
for (i = 1; i <= D; i++)
{
cin >> activity[i][0] >> activity[i][1] >> activity[i][2];
}
ll ans = max({cal(1, 0), cal(1, 1), cal(1, 2)});
cout << ans;
}
return 0;
}
Editorialist's Solution
//DP Using Iterative Approach
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mxn = 1e5 + 5;
ll activity[mxn][3], D;
ll dp[mxn][3];
int main()
{
ll t = 1;
while (t--)
{
ll i, j, k, n, m;
cin >> D;
for (i = 1; i <= D; i++)
{
cin >> activity[i][0] >> activity[i][1] >> activity[i][2];
}
dp[1][0] = activity[1][0];
dp[1][1] = activity[1][1];
dp[1][2] = activity[1][2];
for (i = 2; i <= D; i++)
{
dp[i][0] = activity[i][0] + max(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = activity[i][1] + max(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = activity[i][2] + max(dp[i - 1][0], dp[i - 1][1]);
}
ll ans = max({dp[D][0], dp[D][1], dp[D][2]});
cout << ans;
}
return 0;
}