Minimum Time To Solve The Problems

We want to assign N number of subjects among K friends. So consider this as dividing the array into K partitions, where each partition denotes the subjects assigned to one of the friends. Assume that we already have K-1 partitions i.e. we have already assigned the subjects to K-1 friends, and now we want to do the K th partition. So, this last divider can be put between i th and i+1 th subject for 1<=i<=N-1. Note that, putting the divider before the first element is identical to putting it after the last element.

So, after the K th partition, the total time can be calculated as the maximum of below conditions:

1. The maximum time required among the already existing K-1 partitions.
2. The time required for the last partition i.e. sum of the array from subjects[i] to subjects[N-1] where the last divider is put before the index i.

Steps:

1. If the value of K is 1, then we simply return the sum of the array subjects.
2. If the value of N is 1, then we return subjects[0].
3. We create an ans variable and initialize it to 10^18 (Any value which is greater than the sum of the array).
4. Then, run a loop from 1 to N. Let’s denote the loop counter as i.
5. So, the total time required for this assignment can be calculated as the maximum of the below mentioned conditions:
   1. The time required for the last partition, i.e. K th partition is done after the last element. So, the time required is the sum of elements from i th element to the end of the array, where the k-1 th divider is before element i.
   2. The maximum time required for any partition that is already formed to the left of the k-1 th divider.
6. If the value calculated in the previous step is less than the ans, then update the ans to this variable.
7. Finally, return the ans variable.

In the previous approach, the algorithm recursively calculates and compares every possible partition at every possible element, which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems. To reiterate, memoization is when we store the results of all previously solved subproblems and return the minimum time required to solve the problems, from the dp[i][j] if we encounter the problem that has already been solved.

Since there are two states those are changing in the recursive function, i.e. N and K, so we use the 2-dimensional array dp[][] to store all the subproblems, where dp[i][j] will store the result from 0 to i th friend and from 0 to j th subject.

Another optimization that can be done is that, like in the previous approach, instead of calculating the sum of the array from subjects[i] to subjects[N-1] again and again, we can create a prefixSum array to store the prefix sum of the array subjects and get the sum from subjects[i] to subjects[N-1] in constant time.

Steps:

1. Create a prefixSum array of size N.
2. The steps to calculate the prefix sum:
   1. Initialize all the elements of this array to 0.
   2. Make the first element of the prefixSum array equal to the first element of subjects.
   3. Then run a loop from i = 1 to N and do:
      1. prefixSum[i] = prefixSum[i-1] + subjects[i].
3. Now, create a dp array of size (K+1 * N+1). Initialize the values in the dp array to -1.
4. Implement, and call the function minimumRequiredTimeUtil(subjects, N, K, dp, prefixSum).

minimumRequiredTimeUtil(subjects, N, K, dp, prefixSum):

1. If the value of K is 1, then we simply return prefixSum[N-1].
2. If the value of N is 1, then we return subjects[0].
3. If the value in the dp table is not -1, then we simply return that value.
4. Else, initialize an ans variable to 10^18, and run a loop from i = 1 to N and do:
   1. ans = min(ans, max(minimumRequiredTimeUtil(subjects, i, K-1, dp, prefixSum), prefixSum[n-1] - prefixSum[i-1]))
5. Finally, assign the ans to dp[K][N] and return the ans.

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. Here also, for each partition we have the choices to put the divider between the i th and i+1 th subject for 1 <= i <= N-1. So, with the outer loop running from i = 2 to K and the inner loop running from  j = 2 to N, we can use the recurrence relation of memoization approach as dp[i][j] = min(dp[i][j], max(dp[i-1][x], prefixSum[j-1] - prefixSum[x-1])) where 1 <= x <= j.

Steps:

1. Create a prefixSum array of size N.
2. The steps to calculate the prefix sum:
   1. Initialize all the elements of this array to 0.
   2. Make the first element of the prefixSum array equal to the first element of subjects.
   3. Then run a loop from i = 1 to N and do:
      1. prefixSum[i] = prefixSum[i-1] + subjects[i].
3. Create a dp array of size (K+1 * N+1). Initialize the values in the dp array to -1.
4. If the value of K is 1, then we simply return prefixSum[n-1].
5. If the value of N is 1, then we return subjects[0].
6. Run a loop from i = 1 to N and do:
   1. dp[1][i] = prefixSum[i-1]
7. Run another loop from i = 1 to K and do:
   1. dp[i][1] = subjects[0]
8. Run a nested loop with the outer loop running from i = 2 to K and the inner loop running from j = 2 to N and do:
   1. Initialize an ans variable to 10^18.
   2. Run another loop from x = 1 to j and do:
      1. ans = min(ans, max(dp[i-1][x], prefixSum[j-1] - prefixSum[x-1]))
   3. dp[i][j] = ans.
9. Finally, return dp[K][N].

The idea here is to perform the binary search. We know that the binary search can be performed if the following conditions hold.

1. The target value should lie in a particular range.
2. The search space is sorted.
3. After each iteration, the search space is reduced to half.

So, in order to perform a binary search, we need to detect a suitable search space first. For that, let’s find out the minimum possible value and the maximum possible value of the answer. We can safely assume the lowest possible value of the answer is 0 when the array is empty. However, the highest possible value occurs when the value of K = 1. In that case, the answer is the sum of all the elements in the array “subjects”. So, the highest possible value is the sum of the array “subjects”. So, the range of the search space is [0, the sum of the array subjects].

Now, let us consider that we have t number of friends, so as the value in the above range decreases, the value of t increases and vice-versa. So, by performing the binary search in the range [0, the sum of the array subjects], for each mid in the range, we check whether it is possible to do K partitions such that the answer is mid. We can do so by implementing another function, say, checker. If it is possible to do K partitions for this value of mid, that means we have enough friends to solve the problems in the given time i.e. mid, so we update the upper bound of the range to mid - 1 storing the answer as mid. If it is not possible to do K partitions, that means we do not have enough friends to solve the problems in the given time, so we update the lower bound of the range to mid+1.

Steps:

1. Initialize a sum variable to 0 and calculate the sum of the array.
2. If the value of K is 1, then we simply return the sum.
3. If the value of N is 1, then we return subjects[0].
4. Take two pointers left and right with left pointing to 0 and right to the sum. Create an ans variable and initialize it to the sum.
5. Now apply the binary search in the range from left to right. For this, run a loop while left <= right and do:
   1. Create a mid variable and mid = left + (right - left) / 2
   2. For each mid value, check whether it is possible to do K partitions with the answer as mid. For doing so, implement a function checker(subjects, N, K, mid).
   3. If it is possible to do so, then update right to mid-1 and ans to mid.
   4. Else, update left to mid+1.
6. Finally, return the ans variable.

bool checker(subjects, N, K, mid):

1. Create a temp variable and initialize it to mid and a count variable to 1.
2. Initialize a loop counter let’s say i to 0 and run the loop until i < N and do:
   1. If at any point count exceeds K, then simply return false. As it is not possible to do K partitions.
   2. If ith value of array subjects is greater than temp, then increment count by 1 and make temp equal to mid again.
   3. Else, decrement temp by i th value of subjects and increment i by 1.
3. Finally, return true if we get out of the loop.