Katkat
Back

Maximize Points by Buying Cost-Multiplier Cards

Virtu FinancialData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to determine an optimal ordering strategy and apply dynamic programming to maximize a cumulative score subject to specific operations.

Problem Statement

You are playing a game where you start with a base score of S = 0. You are presented with n cards. Each card i has a multiplier m_i and a cost c_i. When you purchase a card, your base score is updated according to the rule: S_new = (S_old + 1) * m_i - c_i.

You have a total budget of B to purchase a subset of these cards. Each card can be used at most once. You want to maximize your final score S after purchasing some subset of cards in an optimal order.

Implement the function maximize_score(cards, B), where cards is a list of tuples (m_i, c_i) and B is the maximum total cost you can incur.

Constraints

  • n = 1
  • c_i >= 0

Example 1

Input: cards = [(2, 1), (3, 2)], B = 3

  • Option 1 (Card 1 then 2): ((0+1)*2 - 1) = 1. Then (1+1)*3 - 2 = 4.
  • Option 2 (Card 2 then 1): ((0+1)*3 - 2) = 1. Then (1+1)*2 - 1 = 3.
  • Output: 4

Example 2

Input: cards = [(1, 0), (10, 5)], B = 5

  • If you buy only the second card: (0+1)*10 - 5 = 5.
  • Output: 5

Hints

Hint 1

Consider the effect of purchasing two cards in order (A then B) versus (B then A) to determine if a greedy sorting strategy exists.

Hint 2

If you have a fixed subset of cards, can you determine the order in which they should be bought to maximize the score?

Hint 3

Once the optimal order for any subset is determined, the problem reduces to a variation of the knapsack problem where the order matters.

Follow-up questions

  • How does the complexity change if the multipliers `m_i` can be less than 1?
  • If the order of cards was fixed by their input sequence, how would you solve the problem using dynamic programming?
  • What greedy criterion would you use to sort the cards if you were forced to pick all cards with a total budget constraint?