The question we are solving is E. Beautiful Array from Codeforces Round 954 (Div. 3). Here is a link to the problem.

Question Summary

We are given an array of n integers. We are also given an integer k.

Our Goal is to turn the given array into a beautiful array. The question defines a beautiful array as such : The array b1, b2 ,..., bn is beautiful if bi=bn-i+1 for all 1<=i<=n. In plain English an array is considered beautiful if the array is a Palindrome. To better understand this, lets say we have 9 elements and the current index is 2. Then the array is beautiful if array[2] == array[9-2 +1= 8]. Notice how 2 is the second element from the front, and 8 is the second to last element. Let's say the index is 4. Then array[4] == array[9-4+1 = 4]. So the middle element only has to equal itself (if n is odd) just like a palindrome.

We are allowed to shuffle the array elements as we like before we start any operations.

An operation is defined as taking an element and adding k to it.

We want to turn the provided array into a palindrome in the smallest number of operations possible. If it is not possible to turn this array into a palindrome with the provided value of k, we should print -1.

Approach

The first thing to notice is that for a number to be turned into another number by adding k to it, both numbers must have the same modulo k. For example, lets say we want to turn the number 1 to the number 3, but the value of k is 5. We can add 5 as many times as we want to 3, but we will never be able to turn 1 into 3 by adding 5 since they both save different values modulo k. However, if we want to turn the number 1 to the number 6 by adding 5, we can do so with one operation since they both share the same modulo 5. So if we want to turn number A into number B, AmodK == BmodK

Let's say we have two numbers A and B which have the same modulus k. Let's say A is smaller than B. The number of operations (x) to turn A into B is B=A+Kx. B-A = Kx (B-A)/K = x.

So ideally, we would want to group numbers with the same modulo k together, and then pair them up in such a way that it costs the least amount of operations to make them equal. Note that if n is even and there is any element with no one to pair with, or if n is odd and there is more than 1 element with no one to pair with, then we cannot form a palindrome so we must print -1.

Solution

1) Create a map with the key being a number 0-k and the value being a vector of integers. While inputting the values of the array, mod k the number and push it to the appropriate vector in the map.

2) If n is equal to 1, the array is already beautiful since it is a single number. Print 0 and exit

3) Create a variable called total_operations that will hold the total number of operations. Create a variable called no_pair_count which will hold the number of elements that cannot be matched with another element with the same mod k as it.

4) Iterate through all the mod results (0-k).

5) At each iteration, if the vector has an odd number of elements, we increment no_pair_count. If n is even and no_pair_count == 1 or n is odd and no_pair_count>1, we print -1 since we cannot form a palindrome with the given array and value of k.

6) At each iteration, we sort the vector which holds all the elements with the current mod k. This is done to help make it easier to calculate the optimal pairing of elements. Two elements that are the most similar in value and the with the same mod k will require the least additions of k to make the two elements equal.

7) At each iteration, if the number of elements in the vector which holds all the elements with the current mod k is even, the minimum cost to turn each pair of elements equal is just the abs(num[i], num[i+1])/k for each i incrementing by 2. In other words, the minimum cost is the minimum cost of making each set of adjacent numbers equal. So we calculate the difference, and then divide the difference by k to see how many times we would have to add k to the smaller number for the two numbers to become equal.

8) At each iteration, if the number of elements in the vector which holds all the elements with the current mod k is odd we must calculate which element to remove such that the operation is minimized. We can do this efficiently by using a Prefix Sums array and a Suffix Sums array. The Prefix Sums array will hold the rolling total of the number of operations needed to make the adjacent pairs equal starting from index 0. Note that since the number of elements in the vector is odd, and we are incrementing by 2, the last element will not be included in the Prefix Sums. The Suffix Sums array will hold the rolling total of the number of operations needed to make the adjacent pairs equal starting from the last index. Note that since the number of elements in the vector is odd, and we are decrementing by 2, the last element will not be included in the Suffix Sums.

Now we will iterate through all the indices in the vector which holds all the elements with the current mod k.

If the index is odd, we know that there is an even number of elements to the front and an even number of elements to the back. Therefore, the total number of operations needed to turn this vector into a palindrome is just PrefixSums[index/2] + SuffixSums[(vector.size()-i)/2].

