Maximum Credits from Warehouse Dispatch

Maximum Credits from Warehouse Dispatch

Note: This is a reconstructed version of an Amazon online assessment problem based on publicly shared descriptions. Wording and examples may differ slightly from the original.

---

Problem Description

There are $$n$$ warehouses, each with an initial inventory of items. You and your co‑worker take turns dispatching items from one warehouse at a time.

For every dispatch “round” on a warehouse:

• First, you dispatch exactly dispatch1 units from the current warehouse (if it has at least that many; otherwise you just remove whatever remains).
• Then, your co‑worker dispatches exactly dispatch2 units from the same warehouse (or whatever remains), unless they choose to skip their turn.

Your co‑worker is allowed to skip their own turn at most skips times in total across all warehouses.
When your co‑worker skips their turn on a warehouse, that turn is consumed from the global skips budget, and you immediately take the next dispatch turn on that same warehouse (again removing dispatch1 units).

For each warehouse:

• Dispatching continues on that warehouse (alternating you → co‑worker → you → …, with optional co‑worker skips) until its inventory becomes empty or negative.
• A warehouse yields exactly one credit if and only if it becomes empty (inventory $$\le 0$$) immediately after one of your dispatches.
• If the warehouse is emptied by your co‑worker’s dispatch, no credit is earned from that warehouse.

You may process the warehouses in any order and choose optimally on which co‑worker turns to use skips in order to maximize the total credits.

Compute the maximum total number of credits you can earn over all warehouses.

---

Input/Output Format

Assume you are given the following function to implement:

text int getMaximumCredits(int[] inventory, int dispatch1, int dispatch2, int skips)

• Input

  • inventory: array of length n
    • inventory[i] (integer) is the initial inventory of the $$i$$-th warehouse.
  • dispatch1: integer, the number of units you dispatch on each of your turns.
  • dispatch2: integer, the number of units your co‑worker dispatches on each of their turns (when they do not skip).
  • skips: integer, the maximum total number of times your co‑worker may skip their own turn across all warehouses.

• Output

  • Return an integer:
    • the maximum number of credits you can earn in total, assuming optimal use of the skips budget.

Data types are standard 32‑bit (or 64‑bit where necessary) signed integers.

---

Examples

Example 1

Input

text inventory = [5, 13, 22, 11] dispatch1 = 4 dispatch2 = 7 skips = 3

Output

text 3

Explanation

Let $$A = \text{dispatch1} = 4$$, $$B = \text{dispatch2} = 7$$, and a full round (you + co‑worker) removes $$A + B = 11$$ units, called a cycle.

Process each warehouse:

1. Warehouse 0: inventory = 5

   • If you dispatch normally:
     • Your turn: $$5 - 4 = 1$$ (not empty).
     • Co‑worker’s turn: $$1 - 7 = -6$$ → warehouse empty after co‑worker, so no credit.
   • If you spend 1 skip on the co‑worker’s first turn:
     • Your turn: $$5 - 4 = 1$$.
     • Co‑worker’s turn is skipped (skips becomes 2), you go again:
     • Your next turn: $$1 - 4 = -3$$ → warehouse empty after your dispatch, you earn 1 credit.
   • Minimum skips needed here to get a credit: 1.

2. Warehouse 1: inventory = 13

   • Consider full cycles of 11: $$13 = 11 + 2$$.
   • After 1 full cycle (you then co‑worker), 11 units are removed, 2 remain.
   • Now continue without any skips:
     • Your turn on the remainder: $$2 - 4 = -2$$ → warehouse empty after your dispatch.
   • You get 1 credit here without using any skips.

3. Warehouse 2: inventory = 22

   • $$22$$ is exactly 2 full cycles of 11. Equivalently, treat remainder as 11.
   • With normal play:
     • Over the last partial “cycle” of 11 units, your co‑worker empties the warehouse, so no credit.
   • To ensure you are the one to empty those last 11 units, you need:
     • $$y = \lceil 11 / A \rceil = \lceil 11 / 4 \rceil = 3$$ of your turns on that remainder,
     • which requires $$y - 1 = 2$$ co‑worker skips on that warehouse.
   • Minimum skips needed here to get a credit: 2.

