Minimum scalar product

 

Question:

http://code.google.com/codejam/contest/dashboard?c=32016#s=p0

Find the minimum scalar product between two vectors, v1= {x1,x2..xn} & v2={y1,y2,…yn}.

v1*v2 = x1*y1 + x2*y2 + x3*y3… xn * yn

You can try any permutations but the answer should be minimum.

Answer:

  The main confusion for a dummy comes from the permutations in the above question. What does that mean ? does that mean, we can even try x1*y2 ?.. No!! This caused a  major confusion and complicated the things. :)

vector multiplication will happen only between elements in order between two vectors!! Below is the formula

Reference: http://mathworld.wolfram.com/DotProduct.html

So, how would you find the minimum value for this sum ? The minimum sum of products occurs only when you multiply a smaller number in vector 1 with the larger number in vector 2 and add all such occurrences. 

So, we sort vector1 and vector 2. Reverse vector2 and multiply straight to straight to get the minimum sum possible.

Say, if you multiply straight to straight in order or both in sorted, you will get increasing product rather than a reducing product.

Code

#include <algorithm>

long long minimum_scalar(char* inp1, char* inp2, int size)

{

    vector<long> v1, v2;

    long long sum=0;

    char* next = strtok(inp1, " ");

    while(next) {

        v1.push_back(atol(next));

        next=strtok(NULL, " ");

    }

    next = strtok(inp2, " ");

    while(next) {

        v2.push_back(atol(next));

        next=strtok(NULL, " ");

    }

    sort(v1.begin(), v1.end());

    sort(v2.begin(), v2.end());

    reverse(v2.begin(), v2.end());

    for(int i =0; i<size;i++)

    {

        sum += (long long)v1[i] * (long long)v2[i];

    }

    return sum;

}

void main()

{

    ifstream infile("A-large-practice.in");

    ofstream outfile("result.txt");

    string line;

    getline(infile, line);

    int num_of_cases = atoi(line.c_str());

    for(int i=1; i<=num_of_cases; i++)

    {

        getline(infile, line);

        int vsize = atoi(line.c_str());

        getline(infile, line);

        char* list1 = strdup(line.c_str());

        getline(infile, line);

        char* list2 = strdup(line.c_str());

        long long val = minimum_scalar(list1, list2, vsize);

        outfile<<"Case #"<<i<<": "<<val<<endl;

        free(list1);

        free(list2);

    }

}

• Its important to use big data types, especially for codejam problems.
• Read the problem carefully.. i spent lots of time and didn’t figure it out. I need to refer to solutions to come up with this decision. :) no permutations needed again as its just a scalar one-to-one product.
• strtok destroys the input string and can operate at only one string at a time
• strtok is better and faster way of doing contests. But not recommended for production code as it is not thread safe!!