Sports announcers are expected to keep talking during a broadcast of a sporting event even when there
Question:
Sports announcers are expected to keep talking during a broadcast of a sporting event even when there is nothing actually happening, such as during half-time. One common way to fill empty time is with sports trivia. Suppose, then, that you are going to be a sports announcer for the big game between the Bears and the Anteaters. To fill the empty time during half-time, you would like to say that this is the nth time that a game between the Bears and Anteaters has had a score of i-versus-j at half-time. The problem is that you don’t know the values of i and j yet, of course, because the game hasn’t happened yet, and, once half-time arrives you won’t have time to look through the entire list of Bear-Anteater half-time scores to count the number of times the pair (i, j) appears. Describe an efficient scheme for processing the list of Bear-Anteater half-time scores before the game so that you can quickly say, right at the start of half-time, how many times the pair (i, j) has occurred at similar moments in the past. Ideally, you would like the processing task to take time proportional to the number of previous games and the querying task to take constant time
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia