Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!
Hearthstone Basics
Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:
For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.
For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.
Cleanup
You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?
Input:
The enemy minions (a1,h1),…,(an,hn) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2
Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.
Tanks
TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?
Input: The enemy minions (a1,h1),(a2,h2) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2
Output: “Yes” if your minions can take out both enemy minions this turn.
Charge!
Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!
Input Your available mana K. The minions with Charge on your hand, (a1,h1,c1),…,(an,hn,cn) ∈ N2.
Output: The total number of Attack points you can play this round.
Cards generated using achievementgen.com
Thore Husfeldt 
Hi, this is a very enjoyable exam. Here is what I think,
1. Since the number of minions are the same for both sides, we can sort our side attack power; a’_1 … a’_n . Then, sort enemy minion’s health; h_1 … h_n. Assume both series are sorted in non-increasing order (1st is the largest, nth is the smallest). Because each minion can attack only once, we can clean up iff a’_i >= h_i for all i.
2. I think this problem can be reduced to 2-partition when total attack = h1+h2. What we need to fix is that 63 =! 94. To fix this we just add two very large numbers (for example at least sum of our attack) that has the difference of 31 (let’s say x and x+31) in order to make sure that x and x+31 is on the different side when we do the partition. So this is weakly NP-hard.
3. This one is knapsack, so it is also weakly NP-hard.
Sorry, i just found out that my second answer is totally wrong. Reduction must be done in the opposite direction. Given 2-partition problem, we can scale the input number such that each partition sum up to 1. Then, we add 2 more numbers, i.e. 62 and 93, to make both side sum into 63 and 94 respectively. So, if we can kill these two monsters, we can solve 2-partition.