You are given N numbers. Two players alternatively choose numbers. Both players want to maximize the score of numbers picked by them. Chef plays first.
Find out maximum score of the Chef if both players play optimally.
Find the sum of alternate numbers starting from the last when the array is sorted in increasing order.
Let us first play this game before we proceed to the final algorithm.
We will first play it for even numbers.
Let N = 2 and a1 < a2 be two numbers.
if Chef chooses a1 , then Roma will choose a2 and Chef will be left with total sum a1.
If Chef chooses a2 , then Roma will choose a1 and Chef will be left with total sum a2 which is better than a1. Hence the answer will be a2.
In other words, as Chef plays first, he will pick the maximum of the numbers a1 and a2 (i.e. a2).
Let N = 4 and a1 < a2 < a3 < a4.
Suppose chef chooses any number expect a4, then Roma will select a4 [ as he plays optimally ] . For the remaining two numbers chef takes the maximum one [ as seen above ].
Out of all three possible cases, the maximum sum that Chef can get is a3 + a2.
If Chef chooses a4 , then Roma chooses a3. Chef chooses a2 and Roma chooses a1. Now a4 + a3 > a3 + a2.
Similarly we can prove by induction that in the optimal strategy, both the players should pick the maximum number available for picking.
We will sort the array in increasing order and the answer will be the sum of alternate numbers starting from the last.
Proof immediately follows from by the assertion that in the optimal strategy, both the players should pick the maximum number available for picking.
Read(N) for i in [1,N] Read(A[i]) Sort(A+1,A+N+1) //Sort all numbers for(int i=N ;i>0;i-=2 ) Answer = Answer + A[i] Return Answer
As we need to sort the array. We can apply any O(N2) eg. selection, insertion, bubble sorting algorithm.
We need to use O(n log n) sorting algorithm like quick, merge, heap sort.
We can also use O(105) bucket sort Algorithm.
Some Interesting Readings
[Merge Sort in O(N*log N) time]
[Bucket Sort Algorithm in O(Max_Number)]
Setter and Tester Solutions: