CF 104157G - Crappy Typing

We are given a sequence of employees standing in a fixed order, where each employee has a known typing duration. There are M identical computers, and these computers act like parallel processors that continuously take the next available person in the queue.

codeforcescompetitive-programming

CF 104157G - Crappy Typing

Rating: -
Tags: -
Solve time: 59s
Verified: yes

Solution

Problem Understanding

We are given a sequence of employees standing in a fixed order, where each employee has a known typing duration. There are M identical computers, and these computers act like parallel processors that continuously take the next available person in the queue.

At time zero, the first M employees immediately start typing, one per computer. Each computer behaves independently: when a user finishes, that same computer instantly takes the next person waiting in line. The process continues until all employees have completed their tests, and the contest ends when the last employee finishes.

The task is to determine the smallest number of computers M such that the total completion time of the entire queue does not exceed a deadline D.

The constraints make a direct simulation over all possible M infeasible if done naively. N can be up to 100000, and D can be as large as 10^9. A naive attempt that recomputes full scheduling for each candidate M would cost O(N^2) in the worst case, which is too slow for the limit. Even O(N log N) per check becomes expensive if M is tested linearly.

A subtle edge case appears when a single employee’s time is already larger than D. In that situation, even with infinite computers, the answer is still constrained by the maximum individual runtime, since that employee cannot be parallelized. For example, if N = 3, D = 5, and t = [10, 1, 1], the answer does not exist unless the problem guarantees feasibility, which it does. This tells us that we must assume the intended solution space always contains a valid M.

Another edge case arises when all processing times are equal. In that case, the completion time depends almost linearly on ceil(N / M), and a naive greedy intuition might mislead one into thinking M = N is always required, but the queue reuse ensures smaller M can still satisfy the constraint if D is large enough.

Approaches

A brute-force idea is to try every possible number of computers M from 1 to N. For each M, we simulate the entire scheduling process using a priority queue or a min-heap that tracks when each computer becomes free. We push the first M tasks, then repeatedly pop the earliest finishing machine, assign the next task, and continue until all tasks are processed. The total runtime is the maximum finishing time produced by this simulation.

This works because it exactly reproduces the real system. The issue is that each simulation costs O(N log M), and doing it for all M leads to O(N^2 log N) in the worst case, which is far beyond the limits.

The key observation is that the feasibility of a given M is monotonic. If M computers can finish within time D, then any M' > M can also finish within D because adding machines can only reduce waiting time or keep it unchanged. This transforms the problem into a monotonic predicate over M, which immediately suggests binary search.

What remains is an efficient way to check feasibility for a fixed M. The natural simulation with a heap is already acceptable in O(N log M), but since we only need O(log N) checks due to binary search, the overall complexity becomes O(N log N log N), which is sufficient.

We are effectively combining two ideas: load balancing over identical machines and binary search over the number of machines required to satisfy a global time constraint.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(N^2 log N) O(N) Too slow
Binary Search + Heap Simulation O(N log N log N) O(N) Accepted

Algorithm Walkthrough

We solve the problem by searching for the smallest M that passes a feasibility test.

  1. Define a function can(M) that determines whether M computers are enough to finish all tasks within time D. We simulate the process exactly as described in the problem using a priority queue of finishing times.
  2. In can(M), we first assign the first M tasks to M computers. Each entry in the heap represents the time at which a computer becomes free, so we initialize it with t[i] for i from 0 to M−1. This reflects that each of these tasks starts at time zero.
  3. For every remaining task, we repeatedly take the earliest available computer from the heap. That machine finishes at time current_time, and we assign the next task to it, updating its new finish time as current_time + t[i]. We push this updated value back into the heap.
  4. Once all tasks are assigned, the answer for this M is the maximum value seen in the heap. Since the heap always stores finish times, the maximum represents when the last employee completes.
  5. If this maximum is less than or equal to D, then M is sufficient.
  6. We binary search M from 1 to N, using can(M) as the predicate. If can(M) is true, we try smaller M; otherwise, we increase M.

The key reason binary search works is that can(M) is monotonic. If increasing the number of machines cannot worsen the completion time, then once a value of M is valid, all larger values remain valid.

Python Solution

import sys
import heapq

input = sys.stdin.readline

