TopCoder, Math, and Game Programming 287
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."
programming 3D rendering engine (Score:5, Interesting)
Language of Choice (Score:5, Interesting)
I'm not sure what conclusion to draw from that fact, I just find it interesting.
Re:Language of Choice (Score:2, Interesting)
A good friend of mine recently finished a PhD in Maths and decided to start his career in the IT industry. Having never done any computer science, he did a six month course in C++ and then a six month course in Java and found that Java was much easier for him. He said that he never felt that he fully understood C++, but he topped the class in Java. I am sure he could have done well in C++ if he had worked at it, but he has gone on to work as a very successful Java developer.
I think the Language of choice depends on the context, and the conclusion I draw from these annecdotes is that Java is good for industry and C++ is good for academia.
Re:Real World vs. Top Coder... (Score:3, Interesting)
Actually it's not as simple as that. In order to be successful in TopCoder competitions, one has to be a rather smart person (in fact the 2001 winner is "the smartest guy in the world" [nwsource.com]), with good analysis, generalization and abstraction skills, and above all, a quick thinker. The problems are not trivial to dissect, and time pressure is strong.
So for a long term employment (3+ years), I would rather hire a young successful TopCoder participant (one can always gain experience but not smarts) than a regular but experienced guy.
how about encryption? (Score:5, Interesting)
3D rendering is not entirely about math (probably a lot more to do with studying the brain and how people generally interpret images that they see). Encryption however is ALL math. Anyhow, that's my 2 cents.
Re:Language of Choice (Score:1, Interesting)
Industry still relies on C/C++
Re:good thing (Score:3, Interesting)
1. Read the easy question.
2. Recall the Java class/method that shortcutted the problem.
3. Write 3-5 lines of code (not including the class and method header).
4. Score near max points and be done before everyone else and sit for the rest of the round.
5. Challenge round, slam the people that tried to finish as fast as you. Chances are these people made a mistake and if you knew the problem, you knew what to look for right away.
Most of the time I'd also just open the last two questions so I knew what to expect if someone did finish them, but the bulk of the people in the lower rooms would never even get to finish them in the allotted time, if they did, you could almost always count on it being wrong. So long as I didn't answer the big questions and let my scores inflate, I never moved out of those rooms and I never saw a point in it. The only point I saw in getting to the higher rooms was to make the invitational. Yeah I'd love to win $100,000 but at 1 in 64 kids (back a year and a half), my odds weren't that good anyway even if I thought I was talented enough to win (which I know I'm not).
This is not real world coding and I would NOT encourage colleges to become involved in Topcoder because most of their philosophies go directly against what professors are trying to instill in up and coming programmers. You are not encouraged to design, comment, test or even read the problem thoroughly in these competitions because it all costs you valuable points. Whether or not these are valuable skills in the real world, I'm still growing up and learning.
nobody talks about the actual problems? (Score:5, Interesting)
especially the hard one, probably, because my mind is drawing a blank on how to have it implemented... (no i didn't cheat and look at the solution).
heh, actually they go like this:
*easy* - okay, i can think of a algorithm. probably not the fastest thing in the world, but it should work out.
*medium* - have a haze of an idea on what an algorithm might look like. with enough caffine it MIGHT solidify.
*hard* - at least I understand the problem, but curses on the restrictions of a binary tree =)... no idea on algorithm that would finish executing before the end of the universe. (granted, only 50 elements, so maybe it's possible brute-force)
Damn; this is exactly how
Topcoder (Score:2, Interesting)
p.s. Topcoder also has the best Java client side applications going. Their competition arena application/applet is a masterpiece.
no i don't work for them. Yes I have competed.
Re:nobody talks about the actual problems? (Score:4, Interesting)
I'll take a shot.
Ironically, I find the "easiest" one the hardest. I can think of a brute-force O(n^4) algorithm, but it's not pretty.
The medium problem seems to be straight-up dynamic programming.
Sadly, the "hard" problem is also straight-up dynamic programming, and is well-known. It's very lame that they chose this problem -- I'm pretty sure it's in CLR (Cormen, Leiserson, Rivest "Introduction to Algorithms"), and it's definitely considered in many other sources.
Overall, these questions don't seem to be testing for breadth of knowledge, or even ability to think creatively. They all have essentially cookie-cutter answers.
Coding up correct answers under time pressure is another matter, of course. I give all the credit in the world to someone who can crank out the code and test out all the corner cases properly.
Re:nobody talks about the actual problems? (Score:2, Interesting)
anyway, I think it's probably faster to (for every node n)
1) compile a list of nodes going out of n
2) compile a list of nodes coming into n
3) for every node m not associated to n (complement of (1)+(2), find its list nodes that it has relations with, and find the intersection of the sets
4) profit!
well, 250 points only, but i think the above should get you on your way at a lot less than O(n^4). unless i got some costs wrong for some of the operations (i am having doubts about the intersect).
Re:nobody talks about the actual problems? (Score:3, Interesting)
Oh, BTW, you get 8 seconds for your solution to run, so brute forcing all combinations would take way too long. In more concrete terms, this means you want something with a time complexity less than about 50 million.
Occaml - Language of Choice for the Mathematicians (Score:3, Interesting)
Say what you want, but for the math gifted, most of them will code in Occaml, or one of the Meta Languages (ML), if they ever come across them.
Re:nobody talks about the actual problems? (Score:2, Interesting)
Unless the list of intersects (however many intersect pairs you got) is bound by n^2... hmmmmmmm...
haha, alright. I concede. you see why I am only the rank of "armchair computer programming contest participant."
p.s. I have to say, though, that the amount of connectedness amongst the nodes do tricky things - because if very few nodes are connected to eachother, that would give you a huge list to check previously (near n^2), but you would have nearly no neighbors, and vice versa. Even in the middle case (which I assume the worst), this should still limit the algorithm's O down. a little.
or so my gut tells me. heh.
Re:Basis Transforms (Score:2, Interesting)
Re:Language of Choice (Score:4, Interesting)
I'm sure I'm not the only one working in the industry that's had to deal with poorly educated fresh out of college employees. Kids that only know one langauge, and one way of doing things.
OTOH I don't believe I learned much from college, it was the reading and coding I did on the side.
I wish when kids chose CompSci as a major, the first thing they got was a copy of Knuth, Godel Escher and Bach, the Planiverse, and the Turing Omnibus. (There are obviously others I'm leaving out for instance Programming Pearls, Hackers, ext.) I think it would go a long way towards a better Comp Sci education.
Re:Language of Choice (Score:3, Interesting)
I might add that nearly all of the C++ guys were x86ers. Among the prefix notation/parenthetical set of students, there were a lot of school-of-Jobs fanatics and I-*heart*-Woz shirts.
Or was I imagining it? Anyone else find this to be a reasonable thumbrule?
Re:Fascinating reading (Score:2, Interesting)
I'm sure you know that the skills you demonstrated in the contest are only a small part of the skills needed by a professional coder. I'm also pretty sure you'd make a great coder. On the other hand, based on what I've heard about you, I suspect you're too smart to be just a game programmer or something like that, and that better things are in store for you. Of course, coding is still a lot of fun, good preparation for management or research, and a decent profession. Whatever you decide to do, thanks for stopping by on Slashdot, and best wishes.
Re:Language of Choice (Score:3, Interesting)
1. Little popup that puts up the red button to enter the competition areas has the bottom line (warning about DON'T CLOSE THIS WINDOW!) chopped off.
2. Actual coding window when scrolling upward has graphic artifacts and you must highlight the scraggly area and dehighlight to make it look good.
3. Went back later, window with red button hasn't gotten as far as displaying the red button (only displaying "Java stuff loading" or whatever. Half an hour and counting.
And I'm not even looking for problems. They're leaping up and barfing in my face.