Monday, August 15, 2005


Recently a friend of mines introduced me to the world of pure programming competitions on TopCoder. I'm not really the fight-at-all-costs type, but I've to say that I like the idea. I tend most often to see the battle (in chess, or in karate, or now in programming) as a fight against imperfection more than as fight against someone else, but I regretfully discovered that looking at standings to see where I ended up is an important part.
May be indeed that in addition to a fight against imperfection there is a component that is the fight against all others, a fight for distinction (but never a fight against someone specific; even in chess I don't see my opponent as an enemy, and this is probably one of the reasons for which I'm not that good).
Anyway I found myself much weaker than I would have expected ... I need to get better at coding (deep inside I know I'm #1 hehehe).
There are parts of TopCoder that I don't like but still it looks to me a wonderful system and a pretty cool way to exercise. It's not like real coding, of course, but I think it's good. A lot of the emphasis is on the speed, but write incorrect code and you are simply out, as you should deserve.
Also it's funny the challenge part where you are allowed to kick out opponents by proving their solution is incorrect (I don't think this happens often, the submitted code will go through a more serious test anyway so there's just no point in submitting a wrong solution - unless you happen to have a fake account and kick it out from a real account to gain points).
I don't like there's no premium for readability and hence the top solutions are sometimes snippets that would get your ass fired being me the one in charge of quality control, but it would be difficult to place an objective measure for readability (readability depends on the reader, probably it's just that I'm too dumb to understand those programs).
Oh... I would have loved to be surprised on another aspect, but it didn't happen. As one could probably guess there is almost no girl even there. It's because of the fight or because of programming ?


Davide Pasca said...

Ummm.. I've already lost. It's late at night, I tried to click a few times going by intuition and I stopped when it asked me for username and password.
I wish I could have seen a piece of code.
In any case, if you aren't faring well I doubt I'd go anywhere. I still have to buy the Knuth !!
I often code and feel very lame, so much experience, yet not feeling comfortable at all (especially when I go out and experiement with C++).
I suspect that those that do well need to be somewhat trained for doing well in that kind of environment.. possibly some sort of specialization much like it already exists in every field and sub-field.

..yet.. to set for yourself a goal to do well in that field, could certainly be positive. One may end up becoming a wizard at finding pieces of code with search engines, or even to actually become accustomed to solving certain types of problems... which is what productivity really is.. to automate a process, or automate the process of finding the process to automate in this case 8)


6502 said...

You can code in either C++/C#/Java or VB.NET; the problem is often finding the correct algorithm and sometimes just writing a very simple function. For example in one case was asked a function that given the lenght of a movie as a string "HH:MM:SS" and the desired size in megabyte asked to compute the bitrate in kbit per second. There's never OOP but always just a function that given certain parameters should return prescribed results. Sometimes the computation behind is however rather complex (often there is some kind of dynamic programming or recursive search required) and there's also a limitation on total execution time.
For an example of a rather complex one in one case the function was asked to return the "square root" of a permutation (i.e. a permutation that applied twice was equivalent to the input permutation). Somehow I think that either you know the problem or at least some theory behind it or it's very difficult you can find the solution in one hour by yourself. Knuth here helps.

I think you should give it a try... there is a practice area where you can exercise with past problems and the site is technically ok. Just stay away from (note the final s) that has nothing to do with it; they're just trying to make a living from a similar domain name.

If you get over your deep hate for C++ strings and vectors i think it could be fun for you too. Anyway you didn't hate java after all, you can use that instead.

I passed the first selection for TCO2005, now it's where the real fun begins. The bad part is that in the lucky case I pass also next stage (the first online round, used to filter from 750 partecipants to 400) I'll have to set up an alarm at 3am to fight in the second round (400 to 200).

Think to it as kata for programmers :-)

PS: If you register put "6502" as referral code, I'll get part of the money you win ;-)

PPS: Many are from china, but very few from japan...

Davide Pasca said...

Kata for programmers eh ?
When I was very young I did one kata competition. I went on the tatami and completely forgot the moves !!
I had to come back later. Eventually got the bronze medal at least 8)

That summarizes my view of those challenges. A view which is probably tied to a personality which is innate or already developed at an early stage.
Plus, I get enough challenges at work to remind me how weak I can be when I comes to race outside my field.

I bet that some of your sneaky Chinese counterparts are sitting on a stock of books with N PC open on N search engines, Possibly even grouping, who knows !
I can imagine that there aren't many Japanese. Japanese study English in school and are actually obsessed with the ability to speak English. However, at a practical level they don't need it, because they are spoiled with a wealth of material. In the bookstore I could find several interesting books, but unfortunately they were all translated for the local popoulation 8(


6502 said...

I said kata because that's my view, others could think to it as a sort of group kumite :-)

Anyway a few of the problems are indeed very complex and unless you "sit on a book" IMO there's no way you can solve them; this is however a part I don't like much (but admittely the knowledge of theorized algorithms is an important weapon for a programmer; when faced a problem it's not that easy to find the proper words to put in google, and also often "real" problems are variations on the theme, not just the standard well-known algorithm).

I tried a few of the problems from past edition of the tournament and looks like it won't be that easy from now on. Oh well... IIUC I already won a T-shirt... yippee

Back to real stuff we had some more interview in these days and the sitiuaton about IT in italy is not bad. It's desperate. Last candidate is about to get a master in IT and wasn't able to reverse a C string in place... it even managed to call "getchar" (sort of, he wrote things like "getchar(s)"... whatever that is supposed to mean). The prototype for the function to write was "void reverse(char *s)". The very same guy apparently a few months ago passed a C programming exam writing in two hours a dijkstra min path finding implementation (including using an heap to keep the algorithm fast).