Slashdot Mirror
TopCoder, Math, and Game Programming
reiners writes "DevX.com has an interesting interview with David Arthur (dgarthur), the 2003 TopCoder Collegiate Challenge winner. Arthur discusses many interesting topics: the similarities between TopCoder problems and math problems, why TopCoder performance is positively correlated with 'real-life' programming performance, and why game programming is where the action is."
Those 3 don't happen as much in the real world as one would hope to think. Very few companies do code reviews correctly, nor do most programmers spend enough time testing their algorithms.
I would look at a Top Coder victor the same way I would look at someone who can answer trivia questions correctly. The experience is incredibly valuable, but I wouldn't say that they are parallel at all. Most of the questions and tests are biased against people who have experience doing competitions. A veteran programmer would probably perform 10x better in a real world environment, and is much more valuable than a TopCoder winner who is still in school... but I could be wrong.
Dacels Jewelers can't be trusted.
hehe you must have scored REALLY bad on the competitions to have this kind of attitude. From my experience, I have a relatively average score (~1400) and have nothing but the utmost respect for the true "top coders". Being fast is just one part of it, algorithm knoweldge and language mastery is a must-have to be competitive like these guys are.
Did you read why C++ is his language of choice? The reason he gives is because it's the language he has the most experience in. In fact, most of top ranked competitors use C++ (you have a choice between C++, C# and Java). My theory on this isn't that most of them think that C++ is a better language, it's just that most of the top competitors went through school when C++ or C was being taught so they know it the best. Most (but not all) of the top ranked coders are at the ends of their undergraduate careers or older.
in case people will probably not bother to click, it goes something like this:
you have three days to do the programming task (72 hours), and you submit it via email. you can use whatever language you want, etc etc. here is an official quote:
the cool thing is thisanyway... the money isn't as good, but I like it much better. btw the winner for the 2001 one used haskell, and second place used Dylan, ha! eat my (shorts), Arthur. =)My life in the land of the rising sun.
Summarizing your algorithm: for every pair of nodes that are not connected, do the proper intersections of their in/out-neighborhoods. (Note however that the pair of nodes in the other corners must be checked for connectedness too.)
:)
"For every pair" => O(n^2)
"intersect neighborhoods" => O(n log n)
(by sorting the entries in the neighborhoods and comparing from there)
But as for checking connectedness of pairs in the two intersections, that's again O(n^2).
So we're back at O(n^4) (not to mention the work that goes into preventing double-counting of cycles that are found in several different ways).
Which solution would you rather code up?
I did a 'sort of' competition thing (it was actually a study in how programmers program), and I found that the problem was nothing like what I meet in the real world:
In general, I suspect these competitions reflect academic computing, producing nice and small programs. The real world is more like Google's pagerank software, a simple idea, but complicated by all sorts of issues like Bloggs and Googlebombers.
**TODO** Steal someone elses sig.
I don't normally read SlashDot, but after a friend pointed out this post to me, I had to check it out. Having done so, I couldn't resist making a couple comments.
"I find it interesting that a math double-major, who's considering becoming a math professor, uses C++"
I don't see much use for computer programming at all in mathematics, except in applied areas that don't interest me. I learned C++ because it was ideal for game programming, and I learned Java because it was taught in college and used at the company where I worked.
"Maybe there is some kind of speed math problem think tank that secretly controls the world around us"
Amazingly enough, it is actually possible for certain people to do more than one thing, including math research and contests. For example, I once met this guy who could walk and talk at - get this - the same time. It was pretty crazy.
"With looks like those... it's no surprise he has nothing better to do."
Yeah, screw you too. At least I have better things to do than flame college students on SlashDot. In fact, I spend no more than two hours a week on TopCoder, often less. I almost never practice, and I have not competed very many times.
"someone who won top coder is saying it's a good indication of real world ability"
I believe I said that it is not completely irrelevant. That would be different. Since I did this interview for some internet thing that neither I nor my friends read, and since I am not even looking for a job right now, I didn't really have a vested interest.
"(tenured math professor = job security)"
"he's smart enough to know even he can't get a job programming"
If you guys think it is easier to get and maintain a good programming job than it is to get and maintain a math professorship at, say, Harvard, you are very much mistaken.
"So this guy is telling us he makes this for the money and he will become a math professor?"
I believe I mentioned that money is no longer my primary reason for doing TopCoder. Furthermore, just because I choose to spend minimal time making lots of money given the opportunity, does not mean I can't live with a bad-paying job.
"normally you do not *decide* to become a professor"
Really? I actually think this is precisely what happens.
"other serious, more difficult, competitions like the ACM"
You don't know what you're talking about. Everybody in the TopCoder top 10 has done extremely well on some or all of the ACM, the IOI, the Putnam, and the IMO. Of these contests, I'd say the ACM is actually the most worthless (straightforward problems, missing constraints, ridiculous 3-person 1-computer dynamic, ridiculous 2-year limit).
"Mr. TopCoder could very easily be a pro athlete. He sure answers questions like one."
What do you want me to say? Maybe I should have answered questions like "Have you thought about how you want to apply your computer skills after graduation?" with "Actually, since I'm a super-genius, I thought I would show P != NP, and then maybe move on to the Riemann hypothesis, and then maybe I'd see if I could fly just by thinking really hard, like that dude in the Matrix". Certain questions will get lame answers every time.
To those of you who aren't asses, good day.
-- David Arthur
In theory, C++ would be the worst of the three in a timed contest--too much housekeeping.
Absolute nonsense.
If you know C++ well, and use the language effectively, there is very, very little housekeeping. My C++ code probably has less housekeeping code than typical Java code, because destructors are an immensely useful tool. Toss in auto_ptr, a couple of other smart pointer types and a few design guidelines and C++ is very good at allowing you to focus on the problem, not the tool.
Plus, I never have to remember to call "close()".
Java has an edge not in the area of housekeeping (and, as you mentioned, Java is unpleasantly verbose, particularly with respect to all of the casting that is often required) but in the area of libraries. This gap isn't as large as some might think, though, because (a) many of the Java libs are rather poorly designed and make you work much harder than you should have to and (b) there are some decent libraries around for C++.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.