Log in

No account? Create an account
lars0 [entries|archive|friends|userinfo]

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Waterloo contest [Feb. 5th, 2005|04:39 pm]
I beat everybody today! :)

http://plg.uwaterloo.ca/cgi-bin/cgiwrap/acm00/score2.cgi (same contest)

It was nice to code at home, instead of on the broken terminals in MC. Problem A was on the nasty side. I was lucky to notice all the tricky cases, and also to come up with a nice approach. For a long while I thought I would have to do all kinds of horrible 3D geometry, but I ended up just doing a 4-point binary search (or whatever one wants to call it) on the line segment joining A and B. Segment AB happens to lie on the great circle - how convenient! So for every point P on it, you can just extend OP to the edge of the great arc.
link2 comments|post comment

Greek letters [Dec. 17th, 2004|02:25 pm]
I may be the only person in the history of the world to encounter a scenario where a factor of O(\alpha(n)) was of practical significance. \alpha(n), of course, being the inverse Ackermann function.

My solution to 'skiareas' from last weekend's USACO contest timed out on a single test case because I used union-find with path compression (as I am wont to do) to merge ajacent points of the same height into a single component, rather than coding up a BFS/DFS.

(Yeah, I know there are factors besides the asymptotic complexity, such as an function call for each lookup, but that should never be the difference between passing and failing a test case. I've always found USACO's super-strict time limits irritating.)
link3 comments|post comment

Candy [Nov. 25th, 2004|02:21 pm]
Today I mailed a box of Glosette chocolate coated raisins from Toronto to Calgary.

Cost of Glosettes: $0.75 + tax
Cost of express postage: $8.70 + tax

I now have a tracking number for the Glosettes. Sweet.

And yes, they have Glosettes in Calgary.
link1 comment|post comment

I got the job. [Nov. 23rd, 2004|04:58 pm]
Google, here I come!
link9 comments|post comment

Relationship troubles? [Jun. 17th, 2004|01:52 pm]
This is pretty amusing so far (I'm about 2% of the way down the page).

linkpost comment

UVA contest [Jun. 6th, 2004|08:10 pm]
Edited: okay, so it turns out E was easy too, and the problem description was just bad. Argh.
linkpost comment

Thesis [Jun. 2nd, 2004|04:05 pm]
[mood |aggravatedaggravated]

Man, I am so sick of this. I'm not learning anything, I'm not doing anything. I'm just writing stuff that's really of no interest to anybody, least of all myself. The real work was done months ago in the span of a couple of weeks, is already documented in conference papers, merely fills a void rather than being truly interesting, and completely solves the problem. Continuing to write is such a massive waste of time. I kind of wish I'd just submitted the papers months ago and then quit; screw the stupid thesis and the stupid degree and do something real! (Either industry, or switch fields from CS to math.) ~25 pages to go (sigh).
linkpost comment

IPSC [May. 21st, 2004|05:38 pm]
[mood |accomplished]

I competed in the Internet Problem Solving Contest this morning and placed 19th. I guess that's not bad, considering I was competing individually, but I had hoped for top 10. I should have been able to get A2, which would've done the job. Oh well -- next year. It's my first time trying this contest, and I was quite pleased at how interesting and fun most of the problems were. I definitely recomend checking them out, and previous years' too! Last year's problems may have been even better. I loved the hard one that nobody got; it was a really nice mix of game theory and graph theory, as opposed to really nasty geometry this year.
link1 comment|post comment

Sympatico is down this morning [May. 17th, 2004|10:04 am]
[mood |amusedamused]

So I skipped breakfast and went straight to my office so I could be somewhere with Internet access ASAP. Now I'm hungry.
linkpost comment

SRM 194 [May. 15th, 2004|06:26 pm]
[mood |frustratedfrustrated]
[music |Rush - Middletown Dreams]

This was a rare SRM that I came close to winning, and therefore a perfect time to rant. In spite of having to go back and resubmit my 250 because of a really bad mistake, I ended up being the first to submit all three problems. After racing through the 500 and 1000 (481 and 715 points respectively), I was pretty excited at my huge lead. I typically don't fare so well on easy problem sets.

After a minute or two, jshute ended up pulling ahead of me in points, thanks to my resubmission and his high score on the 1000. After testing my problems some more and chatting with Yarin, I noticed jshute suddenly drop below me with his own resubmit of the 250. I went back to double check my own 250 and found *another* mistake and had to resubmit again, putting antimatter in the lead. Then I watched him resubmit his 250 as well!

So the events basically went like this:

1) I resubmitted myself out of first, leaving jshute in first.
2) jshute resubmitted himself out first, returning me to first.
3) I REresubmitted myself back out of first, leaving antimatter first.
4) antimatter resubmitted out of first, leaving jshute in first.

It must have been a fun match to watch. The three of us were well ahead of everyone else until we had to resubmit our problems.

My first resubmit was because I wasn't actually multiplying anything by two, even though that's what I'd intended to do all along. It was so glaring and stupid that I noticed it immediately after my original submission, and resubmitted in time to still get 210 points. The second resubmit was because I had "< 62" instead of "<= 62", and much more costly. If I'd only noticed that on my original resubmission, I'd have won comfortably.

Careless errors have been my achilles heel since high school math. Argh! But at least another Waterloo grad won.
link2 comments|post comment

[ viewing | most recent entries ]