Skip to content

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. anon

    Below is python code for the same problem

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

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

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

    def array():
    s=f.readline()
    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)

Leave a Reply

Your email address will not be published. Required fields are marked *