# Minimum Scalar Product

My solution for the Minimum Scalar Product problem of Round 1A of Google Code Jam 2008:

``````
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int cmpA(const void *v1, const void *v2) {
int *e1 = (int*)v1, *e2 = (int*)v2;
if (*e1 < *e2) return 1;
if (*e1 > *e2) return -1;
return 0;
}
int cmpB(const void *v1, const void *v2) {
int *e1 = (int*)v1, *e2 = (int*)v2;
if (*e1 < *e2) return -1;
if (*e1 > *e2) return 1;
return 0;
}

main() {
char str[4096];
int N, n, Q;
int iN, i;
long long result;

int A[800], B[800];
int rA[800], rB[800];
int sA, sB;
int pA, pB;
int zA, zB;

fgets(str, sizeof(str), stdin);
sscanf(str, "%d", &N);
fprintf(stderr, "N:%d\n", N);

for (iN = 0; iN < N; iN++) {

result = 0;

fscanf(stdin, "%d", &n);
fprintf(stderr, "Case#%d N:%d\n", (iN+1), n);

for(i = 0; i < n; i++) {
fscanf(stdin, "%d", &A[i]);
}
for(i = 0; i < n; i++) {
fscanf(stdin, "%d", &B[i]);
}
qsort(A, (size_t)n, sizeof(*A), &cmpA);
qsort(B, (size_t)n, sizeof(*B), &cmpB);

for(i = 0; i < n; i++) {
result += (long long)A[i] * (long long)B[i];
}

fprintf(stdout, "Case #%d: %lld\n", iN + 1, result);

}
return 0;
}
``````

## 1 thought on “Minimum Scalar Product”

1. Below is python code for the same problem

f=open("round1A-large.in")

def integer():
s=s.strip()
s=int(s)
return s

def string():
s=s.strip();
return s

def array():
s=s.strip()
s=s.split()
for i in range(len(s)):
s[i]=int(s[i])

return s

noTests=integer()

for i in range(noTests):
integer()
row1=array()
row2=array()
row1.sort()
row2.sort()
row2.reverse()
Sum=0
for ii in range(len(row1)):
Sum += row1[ii]*row2[ii]

print "Case #%d: %d" %(i+1,Sum)