4. Warehouse 3: inventory = 11

   • This is the same remainder case as above (11).
   • Again, without skips, the co‑worker empties it; to flip it so that you empty it, you need 2 skips.

Now, summarize:

• Warehouses needing 0 skips for a credit:
  • Warehouse 1 → 1 credit, cost 0 skips.
• Warehouses needing 1 skip for a credit:
  • Warehouse 0.
• Warehouses needing 2 skips for a credit:
  • Warehouses 2 and 3.

You have skips = 3. Use them optimally:

• Take the free credit from warehouse 1 → credits = 1, skips used = 0.
• Next, take the warehouse needing 1 skip (warehouse 0):
  credits = 2, skips used = 1.
• Remaining skips = 2. You can afford one of the warehouses that need 2 skips (either 2 or 3):
  credits = 3, skips used = 3.
• You cannot afford the remaining 2‑skip warehouse.

Maximum total credits = 3.

---

Example 2

Input

text inventory = [5, 8, 9] dispatch1 = 3 dispatch2 = 5 skips = 2

Output

text 2

Explanation

Let $$A = 3$$, $$B = 5$$, so a full cycle removes $$A + B = 8$$ units.

1. Warehouse 0: inventory = 5

   • Normal play:
     • Your turn: $$5 - 3 = 2$$.
     • Co‑worker: $$2 - 5 = -3$$ → co‑worker empties; no credit.
   • If you use 1 skip on the co‑worker’s first turn:
     • Your turn: $$5 - 3 = 2$$.
     • Co‑worker’s turn skipped (skips from 2 to 1), you act again:
     • Your next turn: $$2 - 3 = -1$$ → you empty the warehouse → 1 credit.
   • Minimum skips for a credit: 1.

2. Warehouse 1: inventory = 8

   • Normal play:
     • Your turn: $$8 - 3 = 5$$.
     • Co‑worker: $$5 - 5 = 0$$ → co‑worker empties; no credit.
   • To make you empty it:
     • You need enough of your turns to remove all 8 units by 3’s:
       $$y = \lceil 8 / 3 \rceil = 3$$ of your turns.
     • That implies $$y - 1 = 2$$ skips on this warehouse.
   • Minimum skips for a credit: 2.

3. Warehouse 2: inventory = 9

   • After one full cycle (you then co‑worker): 8 units are removed, 1 unit left.
   • Next, your turn on the remainder: $$1 - 3 = -2$$ → you empty it; no skips needed.
   • Minimum skips for a credit: 0.

Now choose optimally with skips = 2:

• Take the free credit from warehouse 2 (0 skips) → credits = 1, skips left = 2.
• You can either:
  • Spend 1 skip on warehouse 0 (get 1 more credit; total 2, skips left = 1), or
  • Spend 2 skips on warehouse 1 (get 1 more credit; total 2, skips left = 0).
• In both cases, total credits = 2. You cannot get credit from both warehouses 0 and 1, because together they would require $$1 + 2 = 3 > 2$$ skips.

Thus the maximum possible credits is 2.

---

Constraints

A commonly reported constraint set for this problem is:

• Number of warehouses:
  • $$1 \le n \le 10^5$$
• Inventory values:
  • $$1 \le \text{inventory}[i] \le 10^9$$
• Dispatch amounts and skips:
  • $$1 \le \text{dispatch1}, \text{dispatch2}, \text{skips} \le 10^9$$

Implementation and design expectations:

• Time complexity around $$O(n \log n)$$ or better.
• Additional space complexity around $$O(n)$$ for any auxiliary arrays.

---

Solution Hint

For each warehouse, treat repeated alternating turns as cycles of size dispatch1 + dispatch2, and compute the minimum number of co‑worker skips needed (if any) for you to be the one who empties that warehouse; then, given these “costs”, greedily select warehouses in order of increasing required skips until you exhaust the global skips budget to maximize the total credits.