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 uncertainty. 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 formally, here is what your data structure should support: there are n horses, and horse i has a corresponding list (11,...,1m) of m¡ results (positive integers) indicating their rank in all the mi races that horse ran so far. Your data structure needs to support the following operations:

• 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 = max1<i<n mi.

GETWORSTRESULT(i): Given a horse's number, return its worst performance in O(log n) time, where the worst performance is r'worst (i) = max15i<m; ';. If the horse has no result recorded yet, return o (i.e., infinity).

GETSAFESTHORSE(): Return the number of a horse with the "best worst performance" in O(1) time; that is, return the integer i* between 1 and n such that I'worst (i*) = min <i<n l' worst (i). If multiple horses have the same best worst performance, you can return any of them.

Example: ADDHORSE() - returns 1

ADDHORSE() - returns 2

GETWORSTRESULT(1) - returns ∞

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 ist race

ADDRACERESULT(2,12) - stores that horse 1 finished in 12th position in their 2nd race

GETWORSTRESULT(1) - returns 1

GETWORSTRESULT(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 2 space,

Your task is to design a data structure for this problem that uses O(n+m 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.