LT16-Editorial

Problem Link

Loop Through

Author:isag2008

Difficulty

Medium-Hard

Prerequisites

DP, Binary Search

Problem Statement

You are the head chef of a very popular 80s restaurant called Bennigan's. On one completely packed night, you have N dishes to serve and N cooks (including you) to prepare the dishes (each cook prepares 1 dish).
Only you have access to the recipes and you can read them before the customers arrive.
Not everyone knows the recipes beforehand, so to prepare a dish, a chef needs to be told the recipe. After knowing the recipes once, a chef is eligible to explain them to other chefs (one chef at a time). You can assume that the explaining (1 or N recipes) will always take D minutes. During explaining, none of the two involved chefs will be able to do anything else.

All the dishes take varying amounts of time to be prepared, it will take Ti time to prepare the ith
dish, regardless of who cooks it.

Given all the data, what is the minimum possible time required to prepare all the dishes.

Approach

The intended solution for this problem was O(N2) Dynamic Programming, although there exist better complexity solutions suitable for higher constraints.

At first, problems need to be sorted in non-increasing order of their solving time.

From each state i, j, where i is the number of contestants who knows the problem statement and j is the number of problems already solved, we have a few options.

If n-j (number of unsolved problems), is smaller to equal to i, then we have enough members able to solve one more problem and doing that will result in optimal time.

We can either explain the problem to as many new members as possible by spending D time.

Or, we can solve one problem in parallel. This can be calculated by comparing with the precalculated time of solving one more problem with one less member aware of statements (state i-1, j-1).

Solution

 #include <bits/stdc++.h>
 using namespace std;

 #define mx 3030
 long long dp[ mx ][ mx ];

 int main() {
     int test;
     cin >> test;
     while( test-- ) {
         int n, d;
         cin >> n >> d;

         vector<long long> a( n );

         for(int i = 0; i < n; i++) cin >> a[i];

         sort(a.begin(), a.end(), greater<long long>());

         memset(dp, 0, sizeof dp);

         for(int probC = n-1; probC >= 0; probC--) {
             for(int manC = n; manC >= 1; manC--) {
                 if( manC >= n - probC ) dp[ manC ][ probC ] = a[ probC ];
                 else {
                     dp[ manC ][ probC ] = d + dp[ min(n, manC<<1) ][ probC ];
                     if(manC > 1) {
                         long long C = max( a[ probC ] , dp[ manC-1 ][ probC+1 ]);
                         dp[ manC ][ probC ] = min( dp[ manC ][ probC ], C);
                     }
                 }
             }
         }
         cout << dp[ 1 ][ 0 ] << endl;
     }
     return 0;
 }