Answer Happy

Problem 3. Your friend likes horse races and, more specifically, likes to bet on them. However, he is also the most risk-averse gambler on Earth and really dislikes uncer- tainty. He maintains a list of all horses participating in races and, for each of them, a list of their results (how well they placed). He asks you to create a data structure which will allow him to very quickly find which horse has the best worst performance (i.e., never did too badly), so that he can always bet on the safest choice. More for- mally, here is what your data structure should support: there are n horses, and horse i has a corresponding list (r₁,...,m) of m, results (positive integers) indicating their rank in all the m, races that horse ran so far. Your data structure needs to support the following operations: I • ADDHORSE(): Add a horse (with no history of scores) in O(logn) time, and return its number. • ADDRACERESULT (i,r): Given a horse's number i and a positive integer r, add the race result r to horse i in O(logn+log m) time, where m= maxisin mi. • GETWORST RESULT (i): Given a horse's number, return its worst performance in O(logn) time, where the worst performance is worst (i) = maxisjsmj. If the horse has no result recorded yet, return co (i.e., infinity). • GETSAFESTHORSE(): Return the number of a horse with the "best worst perfor- mance" in O(1) time; that is, return the integer i between 1 and n such that Tworst (i) minisis worst (i). If multiple horses have the same best worst per- formance, you can return any of them. = Example: ADDHORSE() returns 1 ADDHORSE() returns 2 GET WORST RESULT(1) - returns co ADDRACERESULT(1,1)- stores that horse 1 finished in 1st position in their 1st race ADDRACERESULT(2,10)- stores that horse 2 finished in 10th position in their 1st race ADDRACERESULT (2,12) - stores that horse 1 finished in 12th position in their 2nd race GETWORST RESULT(1) - returns 1 GETWORST RESULT(2) returns 12 GETSAFESTHORSE() returns 1 - - . ADDRACERESULT(1,20)- stores that horse 1 finished in 20th position in their 2nd race GETWORSTRESULT(1) returns 100 GETSAFESTHORSE() - returns 21 Your task is to design a data structure for this problem that uses O(n + m) space, and satisfies the required worst-case time complexities. Remember to: a) Describe your data structure implementation in plain English. b) Prove the correctness of your data structure. c) Analyze the time and space complexity of your data structure. [8 marks] [7 marks] [5 marks]