HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Minimum Scalar Product

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
scalarminimumproduct

Problem

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
#include
#include

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        std::size_t n;
        std::cin >> n;
        if (n != 0) {
            int product = 0;
            std::vector x(n);
            for (std::size_t x_index = 0; x_index > x[x_index];
            }
            std::vector temp(n);
            for (std::size_t t_index = 0; t_index > temp[t_index];
            }
            sort(x.begin(),x.end());
            sort(temp.begin(),temp.end());
            std::vector 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?

Solution

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 > y[y_index];
}
sort(y.begin(),y.end(), std::greater());


Second, the scalar product can be computed with

#include 

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

Code Snippets

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>());
#include <numeric>

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

Context

StackExchange Code Review Q#71210, answer score: 7

Revisions (0)

No revisions yet.