Maximize Points by Buying Cost-Multiplier Cards
Company: Virtu
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given `n` cards. Card `i` has a non-negative integer **cost** `cost[i]` and a positive integer **multiplier** `multiplier[i]`. You start with `initialPoints` points.
You may buy any subset of the cards (including none), and you may buy the cards you choose **in any order**. Each card can be bought at most once. You can buy a card only when your current points are at least its cost (you can never go into debt).
When you buy card `i` with current points `p`, your points become:
$$p \;\leftarrow\; (p - cost[i]) \times multiplier[i]$$
That is, you first pay the cost, then the **remaining** points are multiplied by the card's multiplier.
Return the **maximum** number of points you can end up with after buying cards optimally.
### Examples
**Example 1**
```
cost = [3, 5, 2]
multiplier = [2, 3, 2]
initialPoints = 10
```
Output: `63`
One optimal plan buys the third card, then the first, then the second:
- Start with `10`. Buy card 3 (cost 2, mult 2): `(10 - 2) * 2 = 16`.
- Buy card 1 (cost 3, mult 2): `(16 - 3) * 2 = 26`.
- Buy card 2 (cost 5, mult 3): `(26 - 5) * 3 = 63`.
No other subset or order produces more than `63`.
**Example 2**
```
cost = [1, 1000, 1]
multiplier = [2, 2, 3]
initialPoints = 5
```
Output: `22`
It is best to buy card 3 then card 1, and **skip** the expensive card 2:
- Buy card 3 (cost 1, mult 3): `(5 - 1) * 3 = 12`.
- Buy card 1 (cost 1, mult 2): `(12 - 1) * 2 = 22`.
- Card 2 would require paying 1000, which is never worthwhile, so it is left unbought.
**Example 3**
```
cost = [100]
multiplier = [2]
initialPoints = 10
```
Output: `10`
You cannot afford the only card (and buying it would lower your points anyway), so the best you can do is buy nothing and keep your `10` starting points.
### Constraints
- `1 <= n <= 1000`
- `cost.length == multiplier.length == n`
- `0 <= cost[i] <= 10^4`
- `1 <= multiplier[i] <= 10^4`
- `0 <= initialPoints <= 10^9`
- It is guaranteed that the maximum achievable points fits in a signed 64-bit integer for every test case. (Languages with native big integers, such as Python, may simply use arbitrary-precision arithmetic.)
### Input / Output
- Input: two integer arrays `cost` and `multiplier` of equal length `n`, and an integer `initialPoints`.
- Output: a single integer — the maximum points achievable.
Quick Answer: This question evaluates a candidate's ability to reason about optimal ordering and subset selection under a multiplicative-then-subtractive scoring rule, a classic dynamic programming and greedy-exchange-argument scenario. It tests practical algorithmic problem solving in the coding and algorithms domain, requiring proof that a particular buying order maximizes the final value. Such problems are common in technical interviews to assess whether a candidate can identify and justify a non-obvious ordering strategy.
You are given `n` cards. Card `i` has a non-negative integer **cost** `cost[i]` and a positive integer **multiplier** `multiplier[i]`. You start with `initialPoints` points.
You may buy any subset of the cards (including none), and you may buy the cards you choose **in any order**. Each card can be bought at most once. You can buy a card only when your current points are at least its cost (you can never go into debt).
When you buy card `i` with current points `p`, your points become:
p <- (p - cost[i]) * multiplier[i]
That is, you first pay the cost, then the **remaining** points are multiplied by the card's multiplier.
Return the **maximum** number of points you can end up with after buying cards optimally.
### Examples
**Example 1**
cost = [3, 5, 2]
multiplier = [2, 3, 2]
initialPoints = 10
Output: 63
Buy card 3 (cost 2, mult 2): (10 - 2) * 2 = 16; card 1 (cost 3, mult 2): (16 - 3) * 2 = 26; card 2 (cost 5, mult 3): (26 - 5) * 3 = 63.
**Example 2**
cost = [1, 1000, 1]
multiplier = [2, 2, 3]
initialPoints = 5
Output: 22
Buy card 3 then card 1 and skip the expensive card 2: (5 - 1) * 3 = 12, then (12 - 1) * 2 = 22.
**Example 3**
cost = [100]
multiplier = [2]
initialPoints = 10
Output: 10
You cannot afford the only card, so keep your 10 starting points.
### Constraints
- `1 <= n <= 1000`
- `cost.length == multiplier.length == n`
- `0 <= cost[i] <= 10^4`
- `1 <= multiplier[i] <= 10^4`
- `0 <= initialPoints <= 10^9`
- The maximum achievable points fits in a signed 64-bit integer for every test case.
### Input / Output
- Input: two integer arrays `cost` and `multiplier` of equal length `n`, and an integer `initialPoints`.
- Output: a single integer, the maximum points achievable.
Constraints
- 1 <= n <= 1000
- cost.length == multiplier.length == n
- 0 <= cost[i] <= 10^4
- 1 <= multiplier[i] <= 10^4
- 0 <= initialPoints <= 10^9
- The maximum achievable points fits in a signed 64-bit integer.
Examples
Input: cost = [3, 5, 2], multiplier = [2, 3, 2], initialPoints = 10
Expected Output: 63
Explanation: Buy card3 -> (10-2)*2=16, card1 -> (16-3)*2=26, card2 -> (26-5)*3=63.
Input: cost = [1, 1000, 1], multiplier = [2, 2, 3], initialPoints = 5
Expected Output: 22
Explanation: Buy card3 -> (5-1)*3=12, card1 -> (12-1)*2=22; the cost-1000 card is unaffordable and never worthwhile, so skip it.
Input: cost = [100], multiplier = [2], initialPoints = 10
Expected Output: 10
Explanation: The only card costs 100 but you have 10, so you cannot buy it and keep your 10 points.
Input: cost = [0], multiplier = [1], initialPoints = 50
Expected Output: 50
Explanation: A multiplier of 1 gives (50-0)*1 = 50, no gain, so buying is pointless; keep 50.
Input: cost = [0, 0], multiplier = [5, 5], initialPoints = 3
Expected Output: 75
Explanation: Both cards are free with multiplier 5: 3 -> 3*5=15 -> 15*5=75.
Input: cost = [9], multiplier = [2], initialPoints = 10
Expected Output: 10
Explanation: You can afford the card, but (10-9)*2 = 2 < 10, so buying it lowers your points; skip it and keep 10.
Input: cost = [0], multiplier = [10], initialPoints = 0
Expected Output: 0
Explanation: With 0 points, (0-0)*10 = 0, no increase, so the answer stays 0.
Hints
- Expanding the buy sequence i_1, ..., i_k shows the final value equals initialPoints*prod(m) minus a penalty: sum over j of cost[i_j] * (product of multipliers from position j to the end). The prod(m) factor is the same for every ordering of a fixed chosen subset, so only the penalty depends on order.
- For a fixed subset, the penalty is minimized (final maximized) by an adjacent-swap / exchange argument: card a should come before card b iff c_a*m_a*(m_b-1) < c_b*m_b*(m_a-1), i.e. sort by c*m/(m-1) ascending. Cards with multiplier 1 can never raise points, so ignore them.
- Once the bought cards must appear in that sorted order, the value of the remaining cards is monotone non-decreasing in your current points. Therefore, scanning in sorted order, buy a card only when you can afford it AND (p - cost)*mult > p; otherwise skip it. Lowering your points never helps (it also never makes a later card affordable).