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.
