We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Time Required to Eliminate Bacterial Strains

Number: 3814

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

We are given an array of positive integers (timeReq) where timeReq[i] is the number of time–units needed for a white blood cell (WBC) to eliminate the iᵗʰ bacterial strain and an integer splitTime which is the time–cost for a WBC to split into two. Initially there is only one WBC; however, each WBC can perform only one elimination. To get more “workers” you may split a WBC (taking splitTime time per split) so that the two children can work in parallel. Note that once a WBC “kills” a strain it becomes exhausted. The goal is to determine the minimum time T required so that by some schedule of splits and assignments every bacterial strain is eliminated. (The strains may be processed in any order.)

Key Insights

  • The only way to “parallelize” work is by splitting the lone cell; however, splitting increases the “age” (or level) of the cell so that it becomes less “fresh” for hard tasks.
  • For each bacterial strain that requires time r to eliminate, if the total available time is T then the WBC that eliminates it must have finished splitting by time ≤T – r.
  • Because every split takes splitTime units and each split increases the “level” of the cell by 1, we can associate a cell’s “level” L with the fact that it became available at time L·splitTime.
  • A cell that has never split remains at level 0. Also note that if a strain requires a long killing‐time then the “deadline” for a cell working on it is “tight” – i.e. it must come from a low level (few splits).
  • The problem (once T is “guessed”) reduces to the question: starting from one cell at level 0 and with an operation that “splits” a cell from level L into two cells at level L+1, can we “assign” to every bacterial strain a cell whose level does not exceed a threshold determined by T – r?
  • One may “upgrade” available cells via splitting. But note that splitting always “increases” the level so although it increases the total count (by turning 1 cell into 2) it “degrades” the quality (making cells unsuitable for strains with very tight deadlines).
  • Using a greedy strategy we “group” bacterial strains by the maximum allowed level for a cell that can be used for their elimination. Then a key observation is that if we start with one cell at level 0, then (by splitting) a cell at level current can be “upgraded” to level L at a multiplictive cost of 2^(L–current). In other words, if we have X cells at “level = current” then they can yield up to X·2^(L–current) cells at level L.
  • Finally, we use binary search over T. For each candidate T we compute, for every strain the maximum allowed “cell level” (floor((T – r)/splitTime)). Then we “simulate” (using an aggregated calculation) upgrading of our single cell so that we try to “match” the demands in order of increasing allowed level.

Space and Time Complexity

Time Complexity: O(n · log(maxTime))
 • n is the number of bacterial strains and maxTime (the high bound in binary search) is roughly (n–1)*splitTime + max(timeReq).
Space Complexity: O(n)
 • We store an array for timeReq and a grouping dictionary for the feasibility check.

Solution

We solve the problem by binary searching on the answer T. For each candidate T we “check feasibility” using the following idea.
For each bacterial strain with kill–time r, if T < r then T is too small. Otherwise, the cell that kills that strain must finish its splits by time ≤T – r. Since each split costs splitTime, the maximum number of splits (or “level”) permitted is allowed = floor((T – r) / splitTime).
Now, starting from one cell at level 0, an operation (a “split”) replaces one cell at level L by two cells at level L+1. In the ideal (but constrained) world the number of cells available “at or below” a given level L could be increased up to a factor of 2^(L) if we were to upgrade our sole cell (level 0) to level L; however, note that if we upgrade “aggressively” we lose the very low–level cell (which is required if a strain has a very tight deadline).
In our feasibility check we “group” the bacterial strains that require a cell with maximum allowed level L. Then we simulate “upgrading” our available cell count. We maintain two numbers:  curAvail: the current total number of cells (all considered to be at a “current level”)  current_min_level: the level of the available cells in curAvail.
When we face a group that requires allowed level L (with L ≥ current_min_level) we “upgrade” all available cells from current_min_level to level L at a cost of multiplying curAvail by 2^(L – current_min_level). Then if curAvail is at least the number of strains in that group, we “assign” cells (removing that many cells from curAvail) and then move on.
If at any point curAvail is insufficient, T is not feasible. Finally, we shrink the search space until we find the minimum T that is feasible.

Code Solutions

# Python solution with detailed line-by-line comments

def minTimeToEliminate(timeReq, splitTime):
    n = len(timeReq)
    # lower bound: cannot be less than the smallest kill time.
    lo = min(timeReq)
    # upper bound: in worst-case we do (n-1) splits and then the longest kill;
    # note that each strain must be handled by a unique cell.
    hi = max(timeReq) + (n - 1) * splitTime

    # Feasibility check: Given total time T, can we produce cells to eliminate all bacteria?
    def is_feasible(T):
        # For each strain, if T is less than its kill time, then T is too small.
        for r in timeReq:
            if T < r:
                return False

        # Group bacterial strains by the maximum allowed cell level.
        # For a strain with kill time r, allowed level = floor((T - r) / splitTime)
        groups = {}
        for r in timeReq:
            allowed = (T - r) // splitTime
            groups[allowed] = groups.get(allowed, 0) + 1

        # We process groups in order of increasing allowed level (the most “tight” deadlines first)
        # We start with one available cell at level 0.
        curAvail = 1
        current_min_level = 0

        # For each allowed level in sorted order:
        for level in sorted(groups.keys()):
            # Upgrade all available cells from the current level to the current allowed level.
            # Upgrading means performing additional splits. Each cell at lower level becomes
            # 2^(level - current_min_level) cells at level "level."
            upgrades = level - current_min_level
            # Multiply curAvail by 2^(upgrades)
            curAvail *= (1 << upgrades)  # using bit shift as 2^(upgrades)
            current_min_level = level

            # For the group at this allowed level, we need to assign groups[level] cells.
            if curAvail < groups[level]:
                return False  # Not enough cells available for these strains
            # Use (assign) that many cells (they are removed from available pool)
            curAvail -= groups[level]

        return True

    # Binary search for the minimum T that is feasible.
    ans = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

# Example usage:
if __name__ == '__main__':
    # Example 1:
    timeReq1 = [10, 4, 5]
    splitTime1 = 2
    print(minTimeToEliminate(timeReq1, splitTime1))  # Expected output: 12

    # Example 2:
    timeReq2 = [10, 4]
    splitTime2 = 5
    print(minTimeToEliminate(timeReq2, splitTime2))  # Expected output: 15
← Back to All Questions