Difficulty:
Medium
Prerequisites:
Logic, ad-hoc game, greedy, sorting
Quick Explanation:
====================
Find optimal move for each player & arrange values in the form of array.
Detailed explanation:
=======================
First, we consider the constraints on making moves. Each Ai is paired with each Bi , and only one player can ever receive points for some index i. Once a player receives points for index i, the opposing player can never receive the points at index i of their own array.
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 n-1, 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:
O(n.log(n))