PROBLEM LINK:
Author: Bhushan Khanale
Tester: Suchan Park
Editorialist: Suchan Park
DIFFICULTY:
Easy
PREREQUISITES:
Sorting, Greedy argument
PROBLEM:
Given an integer sequence A_{0}, A_{1}, \cdots, A_{N-1}, Motu’s score is the sum of elements of even indices(A_{0} + A_{2} + A_{4} + \cdots) and Tomu’s score is the sum of elements of odd indices(A_{1} + A_{3} + A_{5} + \cdots). Tomu wins iff his score is larger than Motu’s score. Tomu can swap two elements in the sequence at most K times. Can Motu win?
QUICK EXPLANATION:
It only makes sense to swap an odd-indexed element with an even-indexed element, since otherwise the sum would be the same. For Tomu to maximize his score, he should bring the maximum odd-indexed element, and throw away the minimum even-indexed element. So Tomu can compare these two elements, and if the even-indexed element is larger, then swap these two elements at most K times. This strategy gives optimal score for Tomu every time he swaps. (i.e. If he does K swaps with this strategy, the score he gets is maximal)
EXPLANATION:
Only odd-indexed element and even-indexed element should be swapped. Otherwise, both the score and the set of elements that Motu and Tomu have don’t change, so the swap will be useless.
Suppose the odd-indexed element is x and the even-indexed element is y. When we swap these two elements, Motu’s score is increased by x - y and Tomu’s score is increased by y - x. We can see the sum of two scores doesn’t change, so the best strategy for Tomu is to pick a pair of elements such that y - x is the largest.
Since x and y are from independent sets (odd-indexed and even-indexed), we can choose the maximum y and minimum x! When y - x is positive, Tomu’s score will increase and Tomu should definitely swap these two elements. Otherwise, there is no reason to swap. This solution is always optimal (i.e. makes Motu’s score maximal), since we can think that when we swap K times, we bring K largest elements from the Tomu’s set, and throw away K smallest elements from Motu’s set.
So, the best strategy goes like: for the k-th swap, pick the k-th largest element y from Motu’s original set and the k-th smallest element x from Tomu’s original set. If y > x, increase Tomu’s score by y - x and decrease Motu’s score by y - x. Otherwise, stop the whole process. Compare Motu’s and Tomu’s final score, and print “Yes” if Tomu is the winner.
Since both gamers’ original sets don’t change, we can sort both sets by non-increasing/non-decreasing order, and pick the k-th element from the sorted array while dealing with the k-th swap.
There can be mistakes like: not considering when K > N/2, swap exactly K times without considering whether Motu’s score is increasing or not.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.