Minimizing the dot product codechef solution in c++

 

Minimizing the dot product Problem Code: BITMASK2Submit

Abhishek is very good in mathematics. Now he came to know about dot product of vectors. So He asked his friend Suyash a problem. He gave him two vectors A and B of length N . He asked him to minimize the dot product of these two vectors. Suyash has a choice to change the order of the elements of these two vectors i.e. for any two elements i and j in any vector he can interchange the position of these elements.

Since Suyash is new to programming, He asked you to solve this problem for him. 

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the length of the vectors.

The second and third lines contain N space-separated integers A₁, A₂, ..., A_N and B₁, B₂, ..., B_N denoting the elements of the vectors respectively.

 

Output

For each test case, output a single line containing the minimum dot product.

Constraints

Should contain all the constraints on the input data that you may have. Format it like:

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 8
• -1000 ≤ A_i,B_i ≤ 1000

 

Example

Input:
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Output:
-25
6

-------------------------------------------------------------

solution in cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class solution
{
public:
	void dot_product()
	{
		int n;
		cin >> n;

		vector<int> v1(n);
		vector<int> v2(n);

		for (int i = 0; i < n; i++) cin >> v1[i];
		for (int i = 0; i < n; i++) cin >> v2[i];

		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end(), greater<int>());

		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += (v1[i] * v2[i]);
		}
		cout << sum << "\n";
	}
};

int main()
{
	solution ss;

	int t;
	cin >> t;

	while (t--)
	{
		ss.dot_product();
	}
	
	return 0;
}