PROBLEM LINK:
Setter: Nishit Patel
Tester: Raj Tiwari
DIFFICULTY
Easy-Moderate
PROBLEM
Three brothers, Nishit, Raj and Neelansh, have started a part-time job wherein their employer has put forward certain unusual conditions.
- Employees can work only on weekdays and in a week, only one employee is allowed to work.
- Employees aren’t allowed to work for 2 consecutive weeks i.e. if, for instance, Nishit has worked in week 1, then he can’t work in week 2 but will be able to work in week 3.
- An employee can work for any number of weekdays in a week (maximum 5).
Since they have to also attend their college lectures, they have developed a schedule that depicts when they are available to work. Eg: Schedule: AAABC - This means that in week 1, A (Nishit) can work for only 3 weekdays while B (Raj) and C (Neelansh) can work for only 1 weekday so they have to decide which one of the three will work in week 1. (This example considers only a single week)
Since they are paid per diem (per day) and have separate wages, they need to develop a work schedule that is in accordance with the employer’s conditions and will also help them earn the maximum possible collective wage.
Can you help them find the maximum possible collective wage that they can earn?
EXPLANATION
The very first idea that comes to our mind is to select max combination (workable_days*wage) and let that brother work, but due to the condition 2nd condition this approach fails. The idea for the solution is to use a dynamic programming approach and create a 2D array to keep track of all options.
- dp[i][0] will store maximum wages we can collect if Nishit is working on the ith week.
- dp[i][1] will store maximum wages we can collect if Raj is working on the ith week.
- dp[i][2] will store maximum wages we can collect if Neelansh is working on the ith week.
Let’s salA, salB, salC denote per day salary of three brothers respectively and availA[i], availB[i], availC[i] represent the availability of brothers for the ith week. Then this will be the equation for filling values in dp table.
dp[i][0] = salA*availA[i] + max(dp[i-1][1], dp[i-1][2])
dp[i][1] = salB*availB[i] + max(dp[i-1][0], dp[i-1][2])
dp[i][2] = salC*availC[i] + max(dp[i-1][0], dp[i-1][1])
In the last week, any one of the three brothers can work, hence our answer will be maximum of dp[n][0], dp[n][1], dp[n][2].
TIME COMPLEXITY
The time complexity is O(N).
SOLUTIONS
Setter's Solution
//Author : Nishit Patel
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef double db;
typedef long long ll;
#define pb push_back
#define FAST cin.sync_with_stdio(0); cin.tie(0);
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define arep(i, a, n) for(int i = a; i <= (n); ++i)
#define drep(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef map<ll, ll> ml;
typedef unordered_map<ll, ll> hash;
#define deb_1(A) {cerr << "[" << #A << "] : " << A << endl;}
#define deb_2(A,B) {cerr << "[" << #A << "] : " << A << endl<< "[" << #B << "] : " << B << endl;}
#define deb_3(A,B,C) {cerr << "[" << #A << "] : " << A << endl<< "[" << #B << "] : " << B << endl\
<< "[" << #C << "] : " << C << endl;}
#define deb_4(A,B,C,D) {cerr << "[" << #A << "] : " << A << endl<< "[" << #B << "] : " << B << endl\
<< "[" << #C << "] : " << C << endl<< "[" << #D << "] : " << D << endl;}
#define deb_X(x,A,B,C,D,FUNC, ...) FUNC
#define deb(...) deb_X(,##__VA_ARGS__,\
deb_4(__VA_ARGS__),\
deb_3(__VA_ARGS__),\
deb_2(__VA_ARGS__),\
deb_1(__VA_ARGS__),\
)
ll max3(ll a,ll b,ll c)
{
if(a>b)
{
if(a>c)return a;
else return c;
}
else{
if(b>c) return b;
else return c;
}
}
int main() {
FAST
int t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll sal[3];
cin>>sal[0]>>sal[1]>>sal[2];
string s;
cin>>s;
vector<vector<ll> > data( (n)+1 , vector<ll> (3, 0));
ll dp[n+1][3];
memset(dp,0,sizeof(dp));
ll an=0,bn=0,cn=0;
rep(i,s.length())
{
if(i%5 == 0)
{
data[i/5][0] = an;
data[i/5][1] = bn;
data[i/5][2] = cn;
an=0;bn=0;cn=0;
}
if(s[i] == 'A')
{
an++;
}
else if(s[i] == 'B')
{
bn++;
}
else{
cn++;
}
}
data[n][0] = an;
data[n][1] = bn;
data[n][2] = cn;
arep(i,1,n)
{
dp[i][0] = sal[0]*data[i][0] + max(dp[i-1][1],dp[i-1][2]);
dp[i][1] = sal[1]*data[i][1] + max(dp[i-1][0],dp[i-1][2]);
dp[i][2] = sal[2]*data[i][2] + max(dp[i-1][0],dp[i-1][1]);
}
ll dp_ans = max3(dp[n][0],dp[n][1],dp[n][2]);
cout<<dp_ans<<endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int, int> pii;
#define endl "\n"
#define debug(val) printf("check%d\n", val)
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define FF first
#define SS second
#define ll long long
#define ull unsigned long long
#define FOR(i, j, k, in) for (int i = j; i < k; i += in)
#define forr(k) for (int i = 0; i < k; i += 1)
#define forrr(l) for (int j = 0; j < l; j += 1)
#define For(j, k) for (int i = j; i < k; i += 1)
#define MOD 1000000007
#define clr(val) memset(val, 0, sizeof(val))
#define what_is(x) cerr << #x << " is " << x << endl;
#define OJ \
freopen("./setter_files/input.txt", "r", stdin); \
freopen("./tester_files/output1.txt.", "w", stdout);
#define FIO \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
int main()
{
// clock_t tStart = clock();
FIO;
OJ;
ll t;
cin >> t;
while (t--)
{
ll n;
string s;
cin >> n;
ll w1, w2, w3;
cin >> w1 >> w2 >> w3;
cin >> s;
vector<vector<pair<ll, ll>>> dp(n + 1, vector<pair<ll, ll>>(3, {0, 0}));
for (ll i = 0; i < n; i++)
{
ll c1 = 0, c2 = 0, c3 = 0;
for (ll j = 5 * i; j < 5 * i + 5; j++)
{
if (s[j] == 'A')
c1++;
else if (s[j] == 'B')
c2++;
else
c3++;
}
if (i == 0)
{
dp[i][0].first = c1 * w1;
dp[i][1].first = c2 * w2;
dp[i][2].first = c3 * w3;
dp[i][0].second = max(dp[i][1].first, dp[i][2].first);
dp[i][1].second = max(dp[i][0].first, dp[i][2].first);
dp[i][2].second = max(dp[i][0].first, dp[i][1].first);
}
else
{
dp[i][0].first = c1 * w1 + dp[i - 1][0].second;
dp[i][1].first = c2 * w2 + dp[i - 1][1].second;
dp[i][2].first = c3 * w3 + dp[i - 1][2].second;
dp[i][0].second = max(dp[i][1].first, dp[i][2].first);
dp[i][1].second = max(dp[i][0].first, dp[i][2].first);
dp[i][2].second = max(dp[i][0].first, dp[i][1].first);
}
}
cout << max(dp[n - 1][0].second, max(dp[n - 1][1].second, dp[n - 1][2].second)) << endl;
}
// printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
return 0;
}