3494: Find-the-Minimum-Amount-of-Time-to-Brew-Potions
Medium

table of contents

For this question, I intend to iterate through each potion inside mana and iterate through each wizard inside skill to calculate the consequent time each wizard completes each potion by. Since, to calculate the completion times of each potion, we only need the completion times of the previous potion, we can afford to reduce the space complexity by making our dp matrix have a row size of 2.

int n = skill.size(), m = mana.size();
vector<vector<long long>> dp (2, vector<long long>(skill.size(), 0));

Now, the main part that I realised was is that, in the examples provided, each potion had a column denoting the start-time that the potion is worked on. If you remove the start-time from each row, then each row in dp is just a zero-initialised prefix sum array that you can easily calculate in one-pass.

For example:

Potion Number   Start time  Wizard 0 done by    Wizard 1 done by    Wizard 2 done by    Wizard 3 done by
0               0           5                   30                  40                  60
1               52          53                  58                  60                  64

After subtracting the start time from each done by time, we have:

Potion Number   Start time  Wizard 0 done by    Wizard 1 done by    Wizard 2 done by    Wizard 3 done by
0               0           5                   30                  40                  60
1               0           1                   6                   8                   12

where, we can see that:

Therefore, while we iterate through the array skill for each potion, we need to be able to calculate the potion’s respective start-time and increase it every time the consequent wizard is unable to handle the current potion using the recurrence relationship:

currStartTime += max((long long) 0, (prevStartTime + dp[0][j]) - (currStartTime + dp[1][j-1]));

Now, for the code, we first have to initialise the first row of values in dp:

dp[1][0] = mana[0] * skill[0];
for (int j = 1; j < n; ++j) {
    dp[1][j] = dp[1][j-1] + mana[0] * skill[j];
}

Then, combining all the previous logic, if we iterate through all the potions and wizards, we get:

long long prevStartTime = 0, currStartTime = 0;
for (int i = 1; i < m; ++i) {
    dp[0] = dp[1];                  // shift the "current" row into the "previous" row
    prevStartTime = currStartTime;  // shift the "current" time into the "previous" time
    currStartTime += dp[0][0];      // currStartTime will always be delayed by dp[0][0]
    dp[1][0] = mana[i] * skill[0];  // initialise the first value in the dp row

    for (int j = 1; j < n; ++j) {
        currStartTime += max((long long) 0, prevStartTime + dp[0][j] - currStartTime - dp[1][j-1]);
        dp[1][j] = dp[1][j-1] + mana[i] * skill[j];                                                 
    }
}

return currStartTime + dp.back().back();

code

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();
        vector<vector<long long>> dp (2, vector<long long>(skill.size(), 0));

        dp[1][0] = mana[0] * skill[0];
        for (int j = 1; j < n; ++j) {
            dp[1][j] = dp[1][j-1] + mana[0] * skill[j];
        }

        long long prevStartTime = 0, currStartTime = 0;
        for (int i = 1; i < m; ++i) {
            dp[0] = dp[1];
            prevStartTime = currStartTime;
            currStartTime += dp[0][0];
            dp[1][0] = mana[i] * skill[0];

            for (int j = 1; j < n; ++j) {
                currStartTime += max((long long) 0, prevStartTime + dp[0][j] - currStartTime - dp[1][j-1]);
                dp[1][j] = dp[1][j-1] + mana[i] * skill[j];
            }
        }

        return currStartTime + dp.back().back();
    }
};

complexity

time taken