Asked in: AMAZON
Image of the Question
All Testcases Passed ✔
Solution
import math
def getMaximumCredits(inventory, dispatch1, dispatch2, skips):
arr = []
val = dispatch1+dispatch2
// ... rest of solution available after purchaseExplanation
```
To approach this problem efficiently, begin by understanding the process flow of inventory dispatch from each warehouse. The dispatch cycle is repeated as follows: you reduce the inventory first by a fixed amount (dispatch1), followed by your co-worker reducing it by another fixed amount (dispatch2). The goal is to earn a credit if the inventory is emptied during your turn, i.e., the warehouse’s stock becomes zero or negative directly after your dispatch.
The challenge arises from the co-worker’s ability to skip their turn up to a limited number of times (skips). Skipping allows you to take consecutive turns, thereby increasing the likelihood of you being the one to empty a warehouse and earn the credit for that warehouse. However, because the number of skips is limited, a strategy must be devised to apply skips where they have the most value — specifically, where they convert a non-credit (your co-worker would have emptied the warehouse) into a credit for you.
To devise a solution strategy, think in terms of simulating the dispatch cycle for each warehouse and analyzing the number of turns it takes to drain its inventory to zero or less. For each warehouse, simulate the process under two modes:
1. When no skip is used — i.e., your co-worker takes their turn every time.
2. When a skip is used — i.e., your co-worker skips once, allowing you to take two consecutive turns.
Start by computing the number of full dispatch cycles (your turn followed by co-worker’s) needed to deplete each warehouse’s inventory. At each step, subtract dispatch1, then subtract dispatch2, and repeat until the inventory reaches or drops below zero. The point at which the inventory is depleted tells you who emptied the warehouse — either you (earning a credit) or your co-worker (no credit).
Next, simulate an alternative where your co-worker skips one turn early in the process, giving you two consecutive dispatches. Recalculate the sequence with this skip applied and determine whether the skip changes the outcome — does it convert a warehouse where your co-worker would’ve gotten the credit into one where you get the credit?
With this analysis, you can classify the warehouses into:
- Type A: You would already get a credit even without any skips.
- Type B: You would not get a credit unless your co-worker skips.
- Type C: Even with a skip, you still don’t get the credit.
Type A warehouses always contribute to the credit count and require no skips. For Type B warehouses, you can potentially earn an additional credit if you apply a skip. Therefore, your goal becomes to identify all Type B warehouses, compute how many of them exist, and then decide where to apply your limited skips for maximum gain.
Sort the Type B warehouses by the potential benefit (they all provide a +1 credit if a skip is applied), and select up to 'skips' number of these warehouses to apply your co-worker’s skips. You only want to apply skips to those where it actually increases the total number of credits. Skipping in Type A or C warehouses is wasteful.
The final credit total becomes:
- Credits from all Type A warehouses (automatically earned without any skips).
- Plus the number of Type B warehouses to which you applied skips (up to the limit of the 'skips' value).
Given the constraints (up to 1e5 warehouses and large inventory values), it is crucial to avoid full simulations for each warehouse. Instead, derive a mathematical formula or expression to determine who would have emptied the warehouse in how many turns. Since dispatch amounts are fixed, the process can be predicted with arithmetic rather than iteration.
For instance, you can compute the number of your own dispatches before the warehouse is emptied and compare it to the total number of turns. Determine the number of turns it takes to deplete the inventory by calculating how many (dispatch1 + dispatch2) cycles are required, and where the inventory stands after each. Then, consider what happens if a skip is inserted: does it reduce the number of cycles needed, or shift the sequence so that you now perform the final dispatch?
By analyzing each warehouse in this deterministic way, you can classify the outcomes efficiently and maximize your credits under the given constraints. This approach ensures that the problem can be solved in linear time with respect to the number of warehouses, making it feasible within large input bounds.
```