Lent Money unofficial Editorial

Problem Link: https://www.codechef.com/JUNE19B/problems/LENTMO

Quick Summary of the question:
Given a list of n numbers, find the maximum sum possible by xoring the elements in groups of size K with X any number of times. Elements chosen in any iteration can be re-chosen in the other iterations.

Solution:

The minimum assured sum we can get is the sum of all elements in the array. This value can be increased by a[i]^x - a[i]. So we can calculate the sum and modify the array to hold the value a[i]^x - a[i] instead.

Since we want to maximize the sum, let us sort this new array such that the largest element comes first. This follows the intuition that it is better to choose elements which increase the sum more.

Here comes an important observation. Elements chosen in any iteration can be re-chosen in the other iterations.

That means we can choose indices 1,3,4 in one set and 1,2,4 in the next. The result would be just 2,3. This allows choices in groups of 2 and (n-2)%2 (by xoring the groups containing xored groups of two).

So when K is even, we can select in groups of 2, and when K is odd, in groups of 1.

In said fashion select elements until it stops increasing the sum.

The only case this fails is if N == K. In this case, we can choose either all elements to XOR or none.

Here is a link to my solution: Gajesh’s Solution

PS: This is my first editorial. Suggestions are welcome.

4 Likes

Amazing bro! I used the same approach too :smile:

Mine is a bit different. It is something like, either I can have maximum possible sum (maximum possible value of each array element either by applying xor or not) or I can have max possible sum - minimum difference abs(arr[i]-arr[i]^x). It clicked me when I did sub task 2 first. My solution - Himanshu’s solution

1 Like

I did not understand the part where k is odd and k<n how can we select each individual element to xor with?
for example like n=6 and k=5 how can we xor all the elements ?
Thank you