Week 2 - Assignment 1 - CS103 - Swayam

Week 2 - Assignment 1

Problem Statement

You work at a popular thrift shop in Los Angeles where people donate various clothing items for the goodwill of the community. One day, you receive a large shipment of donations with multiple boxes. Each box contains a different number of clothing items. Your job at the store is to sort through these boxes and display them before your shift ends that day.

You have n hours left on your shift to end from the time you start sorting through these boxes. When you start sorting through one box and displaying them, should you finish your work before that hour ends, you take a coffee break until the next hour to break open the next box of clothing.

Given the donations array which logs the number of clothing items in each box, find a minimum rate of sorting k (in number of clothing items per hour) to sort all the items and display them before your shift ends.

Input Format

The first line of input consists of one integer t, which denotes the number of test cases.

Each test case has the following input:

Constraints

1 ≤ t ≤ 103

1 ≤ length ≤ 104

length ≤ n ≤ 109

1 ≤ donationsi ≤ 107

Output Format

For each test case, output one integer k denoting the smallest rate of sorting and displaying of the clothing items. Your code should run in a small amount of time even for big test cases.

Sample Input 1

Input:
2
7 5
4 3 6 8 9
5 3
23 19 15

Output:

6
23

Explanation

For the first testcase, you start sorting through the boxes. Let's say you choose a rate of sorting of the value 6 number of clothing items per hour. For the:

In total, you finish the sorting in 1+1+1+2+2=7 hours which is before the time your shift ends at. If you choose any other value lesser than 6 as the sorting rate, let's say 5, you will finish in 9 hours, hence not within your shift time.

Similarly, for the second testcase, 23 is the smallest rate of sorting and displaying of clothing items.

Solution

test_cases = int(input())

for _ in range(test_cases):
    # Read remaining hours and number of boxes
    remaining_hours, num_boxes = map(int, input().split())
    
    # Read the number of clothes in each box
    clothes_per_box = list(map(int, input().split()))
    
    # Calculate the total number of clothes
    total_clothes = sum(clothes_per_box)
    
    # Initialize binary search bounds
    min_rate = 1
    max_rate = total_clothes
    sorting_rate = max_rate
    
    # Binary search to find the minimum sorting rate
    while min_rate <= max_rate:
        mid_rate = (min_rate + max_rate) // 2
        # Calculate the time taken at the current mid_rate
        time_taken = sum((clothes + mid_rate - 1) // mid_rate for clothes in clothes_per_box)
        
        # Check if the time taken is within the remaining hours
        if time_taken <= remaining_hours:
            sorting_rate = mid_rate  # Update the optimal sorting rate
            max_rate = mid_rate - 1  # Search in the lower half
        else:
            min_rate = mid_rate + 1  # Search in the upper half
    
    # Print the optimal sorting rate for the current test case
    print(sorting_rate)

Sample Solution Provided by Instructor

import math

def thriftingClothes(donations, n):
    # 'l' is initialized to 1, representing the minimum possible value of 'k'.
    # 'r' is initialized to the maximum value in the 'donations' list, representing the maximum possible value of 'k'.
    l, r = 1, max(donations)
    
    # 'k' is initialized to 'r', as a starting guess for the maximum size of a group of clothes.
    k = r

    # Start a binary search to find the optimal value of 'k'.
    while l <= r:
        # 'mid' is the middle value between 'l' and 'r', representing a possible size for the group of clothes.
        mid = (l + r) // 2
        
        # 'totalTime' will accumulate the total time needed to process all donations, given the current 'mid' value.
        totalTime = 0
        
        # Calculate the total time needed for each donation with the current 'mid' value.
        for clothes in donations:
            # 'math.ceil(float(clothes) / mid)' calculates how many units of time it takes to process
            # 'clothes' items if each unit can process 'mid' items. This ensures we round up to the nearest whole unit.
            totalTime += math.ceil(float(clothes) / mid)
        
        # If the total time is less than or equal to 'n', it means the current 'mid' value is a valid candidate for 'k'.
        if totalTime <= n:
            # Update 'k' to the current 'mid' value, since it satisfies the condition.
            k = mid
            
            # Move the search range to the left (to find a potentially smaller valid 'k').
            r = mid - 1
        else:
            # If the total time exceeds 'n', we need a larger 'mid' value (i.e., we move the search range to the right).
            l = mid + 1
    
    # After exiting the loop, 'k' will contain the optimal value that meets the condition.
    return k

if __name__ == '__main__':
    # Read the number of test cases.
    tt = int(input())
    
    # Loop through each test case.
    for i in range(tt):
        # Read two integers: 'n' and 'length'.
        # 'n' is the maximum total time allowed to process all donations.
        # 'length' is the number of donation piles (unused in the function).
        n, length = [int(x) for x in input().split()]
        
        # Read the list of donations, which contains the number of clothes in each donation pile.
        donations = [int(x) for x in input().split()]
        
        # Call the 'thriftingClothes' function with the donations and the allowed time 'n', and print the result.
        print(thriftingClothes(donations, n))