Tag Archives: kickstart

Code Jam 2008 Round 1A, Problem A: Minimum Scalar Product

Hey there, since things are getting a little more calm, I can focus once more to solve some nice Code Jam problems. And here we go, from the first official tournament round: Problem A: Minimum Scalar Product. It says:

You are given two vectors v1=(x1,x2,…,xn) and v2=(y1,y2,…,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+…+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

There’s a catch on the text, that made me quite confused. In case you didn’t notice, it’s that damn TWO PERMUTATIONS part. Despite getting the sample results right, when the bigger test cases came, I wasn’t able to get the smallest results right! Because, guess why, I was only doing two value permutations, because to me, the text says so!

Anyway, took a look into the results and saw that participants were simply not considering this limitation and outputting the minimum possible value anyway and to hell with it. If Google thinks this would be the correct approach, who am I to judge! 😀 Just sort both arrays, invert one of them, iterate calculating the MSP and you’re done! Python code, as usual:

for case in range(1,int(raw_input())+1): # For all test cases
  size = int(raw_input())                # Since we're informed, save array size
  x = map(int, raw_input().split(" "))   # Get all X parameters
  y = map(int, raw_input().split(" "))   # Get all Y parameters

  x.sort()                               # Sort both vectors
  y.sort()                               # And sort-reverse Y
  y.reverse()                            # So we can match the bigger/smaller values

  msp = 0
  for i in range(size):                  # For all the array's len
    msp += x[i]*y[i]                     # Sum "forward" on X and "backwards" on Y

  print "Case #%d: %d" % (case, msp)     # Print the sum

And that’s it! Quick and easy, despite the text hiccup.  Githubbin’ it. See you!

Advertisements

Project hosting, tough choice

Howdy 🙂

it’s 10PM once again, and I’ve decided to restart posting. Really it’s been really hard to focus energy into posting content. Let’s see how it goes. I was planning a deep analysis into many different services and their offerings, guided by this wikipedia entry, but, as a colleague once said: “who DOESN’T use GitHub nowadays”?

I love Free and Open Source Software and advocate its use, but I don’t really care if the host I’m using holds proprietary software. I work in a closed-source business company (in fact, we use plenty Open Source software to produce our proprietary products), and I don’t think every software MUST be free, but COULD, with a different business model.

I’d like to have a defect control system with it (such as Bugzilla) and I’d love to have my projects featuring a nice front page introduction, perhaps even some examples of its use. A wiki system would also be nice, but I could live without it. I don’t need a build system, mailing lists or forums for my projects. There are also lots of alternatives for team management, so I don’t need it (especially on single-man projects such as mine).

So, not only GitHub matches my needs, but also Sourceforge, Google Code (without web-page hosting), Launchpad (without web and wiki), JavaForge, GNU Savannah and some other less known choices. But, it’s friends’ good experience with it that guides my choice this time, and I can always change if there’s a better solution. 🙂

To GitHub!

Code Jammin’

Always been a fan of Google Code Jam (http://code.google.com/codejam/), tried competing once (2009 with Java, I guess), passed the first stage, didn’t made after the second. 😀 Still, was a great experience on how to code and understand problems in efficient ways, using small amounts of time and confident solutions. The problems I faced through the competition were pushing language and I/O processing boundaries… categories that I’ve improved much through professional experience.

So, as I intend to participate in this year’s competition, I’ll start to upload everyday a solution to a given codejam problem, usually written in Python (great code development speed) and some comments about it. 🙂

So let the Jammin’ begin!