Home » Uncategorized » Google Code Jam — Solutions to two practice problems in Python

Google Code Jam — Solutions to two practice problems in Python

Since Code Jam contest starts in one day, I thought of solving some problems for practice.

Minimum Scalar Product

The solution is based on the fact that the maximum area of a rectangle is when it is square and generalizing to R. It can be proved by taking the derivative of f(x) = (x – a)(x – b). f'(x) = 0 x = (a + b)/2. Therefore, if we have two numbers with a constant sum, their product is maximized when they are as close as possible. My failure to explain it simply should not make it look hard. Intuitively, if we select the number, say 8, 4 * 4 is bigger than 5 * 3 or 6 * 2 or 7 * 1 and so on…

EDIT: Simpler explanation: We want to maximize \vec{A}\vec{B} = -\frac{1}{2}\left((\vec{A} - \vec{B})^2 - \vec{A}^2 - \vec{B}^2\right). We know that \vec{A}^2 and \vec{B}^2 (the measure of the vectors) are the same no matter how we rearrange the coordinates.

testcases = int(input())
for t in range(1, testcases + 1):
    n1 = int(input())
    num1 = [int(n) for n in input().split()]
    num2 = [int(n) for n in input().split()]
    num1.sort()
    num2.sort(reverse=True)
    res = 0
    for i in range(n1):
        res += num1[i] * num2[i]
    print('Case #' + str(t) + ': ', end='')
    print(res)

As we see in this solution, I sort twice. Since addition is commutative, it should be enough to sort only one of the lists but I could not find a smart way of doing so.

Rope Intranet

This problem attends a solution using dynamic programming. We sort according to the numbers on the first building. Then, we start from the lowest window in this building. We check how many ropes from lower windows go higher than the rope from the current window in respect to the other building. And the answer is the sum of the number of ropes that go higher for every window. My solution emulates the way insertion sort works. Probably, there is a better solution.

from bisect import bisect

testcases = int(input())
for t in range(1, testcases + 1):
    n1 = int(input())
    
    wires = []
    for k in range(n1):
        w1 = input().split()
        w1 = (int(w1[0]), int(w1[1]))
        wires.append(w1)
    
    wires.sort(key=lambda wir: wir[0])
    other_building = []
    crossings = 0
    for a, b in wires:
        i = bisect(other_building, b)
        crossings += len(other_building) - i
        other_building.insert(i, b)
    
    print('Case #' + str(t) + ': ', end='')
    print(crossings)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: