[SOLVED] COMP3121/9101 21T3 Final Exam

Question 10 Solution

COMP3121/9101 21T3 Final Exam

Copyright By Assignmentchef assignmentchef

This document gives a model solution to question 10 of the final exam. Note that alter-
native solutions may exist.

1. There are n monsters planning to take over the city, but only one hero guards the
city. The hero has combat effectiveness a0 and initially has b0 health points, while
the ith monster has combat effectiveness ai and initially has bi health points. Both
combat effectiveness and health points are positive integers. Both the monsters and
the hero die when they reach zero health points or less.

In order to protect the people in the city, the hero will fight monsters until either
all monsters are killed or the hero dies. In each fight, the hero can fight any living
monster. If the ith monster is selected, then that monster loses a0 health points and
the hero loses ai health points. After any fight, it is possible that neither the hero
nor the monster dies, and it is also possible that both are killed. However, each time
the hero kills the selected monster without dying, the hero gains h health points as
their success inspires them to keep fighting.

Design an algorithm which determines whether the hero can successfully kill all the
monsters (surviving all fights) and runs in O(n log n) time.

You must provide reasoning to justify the correctness and time complexity of your
algorithm.

The input consists of the positive integers n and h, as well as 2n+2 positive integers
a0, b0, a1, b1, . . . , an, bn.

The output is either YES or NO.

For example, suppose n = 2 and h = 10. Suppose the hero has combat effectiveness
a0 = 5 and initial health b0 = 9, and that the monsters have:

1. combat effectiveness a1 = 3 and initial health b1 = 14.

2. combat effectiveness a2 = 4 and initial health b2 = 8.

The correct answer for this example is YES.

For each monster i, first work out the amount of health ci that must be expended
in order to kill that monster. This is given by the number of fights required bi/a0
multiplied by the combat effectiveness ai of the monster.

We sort the monsters by increasing order of ci. This takes O(n log n) time. Now, for
each monster in this order, the hero should select that monster and fight it until the

monster is killed. The hero spends ci health points to kill monster i, and if the hero
survives, they gain h health points. The health points of the hero can be updated in
O(1) for each monster. If the heros health points remain positive at the conclusion
of every fight, the answer is YES. Otherwise, the answer is NO.

The total time complexity is O(n log n+ n) = O(n log n).

Proof of correctness: First, observe that the hero should fight one monster until it is
dead, rather than switching between living monsters. The latter approach rearranges
the order in which the hero takes damage, and delays the bonus h points for killing
a monster. This is clearly no better than fighting the monsters one by one.

It remains to prove that this sequence of monsters is optimal, using a greedy stays
ahead proof. Since we expend the fewest possible health points to kill the first
monster, our algorithm maximises the health points of the hero immediately after
killing one monster. We then maximise the health points of the hero after killing two
monsters and so on until all monsters are killed, and if these maxima are positive the
answer is YES.

CS: assignmentchef QQ: 1823890830 Email: [email protected]