This homework is due on gradescope Friday March 3rd at 11:59pm on gradescope. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in LTEXis recommend though not required. Question 1 (Gameshow Again, 30 points). Dirk's gameshow from Homework 4 decides to change their rules again. Now Dirk can attempt at most k challenges but cannot attempt the same challenge more than once. Give an O(nlog(n)+kn) algorithm to find the strategy that optimizes Dirk's expected winnings. Hint: Based on the solution to part (a) from the previous problem you can note that whatever challenges Dirk attempts to try, he should always attempt them in decreasing order of piRi/(1pi) (with the order not mattering if there are ties). You can assume this without proof