Maximise Dot Product

Hard
0/120
Average time to solve is 45m
profile
Contributed by
4 upvotes
Asked in companies
ArcesiumDirecti

Problem statement

You are given two arrays of positive integers ‘ARR1’ and ‘ARR2’ of length ‘N’ and ‘M’ respectively, where ‘N’ >= ‘M’.

Dot product of 2 arrays ‘ARR1’ and ‘ARR2’ of size ‘N’ is defined as ‘ARR1[i]*ARR2[i]’ for ‘1 <= i <= N’.

You are allowed to insert a certain number of 0s in ‘ARR2’ to make its size equal to ‘N’, but you cannot change the initial ordering of its elements. What is the maximum dot product of ‘ARR1’ and ‘ARR2’ you can achieve by doing this operation optimally?

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.

The first line of each test case contains two positive integers, ‘N’ and ‘M’ denoting the size of the array ‘ARR1’ and ‘ARR2’ respectively.

The second line of each test case contains ‘N’ space-separated positive integers denoting the elements of ‘ARR1’.

The third line of each test case contains ‘M’ space-separated positive integers denoting the elements of ‘ARR2’.
Output Format : 
For each test case, print a single positive integer, the maximum value of the dot product between ‘ARR1’ and ‘ARR2’.

The output of each test case will be printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’, ‘M’ <= 1000
1 <= ‘ARR1[i]’, ‘ARR2[i]’ <= 1000

Where ‘T’ is the number of test cases, ‘N’, ‘M’ is the size of the arrays, and ARR1[i], ARR2[i] is the ith element of each of the arrays respectively.

Time Limit: 1 sec
Sample Input 1 :
1
3 1
2 11 6
5
Sample Output 1 :
55
Explanation for sample input 1 :
If we add 0s in the 1st and 3rd positions of ‘ARR2’, the array looks like [0, 5, 0]. The dot product then is equal to 0*2 + 5*11 + 0*6 = 55, which is the maximum dot product you can get.
Sample Input 2 :
2
4 2
5 2 4 9
7 8
3 2
5 5 5
6 7
Sample Output 2 :
107
65
Explanation for sample input 2 :
For test case 1, insert 0 in positions 2 and 3(1 based indexing).
So ‘ARR1’ = [5, 2, 4, 9] and ‘ARR2’ = [7, 0, 0, 8] and the final dot product equal to 107.

For test case 2, inserting one 0 at any position makes the dot product equal to 65.
Hint

Try to find a recursive approach.

Approaches (3)
Brute Force Approach:
  • Suppose we are looking at index IDX in ARR2. The elements from index 0 to IDX have been properly placed and 0’s have been inserted at some of these positions.
  • For the current index IDX, we have 2 options. Either we insert a 0 at this index and let the next element in ARR2 go to a farther position or we use the next element of ARR2 at this index.
  • Therefore, for every index of ARR2, we can check what the final answer is if we use a 0 here, or if we use one of the upcoming values of ARR2 here.
  • Use a function RECUR which takes in parameters:
    • IDX, the current index where we need to choose if we want a 0 or not.
    • REMAIN, how many remaining numbers do we have from ARR2? In the end, when IDX = N-1, REMAIN should become 0.
  • Run this function RECUR with IDX = 0, and REMAIN = M. After every array construction, find the dot product, and store the maximum found answer in a global variable ANS.
  • In the end, return the value of ANS.
Time Complexity

O(N*N!), where N is the length of array ARR1.

 

We are finding the dot product of all possible combinations. We insert N - M 0’s in some positions out of N. The time complexity for which in the worst case is O(N!), and for every combination, we do a traversal to find the current answer. Hence the net time complexity is O(N*N!).

Space Complexity

O(N), where N is the length of array ARR1.

 

Looking into the recursion tree, the depth of the tree will be of the order O(N), and at each depth we use the system stack to store the intermediate maximum value of the next RECUR call. Hence the next space complexity is also O(N).

Code Solution
(100% EXP penalty)
Maximise Dot Product
Full screen
Console