New computing contest season

<p>USACO has announced the schedule for their 2004-2005 internet contests. The first round will be the first week-end in Nov. The most noticeable change from last year is that there are now 4 divisions, so everyone from novice to expert prgrammer can compete. Languages include C/C++, Pascal, and Java. They have also recently expanded the interactive training pages to support all 3 languages. </p>

<p>USACO is is a great program! The contests and training material are all free. Anyone in the world can enter, even if your school is not interested. In addition to the opportunity for programming glory, you have a chance to win a free training camp in Colorado Springs.</p>

<p>it's in Colorado Springs this year? that's cool. Ya I'm brushing up on my algorithms right now, good luck to your son.</p>

<p>Penguin - Yeah, the plan is for Colo Springs to be the regular site, although last year they were not able to get the dates they wanted for the dorms at the Colo College, so they went back to Wisconsin. They went white-water rafting at the end of the 2003 camp in Colo. That was a big hit, so they'll probably try to do it again. Good luck to you!</p>

<p>People who enjoy programming should take a look at USACO even if you don't think you have any chance at camp. The contests are fun, and the training material is really great.</p>

<p>I'd consider participating, but I'm afraid that the contest doesn't allow ML, Scheme, Haskell, or any other remotely modern languages. (google them if you wish, there is a whole slew of cool stuff associated with these languages, e.g. it is trivial to write a parser and interpreter for a rudimentary subset of a full blown programming language in at most a day or so, or probably even in one sitting!). </p>

<p>Out of curiosity, what sort of formal background in CS do most of the serious participants have?</p>

<p>the language isn't really important. The algorithm is the thing. You are not going to be writing stuff like parsers if you do usaco. That would be considered a menial task. It's about designing algorithms to solve problems. And the algorithm is completely independent of the language in which it is programmed. </p>

<p>The serious usaco participants usually have a very strong math background and are also very serious particpants in math competitions. The usaco problems are very mathematical. Many of the top usaco competitors also qualify for usamo. The americans who do usaco almost all program in C/C++, both for competitions and in their general prgramming. (That may change with the ap exam going to java.) Interestingly, the Europeans usually use pascal.</p>

<p>I would hate solving USACO challenges with those languagues...maybe its just because I'm accustomed to C++. They have a new Java grader if you want to try something more "modern". As far as "formal" CS experience. I guess I would include AP CS A and training for UIL Computer Science for myself, but the USACO pages have helped me far more than anything else. Check it out.</p>

<p>yeah, writing a recursive descent parser for a Scheme subset is pretty easy. However, while an algorithm itself is language independent, its implementation isn't (try doing something with DAGs or other singly linked datastructures in a language such as C++ that lacks a garbage collector).
From what I saw of sample IOI problems earlier this year (I was bored), they don't involve designing fundamentally new algorithms so much as adapting the underlying principles of preexisting ones. Especially in the case of the ones that seemed to be akin to the travelling salesman and some manner of scheduling/optimization algorithms, which are good problems to have in a contest considering that those problems have very bad asymptotic complexity in the general case.</p>

<p>texas, have you yourself been a participant, as you seem to be very familiar with it.</p>

<p>Having been to USACO camp and to the IOI myself, I can speak with some authority on this topic.</p>

<p>Yes, some algorithms can be more naturally expressed in one programming language than in another, but the basic algorithm is the same. The comment that implementing some data structures in a language which lacks a garbage collector can be hard misses the fact that you can almost always <em>statically</em> allocate all data structures for USACO and the IOI. Just allocate a block of nodes and have integers indexing the next node. You're given the maximum test case sizes, so this is very easy.</p>

<p>The kinds of programs one will be programming in USACO are ones which can be programmed quite reasonably if you know your language well. There's no parsing, almost no need for dynamic memory, and programs are generally fairly short. Admittedly, if you're used to programming in a functional programming language, it may be somewhat different doing USACO in C, C++, or Java, but I encourage you to try it anyway. (You can always email the USACO coaches and ask for your language of choice to be supported, but don't expect anything.)</p>

<p>Lastly, as to the nature of the problems themselves, while it is true that DP, network-flow, Dijkstra, convex hull algorithms, etc. will be your bread and butter, so to speak, it's by no means clear how to adapt, apply, and combine these basic algorithms, together with your own insights, to construct a solution. And, of course, DP is just a technique, not an algorithm. It's really quite similar to the math Olympiad, where yes, you need to know and use Cauchy-Schwartz, cyclic quadrilaterals, etc., but where these form only the basic elements of a solution. Actually creating the solution is up to you.</p>

<p>I'm not sure which IOI problems you've looked at, but they may have been "sample" problems drawn from the practice competition, which serves only to get familiar with the grading system. It you'd like to see some real problems, the problems from this year's IOI (which I warn you was somewhat easy) are at <a href=""&gt;;/a> . There's a link to the second day at the top. My personal favorite problem of the contest is Empodia, from the second day (although the ISC made the test data much too easy except for the last test case).</p>

<p>Another good example of how the solutions to the (highest division) USACO problems aren't just obvious applications or modifications of the basic algorithms is "selfmilk", from USACO camp 2003: the cows have a new milking system whereby each cow, at some point during the day, will enter the barn and hook herself to the milking machine, stay for some interval, and then leave. Farmer John knows when each cow enters and leaves the barn, and has a number of sensor readings of the <em>total</em> amount of milk being produced by all cows in the barn at various points in time throughout the day. The task is to determine a consistent set of values for the amount of milk produced per unit time by each cow, or to determine that the information is inconsistent. (I would like to point out that simply setting up a linear system, and solving it using Gauss-Jordan, doesn't work. The reason is that the cows' milk production rates must all be positive.)</p>

<p>In any event, I strongly encourage you to give USACO a try! The upcoming qualifying contest will have a range of problem difficulties (without any <em>really</em> hard problems), but for the later contests you'll be in a division with problems suited to your level.</p>

<p>hmmm, those problems in that link are pretty interesting. Now if only I had a large block of time to just work on them, which I doubt I ever will have. </p>

<p>If, as you say, there is a minimal need for dynamic memory allocation, then I guess my complaint about the relative merits of programming languages in these competitions isn't valid.</p>

<p>are you still in high school,"gauss-jordan" ?</p>