FastPrep
Problem · Dynamic Programming

Determine the Best Skipping Strategy

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A company operates numerous warehouses, with each warehouse i holding inventory[i] units of a particular product. You and your co-worker are responsible for dispatching these items to fulfill customer orders, following a specific process:

  • When dispatching from warehouse i, you begin by reducing the inventory of the i-th warehouse by dispatch1 units.
  • After your dispatch, your co-worker reduces the inventory by dispatch2 units.
  • This process repeats until the inventory of the i-th warehouse reaches zero or becomes negative (i.e., inventory[i] <= 0).
  • For every warehouse that is emptied during your dispatch (i.e., the inventory reaches zero or below on your turn), you and your co-worker collectively earn 1 credit.

Your co-worker has the option to skip their turn, but they can only do this a limited number of times in total, defined by skips (across all warehouses).

The two of you alternate turns until the warehouse is emptied, then move on to the next warehouse.

Your task is to determine the best strategy to maximize the total credits that both you and your co-worker can earn together. Return the maximum number of credits that can be obtained.

Function

maxPoints(inventory: int[], dispatch1: int, dispatch2: int, skips: int) → int

Complete the function maxPoints in the editor below.

maxPoints has the following parameters:

  • int[] inventory: an array of integers denoting the inventory level of each warehouse.
  • int dispatch1: an integer indicating your dispatch level per turn.
  • int dispatch2: an integer indicating your co-worker's dispatch level per turn.
  • int skips: an integer specifying the maximum number of times your co-worker can skip their turn.

Returns

int: the maximum number of credits both of you can achieve collectively.

Examples

Example 1

inventory = [10, 6, 12, 8, 15, 1]dispatch1 = 2dispatch2 = 3skips = 3return = 5
An optimal dispatch strategy is as follows:
1. Your co-worker skips 2 turns, allowing you to empty the inventory of the 1st warehouse (Inventory: 10 -> 8 -> 5 -> 3 -> 1 -> -1).
2. Your co-worker doesn't skip any turns, and you empty the inventory of the 2nd warehouse (Inventory: 6 -> 4 -> 1 -> -1).
3. Your co-worker doesn't skip any turns, and you empty the inventory of the 3rd warehouse (Inventory: 12 -> 10 -> 7 -> 5 -> 2 -> 0).
4. Your co-worker skips 1 turn, and you drain the inventory of the 4th warehouse (Inventory: 8 -> 6 -> 3 -> 1 -> -1).
5. Your co-worker doesn't skip any turns, and they empty the inventory of the 5th warehouse (Inventory: 15 -> 13 -> 10 -> 8 -> 5 -> 3 -> 0).
6. Your co-worker doesn't skip any turns, and you empty the inventory of the 6th warehouse (Inventory: 1 -> -1).
As a result, the 1st, 2nd, 3rd, 4th, and 6th warehouses were completely dispatched by you, and the two of you collectively earned 5 credits, which is the maximum possible in this scenario. Hence, the answer is 5.

Constraints

  • 1 <= n <= 10^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= dispatch1, dispatch2, skips <= 10^9

More Amazon problems

drafts saved locally
public int maxPoints(int[] inventory, int dispatch1, int dispatch2, int skips) {
  // write your code here
}
inventory[10, 6, 12, 8, 15, 1]
dispatch12
dispatch23
skips3
expected5
checking account