The monsoons make an entrance...

Looks like the rainy season has finally begun in earnest, announcing its presence(to me, at any rate) with a thunderclap so loud that it seemed to come from right outside my window...The rain started a few minutes later, and for the first couple of minutes, the word 'torrential' would have been an understatement...

Mumbaikars have a weird love-hate relationship with the monsoons - on one hand, they welcome them as salvation from the inhuman humidity of May, and on the other, they curse them when the streets begin flooding up and staying dry becomes a virtual impossibility. And yet, year after year, I see dozens of people in college fleeing without any kind of protection. I neatly avoid this problem by tossing my umbrella in my bag at the first sign of rain, and keep it there until the monsoons are long gone. The last part isn't really caution, just laziness...

On the algorithms front, the TC arena is working again, and I did manage to solve the 1000 pointer in the practice room. Once again I was a little astonished by the ease with which I did it. It was a simple brute force attack which involved generating subsets of the input, but the way the solution just seemed to develop itself was unbelievable. This might have something to do with the fact that I've really got the hang of recursion now. After I solved it, I was going through the match editorial to see their solutions, and I saw the magic word 'bitmasks'.

For seasoned algorithms people, this doesn't hold any mystery, but this doesn't apply to me. I've been seeing this word on and off for a while in the match editorials, but I never really knew what it was. Most statements I've seen were of the form, "$CoderName wrote a nice solution using bitmasks." Back then I never had much time to follow them, and somehow I came to the conclusion that a bitmask was an array of booleans...not sure how that happened...

Anyway, I finally found out that a bitmask was a single number whose bits you wanted to piddle around with. Since I'm rather fascinated by the way binary numbers fit into all sorts of mathematical applications, I had to take a look. Turns out there's a nice iterative way to generate subsets by simply incrementing an integer and looking at its bits. I'm surprised I hadn't thought of that, since I've always noted the neat way in which binary numbers count up...In fact, the solution is far cleaner in this case. Generating subsets involves choosing whether to include an element or not, so you have to divide and conquer - include in one recursive call, exclude in another. With bitmasks, all that is handled implicitly by incrementing the counter. The 1's and 0's manage this perfectly.

This abstraction seems a little superior to the recursive one - though the recursive one shows you the choice explicitly(which you might want - though I don't see why), the bitmask implementation handles all that without you having to bother - which in the end is what an abstraction is all about - hiding the fancy details. Plus you don't have the overhead of recursive calls, which doesn't hurt either...

Now to sit back, eat, enjoy the cool weather, and learn flood fill algorithms...