MTYFRI - Editorial

PROBLEM LINK:

Practice

Contest

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.

Are the solution links right? Why does all the links mention GCD? Where do you use it?

1 Like

you can see my code (link below) there is use of gcd in my program
https://www.codechef.com/viewsolution/18413976

The links given are solutions to rd19, the first problem in May Challenge.
My solution to the problem is here - MTYFRI, in case anyone wishes to refer.

The links are certainly incorrect, it points to the code of another problem. @admin, could you please fix this?

Can’t we use heap data structure to solve this ?

1 Like

Easy to understand python solution

https://www.codechef.com/viewsolution/66042194

for _ in range(int(input())):
    n, k = map(int,input().split())
    A = list(map(int,input().split()))
    
    ans = "NO"
    
    motu = []
    tomu = []
    
    motu_score = 0
    tomu_score = 0
    
    for i in range(n):
        if i%2 == 0:
            motu.append(A[i])
            motu_score += A[i]
        else:
            tomu.append(A[i])
            tomu_score += A[i]
    
    if motu_score < tomu_score:
        print("YES")
        continue
    
    motu.sort()
    tomu.sort()
    
    swaps = min(len(tomu),k)
    
    take = sum(motu[len(motu)-swaps:len(motu)])
    give = sum(tomu[0:swaps])
    
    motu_score -= take
    tomu_score += take
    motu_score += give
    tomu_score -= give
    
    if tomu_score > motu_score:
        ans = "YES"
    
    print(ans)