4
\$\begingroup\$

Here's the problem statement for Minimum Scalar Product

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn. Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Please review my code.

#include<iostream>
#include<vector>
#include<algorithm>

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        std::size_t n;
        std::cin >> n;
        if (n != 0) {
            int product = 0;
            std::vector<int> x(n);
            for (std::size_t x_index = 0; x_index < n; ++x_index) {
                std::cin >> x[x_index];
            }
            std::vector<int> temp(n);
            for (std::size_t t_index = 0; t_index < n; ++t_index) {
                std::cin >> temp[t_index];
            }
            sort(x.begin(),x.end());
            sort(temp.begin(),temp.end());
            std::vector<int> y(n);
            for (std::size_t y_index = 0; y_index < n; ++y_index) {
                y[y_index] = temp[temp.size()-1-y_index];
            }
            for (std::size_t i = 0; i < n; ++i) {
                product += x[i]*y[i];
            }
            std::cout << product << '\n';
        }
    }
}

How can I make this code better and faster? Particularly without using an additional vector? And is there a better solution?

\$\endgroup\$
7
\$\begingroup\$

Perhaps you should mention that your code takes advantage of the Rearrangement inequality which states that the scalar product of any permutation of the vectors \$ (x_1,x_2,...,x_n) \$ and \$ (y_1,y_2,...,y_n) \$ is minimal if the elements of one vector are in increasing order and the elements of the other in decreasing order.

I see two possible simplifications: First, instead of reading the second vector into a temporary vector, sorting it and then reversing it "manually", you can sort in decreasing order by supplying a comparator to the sort:

for (std::size_t y_index = 0; y_index < n; ++y_index) {
    std::cin >> y[y_index];
}
sort(y.begin(),y.end(), std::greater<int>());

Second, the scalar product can be computed with

#include <numeric>

int product = std::inner_product(x.begin(), x.end(), y.begin(), 0);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.