In a programming competition, each participant must develop algorithms to solve

Question

In a programming competition, each participant must develop algorithms to solve a set of problems. The ranking is set according to the maximum number of problems solved by the participant. As a tie-breaking criterion, we adopt the total execution time of the algorithms used to solve the problems. Implement a procedure that, given input as a vector of size n with the names of the participants, a respective vector with the number of problems solved and a respective vector with the total execution time, indicates the winner. Your procedure should run in (n). Calculate the cost of your algorithm to prove that it executes in (n).

Explanation / Answer

Psuedocode:

names = ["p1","p2","p2","p4","p5"]; # Input
solved_problems = [8,6,7,9,9]; # Input
time = [3,4,7,7,8]; # Input
maxx_problems = -float("inf")
best_time = float("inf")
winner_index = 0;
for i in range(0,len(names)):
   if((solved_problems[i] == maxx_problems) and (time[i] <= best_time)):
       maxx_problems = solved_problems[i]
       best_time = time[i]
       winner_index = i
   elif(solved_problems[i] > maxx_problems):
       maxx_problems = solved_problems[i]
       best_time = time[i]
       winner_index = i      
print "Winner is", names[winner_index]

Running time: since we are just iterating once through an array of size n, time complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.