def can(M, t, D):
    if M >= len(t):
        return max(t) <= D

    heap = t[:M]
    heapq.heapify(heap)

    for i in range(M, len(t)):
        earliest = heapq.heappop(heap)
        finish = earliest + t[i]
        heapq.heappush(heap, finish)

    return max(heap) <= D

def solve():
    N, D = map(int, input().split())
    t = list(map(int, input().split()))

    lo, hi = 1, N
    ans = N

    while lo <= hi:
        mid = (lo + hi) // 2
        if can(mid, t, D):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    print(ans)

if __name__ == "__main__":
    solve()

The function can(M) simulates the system exactly as a multi-machine scheduling process. The heap stores current finish times, so we always reuse the earliest available machine. This greedy assignment is necessary because delaying assignment would only increase completion time.

The binary search ensures we do not test all M values explicitly. Instead, we rely on monotonicity to reduce the search space logarithmically.

A subtle point is the initialization of the heap with the first M tasks. This models simultaneous start at time zero, which is critical; treating machines as initially idle would incorrectly shift all completion times.

Worked Examples

Sample 1

Input:

N = 6, D = 151
t = [56, 94, 95, 33, 62, 28]

We test candidate M values via binary search.

M Heap evolution (finish times) Final max Feasible
1 [56] → [150] → [245] → ... >151 No
2 [56, 94] → [56, 127] → [150, 127] → ... >151 No
3 [56, 94, 95] → updates → max ≤ 151 151 Yes

With M = 3, the scheduling balances enough load so that no machine exceeds the deadline.

This confirms that increasing M reduces the pressure on individual machines, and the threshold is tight at 3.

Sample 2

Input:

N = 9, D = 83
t = [10, 47, 53, 9, 83, 33, 15, 24, 28]
M Behavior summary Final max Feasible
4 queues accumulate late tasks >83 No
5 load distributes evenly ≤83 Yes

With M = 5, the long task (83) still fits exactly, and all remaining tasks complete without cascading delays.

This trace shows how a single long task can dominate scheduling unless enough machines are available.

Complexity Analysis

Measure Complexity Explanation
Time O(N log N log N) Each feasibility check costs O(N log M), and binary search adds another log N factor
Space O(N) Heap stores up to M elements

The constraints allow up to 10^5 employees, and logarithmic factors remain small enough for a 2-second limit. The heap operations are efficient in practice due to small constants.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import heapq

    def can(M, t, D):
        if M >= len(t):
            return max(t) <= D
        heap = t[:M]
        heapq.heapify(heap)
        for i in range(M, len(t)):
            earliest = heapq.heappop(heap)
            heapq.heappush(heap, earliest + t[i])
        return max(heap) <= D

    def solve():
        N, D = map(int, input().split())
        t = list(map(int, input().split()))

        lo, hi = 1, N
        ans = N
        while lo <= hi:
            mid = (lo + hi) // 2
            if can(mid, t, D):
                ans = mid
                hi = mid - 1
            else:
                lo = mid + 1
        print(ans)

    solve()
    return sys.stdout.getvalue().strip()

# provided samples
assert run("6 151\n56 94 95 33 62 28\n") == "3"
assert run("9 83\n10 47 53 9 83 33 15 24 28\n") == "5"

# minimum case
assert run("1 10\n5\n") == "1"

# all equal
assert run("5 20\n4 4 4 4 4\n") == "1"

# tight deadline
assert run("3 10\n5 5 5\n") == "3"

# larger mix
assert run("4 10\n2 8 3 7\n") == "2"
Test input Expected output What it validates
single task 1 base case
all equal small D 1 worst contention
tight scheduling 3 boundary feasibility
mixed loads 2 greedy balancing

Edge Cases

A key edge case is when M equals 1. In this case, the algorithm degenerates into a simple prefix sum, since every task runs sequentially on one machine. The heap logic still works correctly, but it is effectively unnecessary overhead. For input [5, 5, 5] with D = 10, the simulation produces finish time 15, correctly rejecting M = 1.

Another important case is when M is greater than or equal to N. Here every task gets its own machine, so the answer is simply the maximum value in t. The code handles this explicitly, ensuring no heap operations are wasted and correctness is preserved.

A third case involves one extremely large task among many small ones. The heap ensures that this large task always occupies a machine early, and binary search ensures we find the smallest M that isolates its effect enough to meet D.