# Older blog entries for fzort (starting at number 60)

28 Mar 2007 (updated 28 Mar 2007 at 10:47 UTC) »
Posts longos em português - eu não gosto

jarod: Advogato is an international forum. Please try to use English. It's a matter of common courtesy.

5 Mar 2007 (updated 5 Mar 2007 at 18:16 UTC) »
fejj: another trick is to use use bubble sort when the partition size gets below a certain threshold.

You might also like to check out the paper A Killer Adversary for Quicksort, in case you haven't already. :)

22 Feb 2007 (updated 22 Feb 2007 at 21:10 UTC) »
Bitwise 2007

So, Team Bandersnatch (bi and I) got in the top-50, which entitles us to t-shirts. I did one problem, he did three. :)

I'd post my solution to problem 6, like he did, but it looks fugly - it took a lot of hammering to make the square peg fit in the star-shaped hole.

Some of the problems were hardcore. None of the teams did problems 3 or 4.

Buzzword Assault

A company called D-Wave demo'ed an alleged superconducting 16-qubit quantum computer. Their PR department seems to claim it's able to solve NP-complete problems in polynomial time, which sounds like BS, but the thing looks pretty darn cool anyway. In both senses of the word (ha, ha).

2 Feb 2007 (updated 2 Feb 2007 at 09:09 UTC) »

I got pwned. Big time.

That is all.

1 Feb 2007 (updated 1 Feb 2007 at 15:59 UTC) »
fejj: the standard way to do that is to replace the division with a multiplication by the reciprocal, multiplied by some power of 2. Then divide the result by that power of 2, which can be done with a right shift. In the case of division by 7, you'd end up with the increasingly more accurate expressions:

q = ((a<<3) + a) >> 6

q = ((a<<6) + (a<<3) + a) >> 9

q = ((a<<9) + (a<<6) + (a<<3) + a) >> 12

q = ((a<<12) + (a<<9) + (a<<6) + (a<<3) + a) >> 15

...

and so on (in binary, 1/7 is .001001001...). Optionally, the result can be fixed with something like

r = a - q*7; while (r >= 7) { q++; r -= 7; }

The multiplication by 7 can be replaced with shifts and adds, of course.

31 Jan 2007 (updated 31 Jan 2007 at 13:24 UTC) »

My performance was dismal. I did the easy problem, then moved straight to the hard one. Then I threw away 20 minutes because I jumped straight to the code before understanding completely the problem statement and then had to start all over again, wasted another 20 minutes tracking down a stupid off-by-one bug, panicked for about 5 minutes, and finally ended up submitting a /wrong/ solution. Guess I need to work on the think-crush-under-pressure thing.

What makes it so frustrating is that the problem was not really that hard, and I was able to concoct a correct solution (here) without major difficulties afterwards, when the time pressure was gone.

Gah.

24 Jan 2007 (updated 24 Jan 2007 at 19:19 UTC) »

The qualification round was easier than I expected. It's probably just meant to filter out the curious. I was able to do both problems in about 30 minutes, and qualified to the next phase.

... seems to be making the rounds on the internet. Two different people sent me the link. It's cute, but there's nothing magical about it, really - perhaps if some people look at it as a simple Perl script they'll realize that it's just a way to rasterize the big number, and the bitmap could be anything.

23 Jan 2007 (updated 23 Jan 2007 at 00:19 UTC) »

So, tomorrow is Google Code Jam Latin America. I'll give it a try, but I expect to get my arse kicked. Although I've been practicing a bit at SPOJ and acm.uva.es, I really suck at thinking under pressure. Ah well, let's see how it goes.

OpenSpecies:

1.

```
#define is_odd(x) (((x)&1) != 0)
#define is_even(x) (((x)&1) == 0)
```

2. if you're out to disprove the Collatz conjecture, use GMP or something.

30 Nov 2006 (updated 1 Dec 2006 at 00:13 UTC) »
mchirico, fejj: it's the Look and Say Sequence. See also: Conway's Cosmological Theorem.

It's all demonstrated in this wonderful IOCCC winner (hint file).

51 older entries...