I am planning to participate in the Google Code Jam this year. And I have been working on the practice problems. It’s been fun, It’s a great feeling when you are able to solve a challenging problem after spending time on it.
My strategy for solving problems is simple: First I try the brute force approach, Once I have a solution, I start thinking of a more efficient way to do it. I have since realized that spending some time thinking about the problem before butting your head against it is way more helpful. When I reached the Minimum Scalar Product problem.
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.
I thought for a moment and came up with the idea that I needed all possible combinations of the first vector with a constant ordered second vector. This algorithm had an order of O(n!). I just jumped into coding and started solving it. Here is the ugly mess of code I came up with:
Here is an example test file if you want to try it.
Then, I started actually thinking about the problem. After a few minutes it became clear to me that all I had to do, to get a minimum product, was order the two vectors in opposing orders of magnitude. And with this understanding I could solve it much more easily and with an algorithm with an order of O(nlogn).
In the past I have used brute force to solve problems where the time didn’t matter (I could always move it to a background process if the time mattered), but it’s a nice feeling to be able to be able to solve problems by simply thinking. Sometimes we(software developers) are so addicted to the quick feedback cycle of coding that we fail to spend time thinking of the problem/solution.