Here is my solution and explanation for C. Checkposts from Codeforces Round 244 (Div. 2). Here is a link to the problem. This problem is a pretty straight forward question using Tarjan's Alogrithm.

Question Summary

The problem gives us a directed graph with n nodes (called junctions). We want to optimally build police checkposts at these nodes. A checkpost at node i can protect any other node as long as the there is a path from the node i to another node j, and then another path from node j back to node i. A checkpoint also protects the node that it is built on.

We are also given the costs of building a checkpost at each node. Then we are given a list of directed edges describing our directed graph.

Our goal is find the minimum cost to protect every node as well as the number of different ways we can protect every node at the minimum cost.

Solution

A strongly connected component is a "self contained cycle" within a directed graph where every node in the given cycle can reach every other node in the same cycle. In the question, a checkpost can protect a node as long as there is a path to reach it and get back to the checkpost. Therefore, a checkpost in a strongly connected component can protect every other node in the same strongly connected component. Therefore, to minimize the cost to protect every node, we want to build just 1 checkpost at every strongly connected component. We want the checkpost for each strongly connected component to be at the node with the lowest cost to build a checkpost in that strongly connected component.

Tarjan's algorithm is an algorithm used for finding strongly connected components. We can run Tarjan's algorithm to group all the nodes into their strongly connected component. Then for each strongly connected component we can find the node with the smallest cost to build a checkpost and add that cost to the total cost. We can also count the number of nodes with the minimum cost to build a checkpost in each strongly connected component and use that value to calculate the number of ways to protect every node at the minimum cost. The number of ways to protect every node at the minimum cost will be the product of the number of nodes with the minimum cost to build a checkpost in each strongly connected component.

Code

//Global Variable for the next unused id value that we can assign a node
int id;

//A vector which indicates if a node has been visited yet in the current iteration of dfs
vector<bool>visited;

//We assign ids to nodes using this vector. Also keeps track of if a node has never been visited before in
//any dfs iteration since the id will be unassigned.
vector<int>ids;

//The lowest id of a node in a nodes strongly connected component
//All nodes in the same strongly connected component will have the same
//value in low
vector<int>low;

//Stack we use for dfs
vector<int>stack;

//Map where each key is a strongly connected component (represented by the lowest id value) and
//value is a pair representing the lowest cost to build a checkpoint in all of the nodes 
//in the strongly connected component as well as the number of nodes in the strongly
//connected component with the same cost to build as the lowest cost to build
map<int, pair<long long, long long>>scc_to_min_build_cost_and_count; 

void dfs(int at, vector<vector<int>>&adj_dict){
    //Assign the id and low link of the current node to id
    //Then increment id. Also add the node to the visited set
    //and push the node onto the stack
    ids[at] = id;
    low[at] = id; 
    id++;
    stack.push_back(at);
    visited[at] = true; 

    //Iterate through all the neighbors of the current node, if that neighbor has not been assigned an
    //id yet, recursively call dfs on that neighbor node. If we have visited that neighbor, set the low link
    //value of the current node to the min of the current node's low link value and the neighbors low link value 
    for(auto nei: adj_dict[at]){
        if(ids[nei] == -1){
            dfs(nei, adj_dict);
        }
        if(visited[nei]){
            low[at] = min(low[at], low[nei]);
        }
    }

    //After iterating though all the neighbors, if the id of the current node
    //is still equal to the low link of the current node, then this node is the root of 
    //a strongly connected component. This means that this node has the lowest id of all the
    //nodes in the strongly connected component. 
    if(ids[at] == low[at]){
        //Pop from the stack until we reach the current node
        while(!stack.empty()){
            int node = stack.back();
            stack.pop_back();
            visited[node] = false; 
            //set the low link value of the node at the top of the stack to the current node's it.
            low[node] = low[at];
            if(node == at){
                break; 
            }
        }
    }
}
void solve(){
    int n; cin>>n; 
    vector<int>build_cost(n);
    for(int i = 0; i<n; ++i){
        cin>>build_cost[i];
    }

    visited = vector(n, false);
    ids=vector(n, -1);
    low = vector(n, INT_MAX);
    stack.clear();
    id = 0; 
    scc_to_min_build_cost_and_count.clear();
    
    int m; cin>>m; 
    vector<vector<int>>adj_dict(n, vector<int>());
    for(int i = 0; i<m; ++i){
        int u, v; cin>>u>>v;
        adj_dict[u-1].push_back(v-1);
    }

    //We will run Tarjan's algoritm to find strongly connected components

    //Iterate through all the nodes. If a node has not been assigned an id yet, it has never been visited before
    //in any dfs iteration, so dfs from this node. 
    for(int i = 0; i<n; ++i){
        if(ids[i] == -1){
            dfs(i, adj_dict);
        }
    }

    //In this implementation of Tarjan's algorithm, two nodes are in the same strongly 
    //connected component if they have the same value in the low array (aka same lowest link).

    //Iterate through all the strongly connected components, and find the node with the
    //lowest cost to build a checkpoint in the strongly connected component. 
    //Also count the number of nodes in the strongly connected component with the 
    //lowest cost to build
    for(int j = 0; j<n; ++j){
        if(!scc_to_min_build_cost_and_count.contains(low[j])){
            scc_to_min_build_cost_and_count[low[j]] = {build_cost[j], 1};
        }else if(build_cost[j] < scc_to_min_build_cost_and_count[low[j]].first){
            scc_to_min_build_cost_and_count[low[j]] = {build_cost[j], 1};
        }else if(build_cost[j] == scc_to_min_build_cost_and_count[low[j]].first){
            scc_to_min_build_cost_and_count[low[j]].second++;
        }
        
    }

    //Add up all the lowest costs to build for each strongly connected component
    //to get the minimum cost to ensure security for all the junctions
    //Also calculate the number of ways to ensure security for all the junctions at the 
    //minimum cost. This is the number of elements with the minimum cost to build in each strongly 
    //connected component multiplied. 
    long long min_cost = 0; 
    long long number_of_ways = 1; 
    for(auto p: scc_to_min_build_cost_and_count){
        min_cost+=p.second.first; 
        number_of_ways*=p.second.second;
        number_of_ways = number_of_ways%1000000007; 
    }
    cout<<min_cost<<" "<<number_of_ways<<endl; 
}

int main(){
    solve();
}

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; 

}