Help me solving this problem

general
1

Problem Statement

In the era of food delivery apps, the popularity of food delivery has increased significantly, leading restaurants to establish specific processes for food pickup by delivery drivers (shippers). However, in one particular restaurant, they have a peculiar procedure:

There are N shippers standing in a line, numbered from 0 to N-1. Shipper number i needs to purchase fi items of food. Shippers purchase items in sequence starting from shipper 0. Each shipper can buy only 1 item per turn, then moves to the end of the line, allowing the next shipper to take their turn.

A shipper leaves the line once they have purchased all the items they require. Determine how many rounds it will take for shipper K to purchase all their required items.

Input:

  • The first line contains two integers N and K (1 <= N <= 106, 0 <= K <= N-1), where N is the number of shippers and K is the shipper of interest.
  • The second line contains N integers, where the i-th integer fi (1 <= fi <= 106) represents the number of items shipper i needs to purchase.

Output:

  • Output a single integer, the number of rounds it will take for shipper K to purchase all their required items.

Subtasks:

  • Subtask 1 (50% points): The sum of all fi values does not exceed 108.
  • Subtask 2: No additional constraints.

Examples:
Input 1:

4 1 1 2 3 4

Output 1:

1

Input 2:

7 4 9 6 9 2 8 2 3

Output 2:

37

2

Why, For the Input 1: 4 1 1 2 3 4
Output 1: 1
I am not able to understand this.,
baaki
This question seems to be based on round-robin. Using a queue might be a simple approach to the problem.
Otherwise, wise approach would be toh sum up all values :-
min(kth value , ith value) upto k and min(kth -1 , ith value) after k in the for all values in the array, ex in 9 6 9 2 8 2 3 ,
its 8+6+8+2+8+2+3 =37

3

Can you provide me the link of the question, it will help to understand question better.

4

Oh sorry with Input 1: 4 1 1 2 3 4 . The correct Output is: 5

5

Steps:

  1. Initialize the queue with each shipper’s index and the number of items they need.
  2. Initialize a counter to track the number of rounds.
  3. Process each shipper:
  • Each shipper buys one item per turn.
  • If shipper K completes their purchases, output the current round count and stop.
  • Otherwise, move the shipper to the back of the queue if they still have items to buy.
  1. Continue this process until shipper K is done.Preformatted text
def rounds_to_complete(N, K, items):
    queue = [(i, items[i]) for i in range(N)]
    rounds = 0
    
    while queue:
        index, remaining_items = queue.pop(0)
        rounds += 1
        remaining_items -= 1
        
        if index == K and remaining_items == 0:
            return rounds
        
        if remaining_items > 0:
            queue.append((index, remaining_items))
    
    return rounds

result = rounds_to_complete(7, 4, [9, 6, 9, 2, 8, 2, 3])
print(result)
#output = 37

Step-by-Step for the Given Example

  • N=7,
  • K=4,
  • Items required by each shipper: [9, 6, 9, 2, 8, 2, 3]

Initial Queue State:

  • Queue: [(0,9),(1,6),(2,9),(3,2),(4,8),(5,2),(6,3)]

queue is like key-value pairs with index which is also shipper i and items shipper i need to be done.

in our case, shipper i = shipper k = 4, and it has 9 items to collect.

our loop starts for every shipper 0 to upto n-1(which is 6 inclusive) in our case.

Processing Steps:

  1. Round 1: Process shipper 0: [(1,6),(2,9),(3,2),(4,8),(5,2),(6,3),(0,8)]

Here, shipper 0 had 9 items intially, it take one item, and go back the end of line. now now he has 8 items.(note: always consider those index number as shipper number. we can only take one item each time)round +=1, and shipper 0 items -=1(which is (9-1=8)

  1. Round 2: Process shipper 1: [(2,9),(3,2),(4,8),(5,2),(6,3),(0,8),(1,5)]
  2. Round 3: Process shipper 2: [(3,2),(4,8),(5,2),(6,3),(0,8),(1,5),(2,8)]
  3. Round 4: Process shipper 3: [(4,8),(5,2),(6,3),(0,8),(1,5),(2,8),(3,1)]
  4. Round 5: Process shipper 4: [(5,2),(6,3),(0,8),(1,5),(2,8),(3,1),(4,7)] (our shipper whose items needs to 0 to end rounds;
  5. Round 6: Process shipper 5: [(6,3),(0,8),(1,5),(2,8),(3,1),(4,7),(5,1)]
  6. Round 7: Process shipper 6: [(0,8),(1,5),(2,8),(3,1),(4,7),(5,1),(6,2)]
    again loop reiterates, do the same operations until the shipper 4 has 0 items.