Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Education

ACM World Final Standings Posted 184

Posted by emmett from the think-globally dept.
Nyerp writes "The final results for the ACM International Collegiate Programming Contest are up. Cheers for St. Petersberg State U, followed by my own school, the Univerity of Waterloo!" Congratulations, guys! I wonder if any of the world finalists used Pascal, since it's allowed.
This discussion has been archived. No new comments can be posted.

ACM World Final Standings Posted More

ACM World Final Standings Posted

Comments Filter:

  • Re:Cool. Another "place." (Score:1)

    by Anonymous Coward
    I too was on the CMU team, and I'd like to add my 2c.

    I can first of all confirm what Dom said about practicing. In fact when an IBM rep asked us at the regionals how much we practiced for the contest, all three of us simultaneously started laughing.

    I believe that practice makes a big difference in this contest. This is because you need a bit different set of skills to be really successful in this contest than you do to be a good CS student. Take a look at a contest problem, how fast (the operating word being FAST) can you determine what algorithm to use (or come up with one) to solve it? This is mostly in line with what you need to do well on some of the CS exams at CMU.

    Now though, how fast (the operating word again being FAST) can you correctly code this up? And when what you were sure was a correct solution comes back from the judges with the informative message "wrong answer", how quickly can you find and fix the problem? Being able to code very quickly is not something I found to be at all necessary for academic success in my 3.5 years at CMU. I do think that this is a skill that can be greatly improved with practice.

    There are other contest specific issues, like being able to manage the computer time - you biggest limiting factor, being able to work well with your team, having a booklet of algorithms implemented in C in as few characters as possible (you are allowed books, notes, etc).

    I don't want to take anything away from Univ. of St. Petersburg, or Waterloo, or any of the other teams that put a great deal of effort into preparing for this contest. I salute them, that's what it takes to be champions.

    I can surmise that the reason that CMU does not put more effort into this contest is that 1) we do ok anyways; 2) CMU does not really need this contest to boost its reputation. On the hand, Waterloo for example is much less known, and can use the tremendous success they've had in this contest over the past few years as a big selling point, and a way to get more exposure.

  • My problem with the contest (Score:1)

    by Anonymous Coward
    I think that this contest does not necessarily emphasize the right programming skills, and that great performance on this contest is not indicative of being a great programmer.

    In fact, I'd go as far as to say that practicing a lot for the contest is probably more detrimental to you as a programmer than beneficial.

    Allow me to elaborate, here is the right and the wrong way to do a contest problem:

    The WRONG way
    You spent a great deal of your time planning out how you are going to solve the problem. You keep copious records of all your design rational and tradeoffs you considered along the way. When you do solve it, your code has a beautiful OO structure, filled with design patterns, and copious comments. You variable and function names have long descriptive names. You use elegant data structures, together with efficient algorithms, guaranteeing good performance both in the average and worst case (whether this is in real life or asymptotic terms and why is explained in detail in your design notes).


    Your code is extensible, reusable, modular, and most of all maintainable. It easily generalizes to other problems of this type. It does extensive error checking, every function parameter is validated, every exception is caught, every effort is made to insure that there are no resource leaks (memory or otherwise), even under most strenuous of circumstances. Its very well tested, and you have great deal of confidence in your work.


    And now The RIGHT way
    As soon as you are marginally sure you have an idea of how to solve the problem you start hacking away. You use as few functions as possible, with as many global variables as possible. You rarely have any function or variable names longer than 3 characters, if you do those probably have names like "asdf", or "dfjk" (easy to type). Unless its REALLY inconvenient you store all your data, no mater what it is, in giant global arrays of int's, each one of them bigger by at least a factor of two than it needs to be (wouldn't want any index overruns). You don't concern yourself with performance unless your first submission comes back with "Ran too long". You don't concern yourself with stability unless your first submission comes back with "Runtime error". As soon as your program works on the sample input, you submit it.


    Wait a minute now that I think about it...hmm...with time to market and all...well, maybe this contest is a good measure of how good a programmer you are.

  • Cool (Score:1)

    by Rasmus ( 740 )
    I did my time at U Waterloo as well. Systems Design Engineering, 1993.

    -Rasmus
  • Quite a few years back, I had participated in the undergraduate version of this, just at the regional level (didn't make it to the world finals). I remember getting really mad over faulty information in the givens for one of the problems. It caused us to fail our solution several times over, and since they aren't allowed to tell you anything other than "wrong result", we couldn't tell what was wrong.

    Part of the problem involved having to find the value of N!, where N could get up to a max size of M (I can't remember the exact numbers anymore). You were supposed to tally how many times each digit appeared (assuming it is represented in decimal) in the resulting number. The point was that the good programmer should immediately recognize that there was no way to solve this problem using the built-in binary numbers on any computer, since it required that you store long numbers with perfect accuracy (so floats are out too). So the point was to quickly whip up a string-ized number format, and implement a multiplication routine for it so you could do large factorials. Pretty simple and routine once you realize that you will have to do this, right?

    Well, it *should* have been simple, and it *would* have been if it weren't for the fact that the problem's givens lied to us about how many digits were in M! (It was given that M! would be the largest value in the test data, and that it contains no more than XXX digits.). They said too few digits, and as such our array was too small to hold the result. Our algorithm was actually correct, excepting this one mistake, within 10 minutes of the contest's start. And the rules of the contest prevented us from getting any clarification about what was failing in our test submissions, and there is no way to quickly check if the givens were correct, since you can't calculate what M! is in reasonable time when M is big. (Not without a program - which is what we were making). Besides, since they were givens, we shouldn't have *had* to check them. I was in a funk for a week after that because it wasted too much of our limited time and we had it *right* dammit, from the first 10 minutes. The mistake in the givens didn't get publicised until after the contest was almost over, and we'd already squandered away our time on this one problem that we knew we were this close to finishing.

    That was a long time ago, but it still irks me. That one mistake kept us from going on to the next level of the contest. If that given had been correct, then our first submission, 10 minutes into the contest, would have given us enough total points to go on to the next level. (It was one of those years in which even the best finishers only got 2 of the problems right.)

  • Certainly some motivation to enter into education or an -ology where all the girls are at, (and the good lookin ones too, definately not enough of those in computer science.)
    So that's why there are almost no girls in physics, but there's lots (and good looking at my university, too. :), in biology: Physics doesn't end with ology. Damn :(. OTOH, there are girls in chemistry. At the Canadian Physics Olympiad, 1997, there were 15 guys and no girls. The Chemistry Olympiad, at the same cegep (sp?) in Montreal, had 8 guys and 7 girls, IIRC.
    #define X(x,y) x##y
  • I think the reason that UCF gets overlooked for funding is because of the amount of FSU/UF grads in politics. Though, UCF gets a ton of money from the private sector.

    Unfortunately, we won't have a first rate sports program until we build better facilities for our athletes.

    But, things are changing and UCF is growing. Unlike UF and FSU, there's plenty of room for us to grow.

    There's a picture of the scoreboard at Florida Field from the UF/UCF football game from last year. KNIGHTS 7 GATORS 0. (of course, its in the first quarter and there is 12 minutes left.)

    Go Knights


  • Here is my comment:

    1. Why Java?

    I understand that Java is the rage nowadays, but why Java?

    Java is defintely NOT something that will last. Java is not a FREE language, it is still in many ways controlled by SUN.

    Unlike C, C++ or Pascal, one day Java is still under Sun's control, one day Java is not FREE.

    I rather see the ACM contest use python and/or perl than Java.

    2. Language.

    I understand that to ease the judging process, the English language is used.

    But if the competition is to open to the whole world, wouldn't it be better that the contest be available in other languages as well?

    Imagine that you are not an English speaker, and there are certain things in English that you may still have problem with - even if you are a top programmer - the problem of mis-understanding the question may hamper the competitors' ability to complete his/her/their project, as well as they should have been.

    As I understand - and I am a member of ACM as well -, the ACM is made up of people of all ethnic groups, and there are MANY people from ACM that can be used to help out in the translation process, in problem texts or whatever that needs translated.

    I hope that in coming years, the ACM competition will offer contestants a choice of either using the English text, or language of their own choice.

    In this way, the competition would be fairer, get rid of the language problems, and you may have a better-run programming (computing) competion.

    Isn't that a COMPUTING competition is all about?

  • Perl is a great language. The stuff that you can do is just great. I don't think that one would have been an option :(



    http://theotherside.com/dvd/ [theotherside.com]
  • Hi all,

    My high school's going to be attending a similar contest (on a smaller scale, of course) at Stetson University, in Florida. Hopefully, I'll be placed on the team. Does anybody with experience with these sorts of contests have any tips for us? Information on how best to coordinate a team, reference books to bring, documents to read before hand, etc.?

    The main hurdle I see is that fact that only one workstation is available for the entire team, which is definitely awkward.
  • Did you ever hit reply, and leave for a long time?

    I can't remember what I was going to say, or what I was replying too.

    =/


    -- Thrakkerzog
  • I'm involved with the programming team here at Notre Dame. We actually went to the regionals, which for our region were held at Waterloo. The guys at Waterloo rocked.

    Anyway, some advice:

    • read over all the problems at the beginning and find the easy ones fast. It's important to get those done first, because that'll help your score a good deal.
    • practice as a team. Ideally you'll want to download a sample problem set from somewhere, limit yourselves to a few hours, sit down at one computer, and get used to the whole scenario. The biggest problem our team had was a keyboard bottleneck. I had written up on paper code to solve one of the problems, but didn't get enough keyboard time to debug at the end. When all was over and I was back home, I downloaded the code I'd been working on, and it took me about 10 minutes and 5 lines of code to get what I was working on functional. Those 10 minutes would have made the difference between us getting 3 problems right and being in sixth, and getting 4 problems right and possibly getting third place and going to world. This was the first major programming contest for the three of us on our team, so we hadn't practiced using one machine amongst three of us, and it takes some getting used to.
    • If you're allowed to bring in printed materials, I'd recommend not bringing too much, you will probably want to limit yourselves to a good algorithms book, a calculus book, maybe a geometry book, and maybe printouts of man pages for useful C functions.
    • Be comfortable with manipulating numbers in different bases, sometimes problems throw a problem at you where input isn't in base 10. If you know how to handle this, it won't be a problem, but if you don't, you'll waste time...
    • realize that the data sets they test your program with will probably be much larger than the sample data sets, so even if your program seems to run fast, it may not. It doesn't hurt to know basic complexity analysis. I saw a recursive program once that ran quite quick on a sample data set, but after some simple complexity analysis I realized it would run for 10^30 years on a larger data set.
    • Don't underestimate the powers of the modulus operator (% in C).
    That's all I can think of right now. A really good source for sample problems is on Waterloo's webpage: http://plg.uwaterloo.ca/~acm00/ [uwaterloo.ca]. Also feel free to look at the page I maintain for the ND programming team: http://prijks.esgeroth.org/puters/acm/ [esgeroth.org]
    I'll stop now, I think.

  • Hi everyone! I figured while everyone was checking in and patting our friends from Waterloo on the back, i might as well join in too. Congratulations to Donny, Jeff, and Ondrej!

    I did the contest once, but there are no memories of the math building's comfy lounge for me: I graduated from Computer Engineering at Waterloo in 1998. 1994 was a fun year: we went with united forces from CS and Engineering and kicked butt [baylor.edu]. Those ACM contests are really fun, though i agree with the others that judging errors do suck and some accountability would be nice.

    I've known Donny from a long time ago... [sjr.mb.ca]

    -- ?!ng

  • The Unversity of Central Florida [ucf.edu]. We've been doing the ACM for about 15 years now. Regularly win our regionals or place in the top 3. We are also considered a top 25 school for Electrical and Computer Engineering according to the College Board (the SAT/GRE "guys").

    And there we are, #15 this year (out of >>2,000 teams) -- right next to MIT, Carnegie Mellon and Virginia Tech. Plus, a brief history of UCF's world rankings ...

    • 1997: #16 (out of 1,100 teams)
    • 1996: One of the 43 world contestants (out of >1,001 teams)
    • 1995: #19 (out of >900 teams)
    • 1994: One of the 35 world contestants (out of 628 teams)
    • 1992: #7 (out of >600 teams)
    • 1991: #16 (out of >500 teams)
    • And plenty of world rankings in the '80s (world rankings prior to 1991 not available on-line).

    But people in Florida spit on us and, until recently, we used to get 1/10th of the funds of UF or FSU. We have more programs and students than Florida State (let alone 10x the graduate programs) and are barely behind Florida! Add in the fact that we have the 2nd largest research park in the US and it makes me wonder.

    It wasn't until our Football team moved up to I-A (in 1996) and started playing big schools (and nearly beating them) that we finally got some money proportional to our size. Very sad that sports seems to drive everything.

    Again, no respect!


    -- Bryan "TheBS" Smith

  • I could just imagine how good these people who won are if my group didnt even make it through the regional competition. They must be getting job offers like crazy... And if they arent, they should.

    _joshua_
  • Yeah, and my team (U of Guelph) beat the Waterloo B team at the East North American Regionals in November.
    Maybe next year we'll do some preparation and go after the A team :-)

  • I competed on the University of Alberta team in the '98 and '99 finals. Congratulations to this year's team!

    Here's a few quick hints:

    • Have a firm grasp of standard algorithms (shortest path, max flow, etc.) Bring printouts.
    • An excellent source for sample problems may be found at http://acm.fi.uva.es/ [fi.uva.es].
    • Practice both individually and as a team. Decide in advance how you will share the single terminal. If you can't find a bug within a few minutes, print out your code and let someone else have the workstation.

    Good luck!

    - Adam

  • The Guelph team did not beat either of the Waterloo teams, as it solved only two problems. Read the standings for the East-Central North America Region programming contest [uwaterloo.ca].

    Michael Van Biesbrouck, ECNA Regional Contest Director (1999)

  • I don't believe that any Dutch teams made it to the 1999 finals in Eindhoven. It was a nice contest, however.

    Michael Van Biesbrouck, 1999 ECNA Regional Contest Director

  • The contest has been sponsored most generously by IBM for the past three years. Microsoft software was never required at the regionals (my region has used Unix for all of its contests in recent memory). When I went to Microsoft-sponsored finals (1996) the version of Pascal was from Borland. The following year the Pascal at the finals was a Microsoft beta product.

    Michael Van Biesbrouck, ECNA Regional Contest Director 1999

  • If you write `AA->B' as `B->AA' then this problem becomes a fairly straight-forward parsing problem. You can use any general-purpose CFG algorithm for this without taking advantage of the nicer aspects of the problem specification.

    I don't see why you have a circular order ordering on the letters.

    Michael Van Biesbrouck

  • At the last finals, the Regional Contest Directors for the contest were asked to vote on removing Pascal from the contest finals. The motion was not passed because many of the European teams are from countries in which it is not practical to run regional contest on modern machines. A posting for this article indicates that in the previous two years, St. Petersburg used Pascal and did well at the finals.

    In my own region (East-Central North America, home of Waterloo, CMU and Toronto teams), teams using Pascal tend to do very poorly even though the problems are set with the limitations of Pascal in mind. Unfamiliarity with the region's supported versions of Pascal probably contributes to this problem, but I think that the main issue is that the teams choosing to use Pascal are less experience programmers than the other contestants.

    I am not familiar with the advantages that Delphi provides, but I feel that teams who are extremely familiar with C++'s STL and Java's bignum libraries will have improved chances at winning.

    Michael Van Biesbrouck, ECNA Regional Contest Director, 1999

  • Waterloo won the Putnam too.

    http://www.bulletin.uwaterloo.ca/2000/mar/20mo.h tml

    Notice Donny Cheung in 1998,on the UW ACM team this year and another UW student won the special award for the highest-scoring female student in the contest.

    http://www.stats.uwaterloo.ca/~cgsmall/uwput.htm l

    Go waterloo go.
  • That explains it all.
    I was a member of the swedish team (from Linköping University) and we also got stuck Problem F, which was the first problem we attempted to solve. I guess we spent half of the contest looking for a non-existing bug.
    The results would have been completely different if the test data had been correct.

    Anyway, we really enjoyed our free visit to Florida!
  • The beauty of a sexy built-in "string" type

    Uh, wasn't Pascal the language where two strings of different lengths were considered to be of different types?

    If that's sexy to you.... shudder
  • Like the friend of mine from high school who not only got a free ride from VA Tech (go Hokies!) but also a matching free ride from No Such Agency and guaranteed employment after graduation.

    Haven't heard from him in a while, but that's prob'ly more my fault than his. Brad Banks, if you're out there (at Fort Meade or elsewhere), hope you're enjoying yourself! :)


    ------------------
  • I fell behind in my studies and dropped out of the Univ of Minnesota in '92 after ~2 years of CSci. I worked up from the bottom of IT - junior operations. 2 jobs and 5 years later, I got a programming job, and that was because my friend's father ran the shop. I got lucky. I now work for a Fortune 500 software company making good money.

    The market has changed since I dropped out. You may be able to get an entry level job in software development with only 2 years school. It will be hard, and it may not be your first job..or your second.

    I've worked for 2 software companies: a start-up with 30 people and an established enterprise class software corp with more than 7000 people. Neither company would even consider someone without a degree or experience.

    Finishing the degree is what you will wish you had done when you turn 30. I sure do.
  • I showed some prospective Waterloo mathies around the 3rd floor on Campus Day

    They were so disappointed when I told them that they would probably *not* be using the cute iMacs for their courses, and did not quite believe me that they'd switch over to Unix (!) in their second CS course and never look back...

    "Unix?? Ack!" -- frightened look --
    awww.. so cute.. so innocent.. just ripe for assimilation into the Mathie collective.. ;)
    (yeah, off topic, i know, i know)
  • Ah, but starting next year (or is it this year?), even Modula 3 will be replaced with such atrocities as Java and C++ in first and second-year Waterloo CS courses! We cannot allow this carnage to continue!

    now, how am I going to resell my Modula-3 text?!! (the eminent Harbison)

    .. forty-odd bucks worth of fireplace fuel? even looking at it gives me hives... i know it's not as sexy as pascal, but.. hey, wanna buy it as erotica literature? ;) come on, first 30 bucks takes it!
  • Here in the Netherlands the students organize themselves in teams, and then participate in local contests. The team that scores best goes to the regional. I don't recall any ACM final without dutch participation, so this seems to work pretty well (I must say I haven't really checked the last few years).

    I've participated in the '92 and '95 ACM Finals, scoring 9th and 3rd place. Not so bad I think :)
  • It sucks, it sucks, it sucks.

    But it happens all the time in these contests. I think it should be considered part of the game. (And the Waterloo guys were so bright to realize what was happening here...)

    In one regional I participated in, the judges found out afterwards that the home team had been denied a correct solution. In the end they were awarded a wild card and were admitted to the finals. I think this was unfair, because other teams would never have gotten access to the right information.

    If I'm not mistaken, all jury data is destroyed at ACM Finals immediately after the Final Standings have been made up. There's something to say for this. But I know how you feel (I probably missed the '94 finals because of similar mistake).
  • Correct.

    One (obvious) consequence is that it is important to solve the easiest problems first. For example, if you end up with 6 solved problems, the number of minutes between the start of the contest and the moment your first correct solution was submitted, is effectively multiplied by 6.

    Now look at the final standings of the '95 contest. The top two teams are divided by 3 minutes, each having solved 6 problems. That's equivalent to say taking 30 seconds to open the envelope with problems at the start of the contest.
  • We give the characters A,B,C,D,E a 'circular' ordering. I.e., B follows A, C follows B, ..., A follows E.

    As input we get a string of at most 20 characters picked from A,B,C,D,E. Allowed substring substitutions are of the form AA->B, AA->E, BB->C, BB->A, etc.

    Required output: a list of the single letters that the input string can be reduced to.

    For example, BBBB can be reduced to B,D and E:
    BBBB->ABB->AA->E
    BBBB->ABB->AA->B
    BBBB->CBB->CC->D

    Exponential algorithms are easy.
    Anyone know a polynomial algorithm?
  • Rijksuniversiteit Groningen participated in 1999, so that year is covered. However, it seems that 1998 went without Dutch teams.
  • I forgot to explicitly refer back to the circularity. What I mean is that YY can be substituted by either X or Z, where X immediately preceeds Y, and Z immediately follows Y. But that's probably already clear.

    I'm just a mathematician so I don't know a lot about context-free grammars. For a given CFG, does there exist a cubical algorithm (in the size of the input) that accepts the CFG?

  • typing speed and accuracy are not particularly relevant. the programs typically arent very long (200 lines is about the most ive seen, and mine are often &lt50) and the compiler warns you about almost all typos. its much more important to identify the correct algorithm for a problem, and to see the nasty special cases that arent spelled out in the problem spec.

    and i was offered a job at the contest, actually... ibm was implicitly the only recruiter, but an old friend of our team came to cheer us (and his hometown team, gatech) on, and offered all of us jobs. he says what his company does is rapid prototyping and on-site tweaking to said prototypes, and that it is not unlike contest coding.

    efficiency is important in contest code, although maintainability is frequently neglected. and you say "some test inputs" as if to imply that the programs are not well tested... try it some time, the judge data is usually very good, if not literally exhaustive. (and occasionally doesnt meet the problem spec, GRRR)

    (i am on the ucf team fwiw)

  • Yeah, I went to HS with him. Brilliant guy, congrats Ondrej! (ask him about when he built circuitry to play pong on an old analog oscilloscope. It was a scary rats nest of wires, but worked )
  • Yeah, I was at aldershot, but I knew a lot of people from Nelson (some of which are here at Queen's). You might have even had my mom as your teacher at Tuck
  • But ever notice how no one ever gets any respect when hooking up a huge network of computers? Sure, programming is a very skilled way of thinking, but with networking you have to plan out the next few years worth of growth into your first setup. No time for "betas" here... Why couldn't they have a big prize giveaway for people that mapped out a huge and efficient network?

    Just my $0.02
  • Wow. Look at the takeover by non-US teams. This contest has been going on for a very long time, and I was involved for a couple of years a while back. Came in 5th one year, and 8th the other, if I remember correctly. And almost all of the top teams were US universities at the time (I think Eindhoven was there and was the only foreign team that did consistently well).

    So what has changed? Several things that I can think of: it was always an international competition, but I don't remember this many non-US teams in the past. In particular, when I was competing, the Berlin wall was still up, so we didn't have any eastern European or Russian teams! But even the non-US teams that were there were typically not very strong -- in particular, at that time many schools outside the US simply didn't have the facilities for people to be as experienced as people from US schools. I would imagine that has changed substantially, and non-US teams are now getting plenty of experience before coming to the competition.

    Lastly, is it really that the non-US teams are getting that much better, or have the US teams lost something along the way? Cal Tech has always been good (beat my team both years I went, anyway), and they only got 4 problems, while the winner got 7? That's just not at the same standard they used to work at. Is the education failing these days, or are we not getting as many strong students in Computer Science as we used to?
  • Having done both (admittedly more programming), I disagree. Doing network design always got more respect, because management saw the dollar value of the hardware and line costs. So why did I go back to programming. More fun, less beepers.

    But seriously, software is the heart of both computers and networks of computers. And there are so many ways of solving a problem with code. It's inevitable that there would be contests.

    I can think of a good network test. There are certain routers I have used that could provide material for a contest. Just try to get them to work!

  • Prizes (Score:1)

    by achan ( 69519 )
    I notice that there are no teams from British Columbia... which is sad... I'd never heard about this contest until now, while i'm in my last year of school...

    Does anyone know what the prizes were? I won a "software package and trophy" from IBM a few years ago and they sent me an outdated program that was no long supported and was barely functional without IBM hardware :)
  • Why are we mocking Microsoft in a post about a college programing contest. This is a joke , and it isn't even funny. I am not a judge of humour but, this comment is totally off topic.

  • And this is the reason I am not a programmer. Enjoy yerselves, boys and girls.

    -Steve
  • Looking at the North American team photos, I was struck by the narrow demographics represented... 1. Almost exclusively male. 2. Almost exclusively white or asian. Aren't there any black or hispanic geeks out there ? Or girlie geeks ? Why is geekdom so ethnically and sexually narrow ?
  • Yeah, I entered this contest. I didn't do to well, though. You know how, at the time, you think you're coding well but you think back to it later and you realize you completely screwed up?
    That's what happened here:

    #include <stdio.h>

    void main(int argc,char **argv) {
    printf("Hello, world!\n");
    }


    Despite the fact that this program didn't answer any of the questions given, let alone do anything useful, I didn't come in dead last. I beat... what was it? I don't quite remember. Microsoft something-something 2000....

  • I agree -- network admins don't get enough respect. But how would you ever test for it properly? I mean, mapping efficient networks is not something that can easily be quantified like programming.

    I suppose the real prize good network admins get is the nice little paycheques in the mail, and the stock options (if you're lucky). It will have to suffice! =)
  • Donny Cheung, one of the UWaterloo ACM members, was also a third of the UWaterloo Putnam mathematics competition winning team (which was held last December, the results of which were recently announced as well.) I guess it's just the difference between being able to solve problems, and just being a code monkey. Now I'm not saying it's something that can only be teached at a University (or something that can be taught at all) but I certainly hope people recognize that the difference between a mathematical CS education and a 6-month "I can program in 6 different languages!" technical degree is significant.
  • ...but apparently they can't teached grammar and HTML formatting. furrfu.

  • That's why Larry Wall is THE MAN!

  • Talking about the 3rd floor labs - it is irratating to see the Win98 and the iMac boxes eating spaces previously allocated to Unix terminals...and CS students aren't given accounts...and most of the time the boxes just sit there idle, wasting electricity...
  • (Yeah, I know it's off-topic, sue me.)

    Isn't the Computer Graphics Lab was in DC?

  • Wow, I've seen Donny Cheung in the hallways of the Math building, and never even recognized him... :)
  • Sadly, I feel that there are people who would like to see less mathematical content (e.g. removing multivariable calculus from the requirements)

    It's already happened. MATH 237 is no longer a requirement for CS. I'm not sure when it happened, but it must have been sometime before my first year. But it's still a great idea to take, it really opens your eyes to what calculus *really* is about (in a more general case than a single piddly variable :)

  • Okay, I guess you don't know how the scoring works. It's all based on how many questions the team successfully completes (any language, doesn't matter). NOT the quality of the code.

    However, if a submitted program does not satisfy the automatic testing (and specs), penalty minutes , equal to the number of minutes since the contest began, are added to the team's penalty total. The penalty minutes are used if teams have the same number of correct submissions.

    So first off, whoever has the most correct programs is the winner. If there is a tie, then whoever has the least penalty minutes wins.

  • In response to point 1 I agree. Given the way the contest is judged I think Python would be ideal - it can be vastly quicker to develop a working implementation of an algorithm in Python than it can in C/C++/Pascal or whatever.

  • Though I can't confirm that, it certainly makes sense. Although for the kind of programming I really enjoy, the math isn't /that/ beneficial, for the problems the ACM suggests, it's huge. Being able to think in three dimensions, think in terms of efficiency, proving code, etc., that this university (UW) really hammers on can only help for a contest like the ACM.

    -Sylvester
  • The only reason we'd be on the sixth floor is for Statistics (shudder) or Graphics (the lab is on the sixth floor. Most mathies hang out on the third floor, since that's where the bulk of the labs are, as well as the clubs.

    As for PoETS (or however it's spelled), I've been in there a couple of times. It might've been the times I've been in there, but it's not all that thrilling. I'm sure the hoardes of drunken engineers didn't do much for the ambiance, either.
  • I'm not sure how the other schools form teams, but at Waterloo we do it by holding local contests (usually in October), and having the top six people form two teams (the A and B teams). These two teams compete at the regionals and the best goes on to the finals.

    As for coaching, there's a professor here (Cormack) who handles most, if not all of, the coaching. I've no idea how much time is spent preparing for such things, but I've been under the impression that there is some preparation. Next time I run into some of the ACM people at school (I seem to know the bulk of the current and past contestants from Waterloo -- probably by hanging out in the Pure Math Club with 'em), I'll have to ask them how much training they do.

    Preparation -- speaking as someone who used to be active in various scholastic contests in high school, preparation can play a large role in performance. By doing old contests you get a feel for how the questions are set up and asked, and so when the Big Day comes, you've already got a feel for the whole thing. Still, preparation can only help so much -- you still need a fair bit of talent to do well.

    Anyway, just my thoughts on the issue.
  • (Hoo boy. Way off-topic.)

    Part of the overcrowding has to do with the renovations on the second floor -- all of the lab space down there disappeared, so the Macs and PCs came upstairs to the third floor. I've heard rumours from people "in the know" that the space will be reclaimed next academic year (F00), and some space on the second floor will be for undergrad.math terminals. It sucks, but it shouldn't suck next year.
  • (Off-topic and probably not of interest to non-UW people)

    I've seen a lot of people in MC, and been surprised later when I've found out who they were. Most of them I'd met online before, primarily in the uw.cs.cs* newsgroups (the course discussion newsgroups). I've a feeling the same things happened to others at Waterloo, as well as people at other schools.
  • Hope I'm not wrong in thinking that both schools with St. Petersburg are in the same city, but assuming I'm not this is quite a coup. I wonder if the city will honor them with a parade or at least a special mention from the mayor.

    Being YA Waterloo alum myself, I'm really proud of those guys too but having two schools in the same city place 1st and 4th is downright amazing.

    Also, congrats to all the teams to placed!
  • Delphi is allowed. Which is really just Object Pascal with a nice gui maker. Anyway all of the teams I know who placed well at Regionals used pascal. It is simply safer, and a whole lot faster to develop with. I like C/C++ as much as the next guy, but use the right tool for the job.

    Not to start yet another religious war here, but C and Pascal are, IMHO, more or less equivalent, especially for the kinds of problems they tend to use at ACM programming contests. The languages have pretty close to a 1:1 correlation on features.

    When I competed a few years ago, of the people I talked to there was a pretty strong bias towards C or C++. But there were also some good guys using Pascal, too. It's just a matter of which you were more comfortable with.

  • I remember my first CS course...CS 134. Ahh yes, the beauty that is Pascal. The beauty of a sexy built-in "string" type. The pragmatism of the "var" and "type" sections. Ahhh. Excuse me as I wipe the tears creeping down my flushed cheek...sigh... I'm so pissed that C eclipsed Pascal in terms of popularity. What a fabulously sexy language. And more importantly, the beauty that was the Borland Turbo Pascal compiler for DOS. Ohhh. The greatest compiler ever (Borland Turbo C for DOS was equally sexy). Unfortunately, the U Waterloo CS department forced us to use a Pascal-like language, Modula-3, for several of our subsequent CS courses. A sexy language in itself, but nowhere near as simple and elegant as Pascal... Mr. Wirth, you've done us proud. Well, me anyway.
  • But remember the B team has beat the A team at the regionals! 1997 I think?
  • I'm trying to figure out the timing of answers, I'm used to the contest publishing results showing the time/penalty when a problem was accepted. It can be interesting to note which problems were easy, how many minutes it took to get the first problem solved etc. Does anyone have a link to the full competition results?

    Also, is the 20 minute penalty per wrong submission new? I don't remember seeing this before?
    Ryan
    rjshook@uwaterloo.ca :)
    PS POETS is spelled like that, Piss on everything tomorrow's Saturday

  • The man? Yes. The language? No.

    I participated in the regional competition last fall. We used Pascal and finished 2nd in the undergrad division.

  • I loved those things in college. Of course my time usually didn't fair as well as we should have according to our prof. but hey we also tended to be a little hungover for the contests:) Programing to solve a completely pointless problem that uses some little tricky algorythm sure as hell beats sitting in front of some other guys C code, commented in Swedish, that runs a query on an oracle database and trying to figure out why the report doesn't work anymore. oh well just my worthless .02$
  • I looked at the first one and couldn't believe they said it took Knuth 30 minutes to solve the 2nd maze -- took me just a couple -- the secret, as I suspected, was to work backwards from the exit...

    If I came exited this node in this direction then I had to have come from this direction (usually there was only *1* possible one!)

  • Python has lots of cool built-in types: strings, lists, tuples, dictionaries (hashes), complex numbers ...

    Speaking of M3: I was in the Chapters on Bay/Bloor in Toronto a couple years ago and remembered they had two or three Modula-3 books. Truly weird. :)

    Paul

  • Yeah, they removed MATH 237 from the required list; you have to take another math course in its place though.

    So all the slackers go and take ACTSCI 221.

    This was when they changed C&O 230 to MATH 239. I really wish someone would write course notes that didn't suck for that course.

    Paul

  • My landlord here in San Francisco recognized UW solely because he used to deal with WATFOR.

    Sheesh. Like what have you done for me lately, baby?

    Paul

  • wow. rasmus was a syde. :) Paul 4A CS in S00
  • Well, I've known Ondrej since grade 7 :-) when he was winning national math contests.

    yeah, UW! :)

    How many other UW mathies are reading this thread? I also know Justin, who submitted the story. I'm surprised undergrad hasn't been /.-ed.

    Paul
  • can someone explain how the scoring system (penalty minutes) are calculated/ thanks. Paul
  • I remember all sorts of crazy stuff he did with HyperCard back at Tuck [haltonbe.on.ca]. He wrote some music composition deal, a couple of games, funky stuff.

    I went to Nelson ... I take it you were at Aldershot?

    Paul

  • Yeah, CGL [uwaterloo.ca] is in DC.

    Paul

  • I was kind of disappointed not to see CMU ranking high there, since I do have some school pride. Then I went to read the questions, and I was really disappointed. I think anybody who did decent in 15-212 (sophomore-level CS class) should have no trouble solving these problems. They are all pretty straight-forward, and I consider them pretty boring. When I mentioned this to a friend he said that in higher levels of such competitions it usually comes down to who can write the same code faster. I guess that interests some people, but I'm not surprised now that none of the "good" schools ranked high, since it's just not interesting. (For interesting problems, see http://members.tripod.com/~POTM/) Tim
  • I can tell you that practicing certainly helps. I competed in 98 and the team only solved one problem, then we started practicing every single day until the contest for 99 and tied for 18th (6th out of the US teams), so I can say that practice helps.
  • See their Mathematics Division [math.msu.su] information on the Faculty of Mechanics and Mathematics.

    The Faculty of Mathematics and Natural Sciences [leidenuniv.nl] at Universiteit Leiden has a somewhat similar organization, but I'd consider MSU a much better candidate.

    Note that St. Petersburg State University has a similar organization of having a Mathematics and Mechanics Faculty. [niimm.spb.su] It probably used to be called Leningrad State University back before "glasnost."

    I could go with either MSU or St. Petersburg as being "the ones." St. Petersburg has been doing very well in the ACM contests, which suggests that they are likely rather good.

    Whether that's from student selection ("nature") or quality of teaching ("nurture"), or some combination of both, is another question...

  • Too bad they couldn't all be that simple. The problem is that you could be allowed to travel in any direction when you enter a node, so there could be multiple paths through the maze. The wording of the problem implied that only the shortest path would be accepted. Your algorithm (a depth first search, starting from the destination rather than the entrance) isn't guaranteed to do that. I think they were referring to it taking Knuth 30 minutes to actually walk through the maze. It's certainly a lot different when you can't actually see the entire maze at once. :P

    logan

  • I did some programming contests a few years ago. In one we got killed at the first level, but the first year we got to go the North Eastern US and get killed by Harvard, MIT, and RIT (which was at the local competition, but placed at the regionsals). It was fun, but we didn't take it very seriously. Alot of it seems to come down to figuring out some trick, or just hacking something out.

    A professor of mine (Dr. Hans Koomen) had developed a contest more focused on planning, design, and doing it right [geneseo.edu].

    In 1996 (the only year it was run - if at all it was) it was a Chinese Checkers competition. Build a chinese checkers player, and duke it out. There was a hack contest in the morning too... I wanted to see it happen while I was there, but it never came about. Too bad, seemed like it would be fun.

  • Your milage may vary. My educational background is not dissimilar to yours. I also attended a midwestern University, in my case for about 2.5 to 3 years before I ran out of money. One difference is that I worked for a department at the university as a C/C++ programmer/UNIX sysadmin during the time I was in school and for about 6 months after I dropped out. The pay was really bad, but I got a lot of valuable experience that I was able to use to get my 2nd job. My second job was a middle entry level job doing Informix 4GL programming, database and UNIX administration. It paid about double what my university job did and had actual benefits (which the university didn't pay for hourly people). After a couple of years doing that I was able to move up to a decent job doing C/C++ development at a small (30 person) company for a salary in the middle range for experienced developers at the time. And after 3-4 years I was able to move up to a different position at a larger company (100k+ employees) making towards the middle to upper end of the range for C/C++ developers. During my time there I've gotten several promotions and decent raises. I am just getting ready to start a new position after 3-4 years at the previously mentioned company. I've got more experience now doing web development in Java, Perl, etc. My new position will put me well into the upper range for developers in the area.

    You are right to a certain extent that someone without a degree or experience will have to 'pay their dues', but I am not at all sorry for having taken the path I chose. I wouldn't recommend it without hessitation to everyone though. It does require that you be stubborn, dedicated and willing to work hard to prove yourself.

  • Im curious if VB still suffers from the bad image BASIC has had in academia.

    Yes. It suffers pretty much the same bad image with a large share of the professional development community as well of course, even a pretty fair percentage of the Windows development community.

  • They must be getting job offers like crazy... And if they arent, they should.

    I doubt they will get job offers, and I doubt any company is foolish enough to offer them jobs based on such a contest. I've participated twice in the European finals (once missing a trip to the world finals because despite ending high enough to earn a ticket, all the teams in front of us were from the same country, and there was a 2 team/country limit), and I've organized regional finals. The exercises to be solved are merely puzzles. You have limited time, and limited resources. There's a decent amount of luck involved. If you instantly recognize a problem and map that to a fairly standard problem, to gain valuable time. Or to interpret the wording of the exercise the same way as the organizers intended, and not have to wait for your clearification request to be processed. (Or worse, having to redo part of the program because another team submitted a clearification request, and it turns out your interpretation wasn't correct.) Even losing 20 minutes can be the difference between solving 4 and 7 problems! The contest doesn't judge the quality of the program, or its efficiency, maintainability, or anything that's actually important for a program. All it needs to do is compile, and produce the correct output on some test inputs. Of course it helps if you are a good programmer, but other important skills are typing speed, and the skill to avoid typos.

    -- Abigail

  • I agree that Problem F was poorly specified.

    What surprises me is the number of people here complaining about problem F, describing in detail how the dealt with it, but noone said they submitted a clearification request.

    -- Abigail

  • I rather see the ACM contest use python and/or perl than Java.

    There was once a programming contest that allowed the use of Perl. I think it was in one of the contests to gain access to a regional final of the ACM contest, but I might be mistaken. There was a one-man team. Who solved all problems correctly within an hour. Using Perl. The team finishing second (not using Perl) solved half of the problems.

    Perl is no longer allowed in ACM programming contests.

    -- Abigail

  • Also, is the 20 minute penalty per wrong submission new? I don't remember seeing this before?

    Not new at all. That rule existed when I participated in the '80s, and when I organized a contest in 1992, we had that rule as well.

    -- Abigail

  • and offered all of us jobs. he says what his company does is rapid prototyping and on-site tweaking to said prototypes, and that it is not unlike contest coding.

    I don't know about you, but I rather not work for a company where I'd have deadlines measured in hours while I have to share my workstation with two other people. I'd run away from any company that says "oh, our working environment looks just like a programming contest".

    and you say "some test inputs" as if to imply that the programs are not well tested... try it some time, the judge data is usually very good,

    I've been there. On both sides of the fence; as a participant, and as a organizer/judge. It's not that the programs aren't very well tested, but the test input will confirm to very specific specifications. It doesn't have to survive the typing monkey test.

    -- Abigail

  • Don't forget WATFOR [uwaterloo.ca] the Fortran compiler that an entire generation used at school.
  • Great Final Standings! But, how the heck are we going to know what the code is?

    I mean, where is the beef?

    Like any beauty contest, we gotta see the gams and curves in the codes.

    Forget the judges (they are fine anyway), I wanna see the beef!

    Where is the beef?
  • I'm not going to speak for the other top U.S. schools, but I was on the CMU team, and I can give you two reasons why we didn't finish in the top three.

    * It's not the school that wins the contest, it's three individual students. One excellent programmer from an average school is worth much more than a good programmer from a top school.

    * CMU does not practice for the contest. Some teams spend 10 hours a week preparing for the contest starting at the beginning of the year. CMU comes every year, cold, and almost always finishes in the top 25%, sometimes higher.

    There were other reasons we didn't do as well as we wanted to - see my post on the controversy, below.

    Dominic
  • Even if you don't place you'll receive job offers. While I was there I was heavily recruited by four companies. Their attitude was "show an interest and I'll hire you on the spot". The starting salaries were about $60k.

    IBM rented Universal Studios for the after-contest celebration. They spent a lot of money trying to attract the best and brightest.

    Peter Doege

  • Isn't he dead already?
  • Well the next time you see me you should introduce yourself.

    Please stop stalking me... :)

    Donny
  • It's interesting how:
    • Waterloo has been placing in the top six quite regularly, of late.
    • No US institutions have been placing in the top 4, or, this year, in the top ten.

      Not MIT. Not CMU. None of the UC schools. Not Stanford.

    The one non-apathetic thing I did in my time at UW was to help get teams heading back to the ACM Scholastic Programming Contest. That was quite a lot of work, and not terribly worthwhile at the time. It sure feels worthwhile now...
  • If you're on a team that "places," you get a better prize than the possibility that IBM might give you a "free" laptop. You'll get:
    Job Offers From Interesting Organizations.

  • Re:Controversy over Problem F (Score:3)

    by Logan ( 7529 ) <logan@vt.edu> on Monday March 20, 2000 @03:17PM (#1188941)
    I was also present at the contest and did problem F. I heard this rumor as well, so I feel very lucky. I implemented the problem in a way that paths with "infinite" distances simply weren't counted when I obtained the average.

    I've often wondered how these sorts of things should be resolved, and I don't really have any answer. I'd certainly be very angry if that were the case and I'd had to spend hours on the problem. I got lucky. (I just hope I do better next year).

    logan

  • Re:Pascal (Score:3)

    by SoftwareJanitor ( 15983 ) on Monday March 20, 2000 @04:02PM (#1188942)
    Delphi/Object Pascal is somewhat safer than C/C++ only because it is somewhat more limited in what or how you can use pointers. But that is a pretty marginal thing. You can certainly shoot yourself in the foot with pointers in either language. Whether it is faster or not is largely a matter of opinion, and which tool a given person is personally more comfortable with, and also which C/C++ tools are selected. To say 'a whole lot faster' is really not a fair generalization.

    Probably my biggest complaint against Object Pascal/Delphi is that it is still mostly a uniplatform tool (albiet FreePascal and a couple of other free alternatives are in development, none are really finished and completely compatible with the Borland products yet). C/C++ multiplatform compatibility isn't perfect, far from it -- especially when moving code between Windows and and Linux/*nix/*BSD platforms. But at this point nontrivial C/C++ code that is written with the intention of being portable is much more likely to be so than any current Pascal dialect. There are also more 3rd party (free and commercial) products designed to work with C/C++ to aid in cross platform work than there are specifically tailored to any Pascal dialect. Much as some people deride it, few languages are as close to multiplatform as Java is at this point (not to say that Java is without problems either).

    None of this may be that salient to the contest in question, but they certainly are things that often matter in the real world.

  • Pascal (Score:3)

    by spiffy_guy ( 30225 ) <<spiffy> <at> <babel.acu.edu>> on Monday March 20, 2000 @01:03PM (#1188943) Homepage Journal
    Delphi is allowed. Which is really just Object Pascal with a nice gui maker. Anyway all of the teams I know who placed well at Regionals used pascal. It is simply safer, and a whole lot faster to develop with. I like C/C++ as much as the next guy, but use the right tool for the job.

  • Controversy over Problem F (Score:5)

    by Dominic_Mazzoni ( 125164 ) on Monday March 20, 2000 @03:09PM (#1188944) Homepage

    I was on the CMU team. If you look at the statistics, you see that we solved 3 problems and were ranked 15th (in a tie). This is not what actually happened. We actually solved problem F correctly and did not get credit for it. At least a dozen other teams were also denied credit for a correct solution to this problem.

    The controversy is that the judges and ACM contest staff still claim that there was no error in the grading of the problem, and that their datasets were consistent with the problem statement. Here's why I don't believe them.

    Take a look at problem F. (Here are the contest problems [baylor.edu] in PDF if you're interested.) In a nutshell, you're given a complete directed graph, and you need to return the average length of all shortest paths between all pairs of nodes. The problem explicitly stated that you will only be given graphs in which there exists a path from every node to every other.

    This is not a hard problem to work out, but anyone who has had a formal course in computer science ought to recognize that the Floyd-Warshall all-pairs shortest path algorithm is designed to solve exactly this problem. Then all you have to do is add up all of the elements of the matrix and divide by n * (n-1).

    Except that the judges made a mistake, and tested our input using a graph that was not connected - in other words, there were nodes that could not reach other nodes via a directed path. This would not be a big deal, except that the problem explicitly stated that this would not occur. (Input validation is never a part of this contest.) Furthermore, without further explanation it is unclear how these nonexistent paths should affect the average. It turns out that the judges' solution was not counting these paths, and averaging only the paths that existed. Some teams did this by accident, and others (including Waterloo) figured it out only after submitting multiple runs and incurring large penalties. My team was one of the many that did not figure out the judges' mistake, so we did not get credit for the problem, even though our solution was certainly correct as the problem was worded. If we had received credit we would have had four problems correct, possibly putting us in the top ten. Of course, if we had received credit right away, we might not have wasted so much time figuring out what was wrong with our solution and we could have solved another problem in that time. Of course, many other teams were in a similar situation, so I have no idea what the final ranking would have been, but clearly it would have been different.

    Now for some disclaimers.

    First of all, I do not know firsthand that the judges had an incorrect data set, because their policy is not to release the data sets they use to test our programs. However, literally dozens of the 60 teams there encountered this error and many of them gained serious evidence that this was in fact the exact error. For example, one person showed me code he had written that would cause the program to seg fault if and only if the graph was not connected. He turned it in, and he got "runtime error" from the judges, indicating his program crashed. When he removed that line, he got "wrong answer". Even the team from Waterloo agreed that the data set was faulty.

    Also, I am not trying to imply that the teams that did win did not deserve it. All of the top teams did an excellent job and deserve to be congratulated. I'm mostly upset that the ACM contest staff will not either admit there was an error, or release the datasets to prove there wasn't one.

    Dominic

Slashdot Top Deals

Them as has, gets.

Close