Home ›

Google Code Jam - Minimum Scalar Product

Nico Heid's picture
by Nico Heid on Sun, 04/10/2011 - 13:52
in

With the Google Code Jam 2011 less than four weeks away, it is time for some finger exercises.

Let's start with the Minimum Scalar Product, which should only take you a few minutes.

Here's the Java version, which will only work for the small input set. I'll explain later.

  1. public static int getMinimumScalarProduct2(int[] x, int[] y) {
  2.  
  3.         Arrays.sort(x);
  4.         Arrays.sort(y);
  5.         int sum=0;
  6.  
  7.         for (int i = 0; i < x.length; i++) {
  8.             sum += x[i] * y[x.length -1 -i];
  9.         }
  10.         return sum;
  11.     }

What we do is sort both arrays, then multiply them. One starting from the beginning, the other from the end. So our biggest numbers are multiplied with the smallest. The math is on Google's solution page, we're just looking at coding here.

This works for the small input set, but not the large one. Why?

Take a look at the Limits:

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

The result of the large dataset will not fit in an int. So we switch to BigInteger, which can hold our results.

  1. public static BigInteger getMinimumScalarProduct(int[] x, int[] y) {
  2.  
  3.         Arrays.sort(x);
  4.         Arrays.sort(y);
  5.  
  6.         BigInteger sum = BigInteger.ZERO;
  7.         for (int i = 0; i < x.length; i++) {
  8.             sum = sum.add( new BigInteger(""+ x[i]).multiply(new BigInteger(""+y[x.length -1 -i])));
  9.         }
  10.         return sum;
  11.     }

Take a look in the BigInteger API doc, I'm very sure you'll need it for this years jam. I initially made the mistake of not assigning the result of sum.add() to sum.

Now, as I try to do a bit python, I will also present my python solution. Maybe Christian can spot my classic java thinking and provide a more python like version for my lines.

  1. f = open('../resources/codejam/msp-large.in', 'r')
  2.  
  3. cases = int(f.readline())
  4.  
  5. for i in range (0, cases):
  6.     nrOfIntegers = f.readline()
  7.     xs = f.readline()
  8.     ys = f.readline()
  9.  
  10.     x = [int(s) for s in xs.split()]
  11.     y = [int(s) for s in ys.split()]
  12.  
  13.     x.sort()
  14.     y.sort()
  15.     sum = 0
  16.     size = len(x)
  17.  
  18.     for j in range(0, size):
  19.         sum+= int(x[j])* int(y[size -1 - j])
  20.  
  21.     print sum

It's the exact same idea, so no suprises here.

Happy practicing.

Comments

Christian Harms's picture
smaller python solution
Christian Harms - Mon, 04/11/2011 - 09:38

Ok, my python solution looks shorter, but the algorithm is not changed:

  1. fp = open("A-large-practice.in")
  2. for case in range (int(fp.readline())):
  3.     nrOfIntegers = fp.readline()
  4.     x = sorted(map(int,  fp.readline().split()))
  5.     y = reversed(sorted(map(int,  fp.readline().split())))
  6.     print "Case #%d: %d" % (case+1, sum([a[0]*a[1] for a in zip(x,y)]))

FrankieTheCoin's picture
stdin =
FrankieTheCoin (not verified) - Thu, 04/14/2011 - 19:25

  1. stdin = open("A-large-practice.in").readlines() # stdin = list(sys.stdin)
  2. for case, vectors in enumerate(zip(stdin[2::3],stdin[3::3])):
  3.     v1 = sorted(map(lambda x: int(x), vectors[0].split(" ")))
  4.     v2 = reversed(sorted(map(lambda x: int(x), vectors[1].split(" "))))
  5.     print "Case #%s: %s" % (case, sum(map(lambda a: a[0] * a[1], zip(v1,v2))))

I've done it some time ago and I believe that my algorithm is the same. Still python sorry. Going to learn Lua.

jhe's picture
yuck, map with lambdas
jhe (not verified) - Thu, 05/05/2011 - 13:33

  1. import itertools, operator, sys
  2. next(sys.stdin)
  3. for idx, test in enumerate(itertools.izip(*(sys.stdin,)*3)):
  4.     (n,), v1, v2 = ([int(i) for i in line.strip().split()] for line in test)
  5.     print "Case #%s: %s" % (idx+1, sum(map(operator.mul, sorted(v1), sorted(v2, reverse=True))),)

N00bs! :Þ

Ismael's picture
This Python solution doesn't work
Ismael (not verified) - Sat, 03/31/2012 - 10:44

Why this prodvides an incorrect ouput for me ?

  1. for i in range(1, N+1):
  2.         str1 = 'Case #' + str(i) + ': '
  3.         fout.write(str1)
  4.  
  5.         # n integers
  6.         n = int(it.next())
  7.  
  8.         x = [int(xi) for xi in sorted(it.next().split())]
  9.         y = [int(yi) for yi in sorted(it.next().split(), reverse=True)]
  10.         scalar = sum([elm * y[index] for index, elm in enumerate(x)])
  11.  
  12.         fout.write(str(scalar) + '\n')

Christian's picture
sorting strings instead of int
Christian (not verified) - Mon, 04/02/2012 - 12:52

I guess you sorted the list of strings instead of integers?

Ismael's picture
YES
Ismael (not verified) - Mon, 04/02/2012 - 14:07

OOOHHH Thx a lot!

  1. x = [int(xi) for xi in it.next().split()]
  2. y = [int(yi) for yi in it.next().split()]
  3.        
  4. x.sort()
  5. y = sorted(y, reverse=True)