However, If the index is even, there is an odd number of elements to the front and an odd number of elements to the back. So we want to pair up the adjacent elements to the front except for at i-1 and pair up adjacent elements to the back except for i+1. Then we want to add the number of operations required to make num[i-1] equal to nums[i+1]. Therefore, the total number of operations needed to turn this vector into a palindrome is just PrefixSums[(index-1)/2] + SuffixSums[(vector.size()-i-1)/2] + (nums[i+1] — nums[i-1])/k. So during each iteration we calculate the total number of operations required to make the current vector of elements which all have the same mod k into a palindrome if we removed the current index, and the minimum cost would be the min of all these costs.

Once we have the min cost to make the current vector of elements which all have the same mod k into a palindrome, we add it to our total_operations variable.

Note that the parity for index values is flipped if we 0-index.

9) Once we have finished iterating through all 0-k, we print total_operations.

Code

void solve(){
    long long n, k; cin>>n>>k; 
    vector<long long>nums(n);

    //Group together elements with the same mod k. 
    map<long long, vector<long long>>mod_k_counter; 
    for(long long i = 0; i<n; ++i){
        cin>>nums[i];
        mod_k_counter[nums[i]%k].push_back(nums[i]);
    }
    
    //Base Case : if the array is 1 element, it is already a palindrome
    if(n==1){
        cout<<0<<endl; 
        return; 
    }

    long long total_operations = 0; 

    //Holds the total number of elements that do not have another element with the same mod k
    //to pair with in a palindrome.
    long long no_pair_count = 0; 

    //iterate through all the groups of elements that share mod k values. 
    for(auto& p: mod_k_counter){
        //if there is an odd number of elements in the group, there will be an additional
        //element that cannot pair up with another element of the same mod k
        if(p.second.size()%2==1){
            no_pair_count++;
        }
        if((n%2 == 0 && no_pair_count>0) || (n%2==1 && no_pair_count > 1)){
            cout<<-1<<endl; 
            return; 
        }

        //Two elements will take the least number of operations to make equal if they are close in value
        sort(p.second.begin(), p.second.end());

        if(p.second.size()%2==1){
            //cout<<"Number of elements with this value of mod k is odd"<<endl; 
            //One element will remain unpaired.
            //After one element is removed, it breaks down into the even case
            
            //Prefix Sum of costs of pairs starting from the front
            //Last element not incluced
            vector<long long>prefixPairs;
            prefixPairs.push_back(0);
            for(long long i = 0; i<p.second.size()-1; i+=2){
                prefixPairs.push_back(prefixPairs.back()+(p.second[i+1] - p.second[i])/k);
            }

            //Suffix Sum of costs of pairs starting from the back
            //First element not included
            vector<long long>SuffixPairs;
            SuffixPairs.push_back(0);
            for(long long i = p.second.size()-1; i>0; i-=2){
                SuffixPairs.push_back(SuffixPairs.back()+(p.second[i]- p.second[i-1])/k);
            } 

            long long min_cost = INT_MAX; 
            for(long long i = 1; i<p.second.size()-1; i++){
                if(i%2==1){
                    //If the index is even (1-indexed), then there is an odd number of elements to the front and back
                    long long cost = 0;

                    long long num_pairs_front = (i-1)/2; 
                    cost+=prefixPairs[num_pairs_front];

                    long long num_pairs_back = (p.second.size() - i-1)/2;
                    cost+=SuffixPairs[num_pairs_back];

                    cost+=(p.second[i+1] - p.second[i-1])/k; 
                    min_cost = min(min_cost, cost);
                }else{
                    //If the index is odd (1-indexed), then there is an even number of elements to the front and back. 
                    long long cost = 0;

                    long long num_pairs_front = i/2; 
                    cost+=prefixPairs[num_pairs_front];

                    long long num_pairs_back = (p.second.size()-i)/2;
                    cost+=SuffixPairs[num_pairs_back];

                    min_cost = min(min_cost, cost);
                }
            }
            //Cost if first index is removed
            min_cost = min(min_cost, SuffixPairs.back());

            //Cost if last index is removed
            min_cost = min(min_cost, prefixPairs.back());

            total_operations+=min_cost; 
        }else{
            //Even number of elements with the same mod k
            //Just pair up adjacent elements starting from the front
            for(long long i = 0; i<p.second.size(); i+=2){
                total_operations+=(p.second[i+1] - p.second[i])/k;
            }
        }
    }
    cout<<total_operations<<endl; 

}