18 August 2013

Union Find

I never understood the point of union find (not after learning it in high school with Dr. Nevard, or even after learning about Kruskal's minimum spanning tree algorithm) until I saw this problem:

A journey to the Moon

The member states of the UN are planning to send two people to the Moon. But there is a problem. In line with their principles of global unity, they want to pair astronauts in such a way, that both are citizens of different countries.

There are N astronauts numbered with identifiers from 0 to N-1. They are qualified and trained to be sent to the moon. But the trouble is that those in charge of the mission haven’t been directly informed about the citizenship of each astronaut. The only information they have is that some particular pairs of astronauts belong to the same country.

Your task is to compute in how many ways they can pick a pair of astronauts satisfying the above criteria, to be sent to the moon. Assume that you are provided enough pairs to let you identify the groups of astronauts even though you might not know their country directly. For instance, if 1,2,3 are astronauts from the same country; it is sufficient to mention that (1,2) and (2,3) are pairs of astronauts from the same country without providing information about a third pair (1,3).


Input Format

The first line contains two integers, N and I separated by a single space. I lines follow. each line contains 2 integers separated by a single space A and B such that

0 ≤ A, B ≤ N-1

and A and B are astronauts from the same country.


Output Format

An integer containing the number of permissible ways in which a pair of astronauts can be sent to the moon.


Constraints

1<=N<=10^5

1<=I<=10^6


Sample Input

4 2
0 1
2 3


Sample Output

4

Explanation

As persons numbered 0 and 1 belong to same country and 2 and 3 belong to same country. So the UN can choose one person of 0,1 and one out of 2,3. So number of ways of choosing pair is 4.

This pre formatting sucks, but that's beside the point.

Here's my solution:

class DisjointSet(object):
    def __init__(self, vals):
        self.parents = {x: x for x in vals}
        
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            return self.find(self.parents[x])
    
    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        self.parents[xRoot] = yRoot
        
    def sets(self):
        d = {}
        for child in self.parents:
            parent = self.find(child)
            if parent not in d:
                d[parent] = set()
            d[parent].add(child)
        return d        

N, L = map(int, raw_input().strip().split())
ds = DisjointSet(range(N))
for i in range(1, L+1):
    a, b = map(int, raw_input().strip().split())
    ds.union(a, b)

s = ds.sets()
acc = 0
if len(s) > 1:
    cumsum = [len(x) for x in s.values()]
    for i in range(len(cumsum)-2, 0, -1):
        cumsum[i] += cumsum[i+1]
    
    for i, x in enumerate(s.values()[:-1]):
        acc += len(x) * cumsum[i+1]
        
print acc

Maybe someday I will get proper code formatting for my blog.

15 August 2013

Stark Contrast

"That's the difference between you and me," he said. "I just assume that there will be nannies."
--Elon Musk

but s/nannies/supercars/

Source: http://www.marieclaire.com/sex-love/relationship-issues/millionaire-starter-wife

08 August 2013

Chilling

"I am your wife," I told [Elon Musk] repeatedly, "not your employee."
"If you were my employee," he said just as often, "I would fire you."
Justine Musk's account of her failed marriage: http://www.marieclaire.com/sex-love/relationship-issues/millionaire-starter-wife

07 August 2013

A Summer of Cars: Part III

A generous salesman by the name of Matt at the New England Aston Martin-Lotus dealer volunteered to teach me how to drive a manual. Thanks for making my summer complete!


After arriving at the dealer, we took this beautiful white Lotus Elise to a nearby parking lot. Matt pushed the car quite hard to show me how nimble it was -- very! It showcased the car's favorable power-to-weight ratio.

A bit more about the Elise: it's a sub-2000lb roadster powered by a 180hp Toyota engine. The car is very stripped, whose interior consists of…almost nothing. The mirrors are manually adjusted. The seats don't have a backrest adjustment. The passenger seat is bolted to the chassis. As in, it doesn't move back and forth. And that's why I can't believe this car has power windows.


Now onto the fun part. I've watched several videos of people driving a stick, heel-to-toeing (an advanced technique), and such, but they don't reveal the subtleties. In particular, the clutch behaves more like a sigmoid than a digital function, to my surprise:

When you shift into gear, you (slowly) let go of the clutch until you feel it grabbing the engine, then give the engine some gas, and finally (slowly) release it. Releasing the clutch too fast, and the engine stalls. Release it too slow, and the clutch wears and may start smelling badly.

We started off by starting the car, shifting into first, driving in a large circle, shifting into neutral, and stopping. This took a few tries to get, and even then, I sometimes still had trouble because I was releasing the clutch too quickly after it engaged with the engine.

Next up was shifting into 2nd, which was fairly easy. I pushed the car a little harder by going faster (about 20mph) and making tighter turns while doing figure eights.

Impressed by how quickly I have progressed, Matt let me shift into third, which went smoothly, although an ominous smell emanated from the clutch. Oops!

I then tried starting the car on a 5* hill. The process was more or less the same, but I had to give the car a little more gas to counteract gravity. I took a few tries to get it since I wasn't stepping on the throttle enough.

Finally was reverse. I found this the trickiest, mainly because I suffered from some cognitive dissonance -- I illogically thought that reverse was so different from the forward gears. I got it after a few tries, but wasn't as good was shifting into first, etc.

As for the ride experience, the car is very loud. The engine drones, since it cruises around 3000-3500rpm; if you've sat in the godawful Smart ForTwo, it's a comparable experience. You feel every single imperfection in the road, and know which tires ran over the bump. An accurate description is a box on wheels, or a street legal go-kart. But it's so undeniably lovable, and I think that makes me sad if I were to turn it down.

So here comes the really heartbreaking part: I have to make a choice between the Elise and the 981 Boxster before the end of the year, since the lead time for order a bespoke Porsche is 6 months. (Porsche essentially shuts down the factory to handle all of the special orders at the end of a model year.) I'm not sure if I'll be able to live with the Lotus and its dearth of practicalities, such as next-to-nothing sound deadening, track seats, briefcase-sized trunk, and possibly awkward blind spots.

But for now, I'll live and dream as if I had both.

02 August 2013

Ideal Philosophy

The Koenigsegg philosophy does not tolerate compromise. Rather, we work at innovation in order to avoid compromise completely. Nothing is impossible. This open-mindedness and dedication are what define Koenigsegg and its cars.