Discription
Sample input 1:
4
1 2 3 4
5 6 7 8
Sample output 1:
70
Explanation :
(8*4 + 7*3 + 6*2 + 1*5) = 70
Sample input 2:
4
-1 -2 -3 -4
5 6 -7 -8
Sample output 2:
37
Explanation :
(-4*-8 + -3*-7 + -2*5 + -1*6) = 37
Solution:
C Program
#include <stdio.h>
#include <limits.h>
// SpecialSort function sorts negetive numbers in array1 in ascending order
// and positive numbers and zero in descending order
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void SpecialSort(int *vec1,int n)
{
for(int i = 0 ; i < n-1 ; i++)
{
for(int k = 0 ; k<n-1-i ; k++)
{
if(vec1[k] < vec1[k+1])
{
swap(&vec1[k],&vec1[k+1]);
}
}
}
for(int i = 0 ; i<n ; i++)
{
printf("%d ",vec1[i]);
}
printf("\n");
int idx=0;
while(vec1[idx] >=0)
{
idx++;
}
int start = idx,end = n-1;
while(start<end)
{
swap(&vec1[start],&vec1[end]);
start++;end--;
}
for(int i = 0 ; i<n ; i++)
{
printf("%d ",vec1[i]);
}
printf("\n\n");
}
// Find min product and move the elements to left side of both arrays
int MaximumScalarProduct(int *vec1,int *vec2,int n)
{
int max,sop=0,id1,id2;
for(int i = 0 ; i<n ; i++)
{
max = INT_MIN;
for(int j = i ; j<n ; j++)
{
if((vec1[i]*vec2[j]) > max)
{
max = vec1[i]*vec2[j];
id1 = i; id2 = j;
}
}
sop = sop + max;
swap(&vec1[i],&vec1[id1]);
swap(&vec2[i],&vec2[id2]);
for(int i = 0 ; i<n ; i++)
{
printf("%d ",vec1[i]);
}
printf("\n");
for(int i = 0 ; i<n ; i++)
{
printf("%d ",vec2[i]);
}
printf("\n\n");
}
return sop;
}
int main()
{
int n; scanf("%d",&n);
int vec1[n];
for(int i = 0 ; i<n ; i++)
{
scanf("%d",&vec1[i]);
}
int vec2[n];
for(int i = 0 ; i<n ; i++)
{
scanf("%d",&vec2[i]);
}
SpecialSort(vec1,n);
printf("%d",MaximumScalarProduct(vec1,vec2,n));
return 0;
}
C++ Program
#include <bits/stdc++.h>
using namespace std;
// SpecialSort function sorts negetive numbers in array1 in ascending order
// and positive numbers and zero in descending order
void SpecialSort(int vec1[],int n)
{
int idx=0;
sort(vec1,vec1+n, greater<int>());
while(vec1[idx] >= 0)
{
idx++;
}
int start = idx,end = n-1;
while(start<end)
{
swap(vec1[start],vec1[end]);
start++;end--;
}
}
// Find min product and move the elements to left side of both arrays
int MaximumScalarProduct(int vec1[],int vec2[],int n)
{
int min,sop=0,id1,id2;
for(int i = 0 ; i<n ; i++)
{
max = INT_MIN;
for(int j = i ; j<n ; j++)
{
if((vec1[i]*vec2[j]) > max)
{
max = vec1[i]*vec2[j];
id1 = i; id2 = j;
}
}
sop = sop + max;
swap(vec1[i],vec1[id1]);
swap(vec2[i],vec2[id2]);
}
return sop;
}
int main()
{
int n; cin>>n;
int vec1[n];
for(int i = 0 ; i<n ; i++)
{
cin>>vec1[i];
}
int vec2[n];
for(int i = 0 ; i<n ; i++)
{
cin>>vec2[i];
}
SpecialSort(vec1,n);
cout<<MaximumScalarProduct(vec1,vec2,n);
return 0;
}
JAVA Program
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
static void swap(int arr[],int start, int end)
{
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// SpecialSort function sorts negetive numbers in array1 in ascending order
// and positive numbers and zero in descending order
static void SpecialSort(int vec1[],int n)
{
Arrays.sort(vec1, Collections.reverseOrder());
int idx=0;
while((idx<n) && (vec1[idx] >= 0))
{
idx++;
}
int start = idx,end = n-1;
while(start<end)
{
swap(vec1,start,end);;
start++;end--;
}
}
// Find min product and move the elements to left side of both arrays
static int MaximumScalarProduct(int vec1[], int vec2[], int n)
{
int max,sop=0;
int id1=0,id2=0;
for(int i = 0 ; i<n ; i++)
{
max = Integer.MIN_VALUE;
for(int j = i ; j<n ; j++)
{
if((vec1[i]*vec2[j]) > max)
{
max = vec1[i]*vec2[j];
id1 = i; id2 = j;
}
}
sop = sop + max;
swap(vec1,i,id1);
swap(vec2,i,id2);
}
return sop;
}
public static void main(String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int vec1[] = new int[n];
for(int i = 0 ; i<n ; i++)
{
vec1[i] = sc.nextInt();
}
int vec2[] = new int[n];
for(int i = 0 ; i<n ; i++)
{
vec2[i] = sc.nextInt();
}
SpecialSort(vec1,n);
System.out.print(MaximumScalarProduct(vec1,vec2,n));
}
}
Python
def swap(vec1, pos1, pos2):
vec1[pos1], vec1[pos2] = vec1[pos2], vec1[pos1]
def SpeecialSort(vec1,n):
vec1.sort(reverse=True)
idx=0
while idx<n and vec1[idx] >= 0 :
idx=idx+1
start = idx
end = n-1
while(start<end):
swap(vec1, start, end)
start = start + 1
end = end + 1
def MaximumScalarProduct(vec1,vec2,n):
sop=0
for i in range(0,n):
max = 2147483647
for j in range(i,n):
if(vec1[i]*vec2[j]) > max :
max = vec1[i]*vec2[j]
id1 = i
id2 = j
sop = sop + max
swap(vec1,i,id1)
swap(vec2,i,id2)
return sop
n = int(input())
vec1 = list(map(int,input().split(' ')))
vec2 = list(map(int,input().split(' ')))
SpeecialSort(vec1,n)
print(MaximumScalarProduct(vec1,vec2,n))