Week 2 - Assignment 2 - CS103 - Swayam

Week 2 - Assignment 2

Problem Statement

Imagine that you own a bookstore in downtown New York. Your shop sells a diverse range of books, of various popularity rankings. You sell New York bestsellers as well as less popular titles. Each of these rankings is published at the end of each week by an autonomous organization. Lower rankings indicate more popular books, while higher rankings signify less popular ones.

One day you receive a large shipment of books. You realize that sorting these books in order of their popularity will boost sales and enhance the customer experience. However, the number of books n is really large for you to handle alone. To make this process of sorting easier, you decide to hire workers. Money is no problem for you, so you can hire as many workers as needed.

Let's say you hire workers and split the book shipment into segments amongst the workers where each worker can get a different sized segment. Each of the workers sorts their books independently according to the popularity ranking.

What is the most number of workers you will hire such that at the end of the day, all your books are sorted by popularity ranking?

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 ≤ 100

1 ≤ n ≤ 20000

0 ≤ book_shipments[i] ≤ 108

Output Format

For each test case, output one integer denoting the most number of workers you can hire such that your books are sorted by popularity ranking once the sorting process is over.

Sample Input 1

Input:
1
5
2 1 3 4 4

Output:

4

Explanation

When you receive the book shipment with book popularity rankings 2, 1, 3, 4, 4; if you hire 4 workers and distribute the book segments in the following way and they sort accordingly:

Then the entire set of books will be sorted by popularity at the end of it.

Solution

# Read the number of test cases
t = int(input())

for _ in range(t):
    # Read the number of elements
    n = int(input())
    # Read the list of elements
    a = list(map(int, input().split()))
    
    # Create a sorted version of the list
    asorted = sorted(a)
    
    # Initialize the maximum number of workers needed
    max_workers = 0
    # Initialize the current maximum element found
    current_max = -1

    # Iterate through the list of elements
    for i in range(n):
        # Update the current maximum element found
        current_max = max(current_max, a[i])
        # Check if the current maximum element matches the sorted element at the same position
        if current_max == asorted[i]:
            # Increment the number of workers needed
            max_workers += 1
            # Reset the current maximum element
            current_max = -1
    
    # Print the maximum number of workers needed for the current test case
    print(max_workers)

Sample Solution Provided by Instructor

def workersBookStore(book_shipments, n):
    # Initialize a list 'minimum' with n elements, all set to 0.
    # This will store the minimum values from the right to the current index.
    minimum = [0] * n
    
    # Set the last element of 'minimum' to the last element of 'book_shipments'.
    # This is because the minimum value from the last element to itself is the element itself.
    minimum[-1] = book_shipments[-1]
    
    # Iterate backwards through 'book_shipments' starting from the second last element.
    for i in range(n - 2, -1, -1):
        # For each element, store the minimum value between the current element
        # and the minimum of all elements to its right.
        minimum[i] = min(minimum[i + 1], book_shipments[i])
    
    # Initialize 'segments' to 1. This variable will count the number of segments 
    # that can be created where each segment satisfies the condition:
    # All elements in a segment should be less than or equal to all elements in the next segment.
    segments = 1
    
    # Initialize 'maximum' to the first element of 'book_shipments'.
    # This will keep track of the maximum value in the current segment.
    maximum = book_shipments[0]
    
    # Iterate through the list up to the second last element.
    for i in range(n - 1):
        # Update 'maximum' to be the largest value found so far in the current segment.
        maximum = max(maximum, book_shipments[i])
        
        # Check if the maximum value in the current segment is less than or equal to 
        # the minimum value of the next segment.
        if maximum <= minimum[i + 1]:
            # If the condition is satisfied, it means we can end the current segment here
            # and start a new segment. Increment the 'segments' counter.
            segments += 1
    
    # Return the total number of valid segments.
    return segments

if __name__ == '__main__':
    # Read the number of test cases.
    tt = int(input())
    
    # Loop through each test case.
    for i in range(tt):
        # Read the number of book shipments (the size of the list).
        n = int(input())
        
        # Read the list of book shipments and convert them into a list of integers.
        book_shipments = [int(x) for x in input().split()]
        
        # Call the 'workersBookStore' function with the shipments and their count, and print the result.
        print(workersBookStore(book_shipments, n))