COMP3121/9101 22T1 Assignment 2

1.  (20 points) You are playing the popular card game “Inscribings”. In this game, your

opponent places n monster cards onto the board, the ith of which has hi  health

points.  You in turn have m ≥ n hero cards in your hand, the jth of which deals

dj  damage per turn.  To begin the game, you will choose n heroes from your hand

and assign each of them to a different enemy monster.  Each turn, your heroes will

deal damage equal to their damage power to the opposing enemy. If at any point an

opponent’s monster reaches 0 health or less, then it is destroyed.

You are given a limited number of turns k to destroy all enemy monsters. Design an

algorithm which runs in O(m + nlog n) time and determines whether it is possible

to assign your heroes in such a way as to destroy all enemy monsters in k turns or

fewer. If it is possible, your algorithm must also return any such assignment.

Up to 15 points will be awarded for an algorithm which runs in Θ(mlog m) time.

2.  (20 points) Alice writes n distinct integers on a blackboard, and picks a positive

integer K. She then allows Bob to make moves, each of which consist of the following

steps.

1. Identify two integers x and y on the blackboard which differ by at most K, i.e.

|x − y| ≤ K.

2. Erase the smaller of the two chosen integers.

Bob’s task is to make moves in this way until he is no longer able to do so. Note that

in some cases, Bob may be unable to make even a single move.