Problem : Find Sequence
Problem link: CodeChef: Practical coding for everyone
Difficulty : Hard
Prerequisites : DP, Greedy, Implementation
Problem :
To find time at which each vehicle will be ready for shipment
rules:
1 worker work in a sequence i.e. first the first worker then second and so on.
2 a worker cannot start on a vehicle until his previous work is done and the last worker is finished on the current vehicle.
Explanation :
Look at it as a scheduling problem where a task cannot begin until the previous task ends
Thus, an employee can start his work if the previous employee did his work and also he is free to do so
Creating a bottom-up approach for this question is ideal.
make a 2-d array that will store appropriate details about each vehicle and work done on it
Time complexity should be O(n*e) where n is number of vehicle and e is number of employees;
Thank you.
Solution :
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
void dev()
{
ll n, m;
cin >> n >> m;
vector<vector<ll>> arr(n, vector<ll>(m));
vector<vector<ll>> brr(n, vector<ll>(m));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < m; j++)
{
cin >> arr[i][j];
brr[i][j] = 0;
}
}
for (ll i = 0; i < n; i++)
{
if (i == 0)
{
brr[i][0] = arr[0][0];
}
else
{
brr[i][0] = brr[i - 1][0] + arr[i][0];
}
}
for (ll i = 1; i < m; i++)
{
brr[0][i] = brr[0][i - 1] + arr[0][i];
}
for (ll i = 1; i < n; i++)
{
for (ll j = 1; j < m; j++)
{
brr[i][j] = max((brr[i - 1][j] + arr[i][j]), (brr[i][j - 1] + arr[i][j]));
}
}
for (ll i = 0; i < n; i++)
{
cout << brr[i][m - 1] << " ";
}
cout<<"\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
cin >> t;
while (t--)
{
dev();
}
return 0;
}
Thank you