Difficulty:
Quick Explanation:====================
Detailed explanation:=======================
Next, we must consider what would make an optimal move. It can be proven that the optimal move for the current player is to always choose the first unused element having the maximal value for AI + Bi , as the player will either add the largest number of points to their own score or block the opposing player from ever receiving a large amount of points. So now that we've established we must both maintain paired values and choose the first available index having a maximal value for AI + Bi, we have to consider the most efficient way to find which index to choose. The best way to do this is to sort each pair of values in descending order of the maximum sum of Ai and Bi. Next, we simply need to traverse the sorted array from 0 to n1, adding the appropriate number of points at index i (i.e., the paired value at i associated with the current player) to the current player's score. This means that in the ith move, the current player will make an optimal move by choosing the ith element in the sorted array. Once we've finished summing the scores, we simply compare them and print the appropriate result. Complexity:
This question is marked "community wiki".
asked 29 Oct '16, 23:42
