Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Introduction to Competitive Programming 211

Posted by ScuttleMonkey from the programming-for-fun-and-profit dept.
chrisjrn writes "Last year, I unexpectedly found myself entered in the Australian Computer Programming Competition, and somehow did well in it. As a result I decided to write a guide as an introduction, for high school-level students (and others, I suppose,) into the world of programming competitively based on my experience, and how to go about successfully competing in competitions." Article looks like a good start, I'm sure Slashdot readers can add many more tidbits of wisdom.
This discussion has been archived. No new comments can be posted.

Introduction to Competitive Programming More

Introduction to Competitive Programming

Comments Filter:
  • My programing skills came from Necessity, a group of people I was with needed a website and nobody could do it. I knew the basics of C programing so I picked up PHP and went from there. Tidbits like this can be very helpfull to the self taught, school taught and clueless.. Personal experiences with programing is golden, always.

    • Re:Programing out of Necessity (Score:5, Insightful)

      by Nuclear Elephant ( 700938 ) on Wednesday September 07, 2005 @06:53PM (#13504417) Homepage
      My team competed (and won first place in) several high school computer programming contests at the colleges in New England back in my day (Plymouth State, St. Anselm, etc). I'm not sure what today's competitions look like, but the team concept made things work here. I was the code monkey of the group, and the rest had their own strengths. Prior to my coming onboard, the team continually lost - not because they weren't smart, but they weren't complete. They were very strong in figuring out solutions to problems, while I was very strong at taking those solutions and laying them out in code. That's one of the reasons I'm suspicious of the 'one-man' competitions, as real-life work challenges are often team-oriented. As adults, most of us have learned to wear many of the different hats (problem solving, mathematics, coding, etc), but building a strong team based on members' strengths still usually makes the difference between mediocre products and works of art. That's just my 2c.

      • Re:Programing out of Necessity (Score:5, Insightful)

        by w98 ( 831730 ) * on Wednesday September 07, 2005 @07:43PM (#13504746) Homepage
        well, not every situation in life is a team effort though - there are tasks that one must do alone at work from time to time, so being able to at least sludge your way through a project on your own can be a real benefit to the company.

        My last job had a total of three programmers, and we all worked on different areas of the system, and only towards what was the eventual end of my employment there (I left for a much better job) did we actually interact and connect some of the pieces together.

        You're right though, in a team situation, things can be done so much faster if you've got a team leader who can recognize skills and traits and assign tasks accordingly. But not every company will have a team of that many people on everything.

        Even at my current job, where we have a very large development team, there are still individual jobs to get done, and there are other jobs that require a team of 3-4 or even collaboration between two or three whole departments.

        And that's my $0.02 ;o)

      • On the other hand (and I'm not really disagreeing with you, but) historically, the greatest works of art in any field have been created by individuals. Bach, Michelangelo, Leonardo Da Vinci ... all were inspired individuals with the vision and the talent to create a masterwork.

        Of course, you're correct in that a lot of modern engineering tasks (software or any other kind) are complex beyond any single person's abilities, no matter how much of a genius they may be. And yes, teamwork is the way. However, i

  • Good Public Relations (Score:5, Insightful)

    by dshaw858 ( 828072 ) on Wednesday September 07, 2005 @06:47PM (#13504378) Homepage Journal
    Hopefully this type of a story will encourage other high school and college students to go into competitive programming. I know that I, at least, am nervous to start in programming competitions, but I think that having a real "just like me" article/guide on the subject will help boost interest.

    All in all, good PR.

    - dshaw

    • Re:Good Public Relations (Score:2, Interesting)

      by Anonymous Coward
      The worst that could happen is you not get any questions right. Funny thing is, you'd probably do better than at least 10 teams.

      I've done college level programming contests, and the atmosphere was always "ok, be prepared, but this is for fun" We had a free lodging, free travel, and free food for the entire weekend. It was cool. Did we win? God no, we came in 12th IIRC, but it was a fun learning experience.

      Some tips I remember:

      1. Know who's good at what. We could only let 1 person from our 4 man group

  • Code before competition (Score:5, Interesting)

    by Aneurysm ( 680045 ) on Wednesday September 07, 2005 @06:51PM (#13504405)
    The article mentions writing template code before the competition begins. How much code do these competitions generally let you rock up with? Could you turn up with huge preprogrammed libraries ready to deal with any situation? I know the questions would probably be rather obscure, but surely you get an unfair advantage by coming with preprepared code. Surely only allowing competitors standard libraries is the easiest way to make things fair.
    • If you don't get your own teminal, sometime it can only be what you can write in 1-5 minutes. So generally, you can only code what I put in the article.
      • Did you get preparation time before the questions were unveiled to write some preemptive code?

        • Re:Code before competition (Score:4, Informative)

          by chrisjrn ( 811644 ) <<moc.liamg> <ta> <nrjsirhc>> on Wednesday September 07, 2005 @07:05PM (#13504489) Homepage
          In the Competition in India, we had around 10 minutes to get used to the IDE and compiler, and we used that to have our code ready. Most other comps are the same.
          • Cool, thanks for the replies and info. Know of any competitions in England by any chance? :)
            • I don't, but I'd assume that you have a National Informatics Olympiad. The best thing to do would be to Google [google.com] it :).
            • Cool, thanks for the replies and info. Know of any competitions in England by any chance? :)

              If you're in college still, ICPC = "International Collegiate Programming Contest." The site seems down at the moment, but it's usually at http://acm.baylor.edu/acmicpc [baylor.edu] or http://icpc.baylor.edu/icpc/ [baylor.edu]

              • I graduated University last Summer. I did Computer Science and never heard anything about competitive programming. Is it a biggish thing in the states?
                • Not really. Someone else posted further down about a few other competitions. The ICPC isn't too old, but many of the other competitions are pretty new. It's a fairly recent (last 10-15 years, but really expanding in the last 5 years) phenomina.

                  I learned about it only because my school's chapter of the ACM always participated. The division I'm in covers the mcuh of the west coast of the US and the west coast of Canada. There were over 100 teams last year. It really sucks to be in the same division as

              • acm.baylor.edu or icpc.baylor.edu

                Ok, this creeped me out just very slightly... How does it come about that this site is hosted at a baylor.edu domain? I'm sitting in my dorm room on Baylor's campus right now... Are there other sites hosted at other universities, or is Baylor just special somehow? I never had the impression that our CS dept was really much good (physics is my business).......
            • Then there are two programming contests that I know of - Robot Table Tennis and the long-in-the-whisker Micromouse Tournament.

              Robot Table Tennis is simple enough - build a machine that is capable of hitting a table tennis ball over the net, either from a serve or from a return. (The umpire serves.)

              The Micromouse Tournament is also simple. Build a machine capable of solving a maze and navigating to the centre in the shortest possible time. In order to be competitive, these days, you've got to have a micromou

            • Re:Code before competition (Score:4, Informative)

              by hburch ( 98908 ) on Wednesday September 07, 2005 @08:19PM (#13504954)
              For high school students, the answer would be the British Informatics Olympiad [cam.ac.uk].

              Could become a representative for Great Britian to the International Olympiad of Informatics [win.tue.nl] next summer, to be held in Mexico.

              If you're in northern Ireland, you'd compete in the Irish Schools' Programming Competition [compapp.dcu.ie].

              You can also compete in online contests such as USA Computer Olympiad [usaco.org] (operated in the USA, but open to everyone), or a quick google search will yield more.

          • In the ICPC, we were given a test problem to work on. We had an hour to complete it, and it was a chance for them to work out any bugs with the network answer submission process before the competition started. Unfortunately, anything we coded up in that hour got wiped before the start of the real competition. The practice problem was also easy. It was something like, take 10 strings from this file, reverse them, and print them to the screen.
          • I was introduced to a different type of programming competition when my team participated in New Mexico's Adventures in Supercomputing Challenge (in association with LANL) during my junior year of high school. We were granted time on a Cray, afforded accounts on a box running OSF/1 and a mentor from Sandia National Labs, and accommodated at a three-day programming retreat. Yet with all that preparation, we were totally unprepared for the presentational aspect of the competition, which was similar to a sci

  • Big Competitions not Mentioned In TFA (Score:5, Informative)

    by Anonymous Coward on Wednesday September 07, 2005 @06:51PM (#13504407)
    - ACM International Collegiate Programming Contest: http://icpc.baylor.edu/icpc/ [baylor.edu] (Big competition between colleges worldwide - sort of the equivalent of the IOI at the university level).

    - TopCoder: http://www.topcoder.com/tc [topcoder.com] (weekly matches, yearly competition with large cash prize, also hosts the Google Code Jam (http://google.com/codejam) [google.com]).

  • Good Info... (Score:4, Funny)

    by Knight Thrasher ( 766792 ) * on Wednesday September 07, 2005 @06:53PM (#13504421) Journal
    Just one tip:
    Needs more Caffeine.

  • Why? (Score:3, Insightful)

    by NumberOneFan ( 811608 ) on Wednesday September 07, 2005 @06:54PM (#13504430)
    Why is "competetive programming" so great? I'm not trying to troll, but is this for some lack of being able to compete in sports or something? Why does this too have to be competitive? It seems like everything in here has to be tested and ranked.

    My university had a team, I went to one meeting and realised how stupid and hokey it was. Half of it was an intellectual circle-jerk and the other half was some practicing. All too l4m3.

    • Re:Why? (Score:5, Insightful)

      by Helios1182 ( 629010 ) on Wednesday September 07, 2005 @07:01PM (#13504467)
      As opposed to the non-intellectual circle jerk that makes up most high school sports? These are students that like to program, ar probably good at it, and enjoy some competition. You can compete in almost everything. Chess, cooking, football, programming, rock climbing, gardening... If it drives you to become better at something you love, whats wrong with it?

    • Re:Why? (Score:2, Interesting)

      by KhaZ ( 160984 )
      Competitive programming is a great way in the way that sex for sport is good.

      If you're nervous, scared of your skills, etc: nothing's better then just straight immersion. You can't get too anxious if you're just *doing* it. You have to jump in with both your feet and start, or else you'll never get anywhere.

      It's really great for those of us who are scared of a particular domain, of not understanding problems, and all in all it really does help in solidifying domain ideas and promoting learning.

      A good
    • In general you'll meet people who like programming (I'm just referring to "programming" in the narrower sense, which doesn't include other computer-related-stuff that you guys may relate to when talking about "programming"), and through trying to solve the tasks there's a sense of accomplishment when you finally get it right.

      Of course, it's not for everyone, and I know people who are gurus in computers and tech in general yet clueless in these competitions, and OTOH I know some people whose computer literac
    • That's been my experience with engineering in general, one giant intellectual circle jerk. No one knows everything, humility is a virtue. But you'd like Real Ultimate Truth actually exists in the minds of a select few who are also tasked with rating and ranking the unwashed masses based on silly questions or agreement some groupthink.

      The only competitive programming that matters is solve a problem no one else has solved. You have your whole life to do it, you may begin....wait for it....now.
    • Why is "competetive programming" so great? I'm not trying to troll, but is this for some lack of being able to compete in sports or something? Why does this too have to be competitive? It seems like everything in here has to be tested and ranked.

      My university had a team, I went to one meeting and realised how stupid and hokey it was. Half of it was an intellectual circle-jerk and the other half was some practicing. All too l4m3.

      Why is "football" so great? I'm not trying to troll, but is this for some lack

  • Competitive high school programming teams ... (Score:5, Funny)

    by Average_Joe_Sixpack ( 534373 ) on Wednesday September 07, 2005 @06:54PM (#13504431)
    Now there's a scary yearbook shot

  • Here's a BIG Hint... (Score:3, Interesting)

    by Syrae ( 802799 ) on Wednesday September 07, 2005 @06:55PM (#13504436) Journal
    Don't party the night before. Being drunk usually isn't good (for most people, though a few code better while inebriated), but being hung over is much worse.

    My school participated in a competition once, and we didn't do too well. One of our teams coming in hung over and running on two hours of sleep probably didn't help.

    • I usually code better when I've been drinking a little. It helps me to see the problem and solution a lot more clearly. I also don't mind commenting the code so much. When I look at it the next day, I think, "hey, it looks good, and runs fine...but how the hell does it work?"

  • TopCoder (Score:5, Interesting)

    by Da Twink Daddy ( 807110 ) <bss03@volumehost.net> on Wednesday September 07, 2005 @06:57PM (#13504442) Homepage

    Want to get involved with some competitive programming, right now?

    TopCoder [topcoder.com] is always looking for more members. The algorithm compeitions only take a few hours, and can pay good money. Plus discussion of the algorithms afterwards with the other members can be quite enlightening.

    They also do design and development competitions, which take a bit longer, but pay a lot better. You can also pick up cash by being a reviewer for these compeitions, if you pick up enough "scratch" in the compeitions themselves.

    You get individually rated on each of the 3 competitions and TC also provides some measure of employment services.

    Back when algorithm competitions always paid, I earned my 1/2 of rent through them. After I graduated from college I paid my bills through a combination of design / development / reviewing. Now I work for TopCoder as a salaried employee.

    Check it out, and look me up. My member handle is the same as my /. handle, just without the spaces.

    TopCoder can be very rewarding. I hope every programmer that reads this at least looks at the website.

    • How does one get started?
      • Go to www.topcoder.com and register.

        The next "Single Round Match" is Fri Sept 9.

        Run the applet, log in, and try some of the practice rooms.

        Too bad the Google Code Jam, and TopCoder Open competitions are already well on their way...

    • TopCoder is always looking for more members

      over the age of 18, apparently. I have an account with them but I couldn't figure out what to do with it since a bunch of the activities require you to be 18 or older.

      Normally I wouldn't complain (TopCoder sounds great, why else would I have registered?), but the article was about high school programming competitions. In fact, the SEARCC that he mentioned has a requirement of being under 18.

  • Why I like competitive programming. (Score:5, Interesting)

    by DiogoFerreira ( 844415 ) on Wednesday September 07, 2005 @07:05PM (#13504495)
    Competitive programming can be addicting, I started on highschool just for fun on a small local contest, then me and my mate moved to the national olympiads, we were there just for the fun of it, but i actually got a good place. Then it started to get addicting, we were participating on every kind of contest, i won the national olympiad that year and therefore went to the International Olympiads in Informatics. This year i went to the IOI again. Just a word of wisdom, do _NOT_ get carried away by these contestes, they are good for fun but if you get addicted, they can even harm your studies.

  • Texas Competitions (Score:2, Interesting)

    by Jeff85 ( 710722 )
    I used to compete in programming competitions during my junior and senior years in a Texas high school. I competed in TCEA [tcea.org] and UIL [utexas.edu]. I did pretty well, though there were never any cash prizes. I always had a lot of fun due to the camaraderie with fellow classmates from my school, and I guess I got recognition for winning. However, the problems were relatively easy, with no complicated graph theory problems and the like.

    My school had a great computer club with a enthusiastic sponsor that went to local prog

  • Real World competitive programming. (Score:5, Interesting)

    by team99parody ( 880782 ) on Wednesday September 07, 2005 @07:09PM (#13504518) Homepage
    The company I'm at has a big C#/ASP.NET application, but a couple marketing guys were doing UI prototyping in Ruby/Rails that appears to be nearing feature completion faster than the "real product". It's kinda fun to see - but in the end only one of the two solutions will survive - perhaps with quite a few people's jobs on the line as the prize.
  • Make sure you know the IDE(s) that you'll have to use. When I went to my first competition, I was only familar with Borland's C++ IDE. Unfortunatly, I could only use Visual Studio. If it wasn't for my partner being familar with Visual Studio, I would have lost time getting used to it.

  • Not a 'great' guide, but good points (Score:3, Funny)

    by OverlordQ ( 264228 ) on Wednesday September 07, 2005 @07:24PM (#13504617) Journal
    I know a couple of the comments he makes to make you better like creating a template can and most likely are against the rules (I can attest to at least one competition that it is). And he is correct that more languages you know the easier it is if you switch between them. I remember one problem, that was easily solved in 2 short lines of Perl, which required the C coders to write quite a few more then that.

  • ICFP (Score:4, Informative)

    by Anonymous Coward on Wednesday September 07, 2005 @07:26PM (#13504628)
    One of the best known contests is the ICFP (International Conference on Functional Programming) Contest [plt-scheme.org]. One great thing about it is that entries can be in any language. Therefore many consider it a competition between languages as much as between programmers.

    The winners to the 2005 ICFP contest are set to be announced this month (Sep 27th). Here're a couple of slashdot threads about it:

    http://developers.slashdot.org/article.pl?sid=05/0 5/30/036201&tid=156&tid=162 [slashdot.org]

    http://it.slashdot.org/article.pl?sid=05/06/26/001 8252&tid=156&tid=8 [slashdot.org]

  • My experience with topcoder (Score:5, Interesting)

    by merreborn ( 853723 ) on Wednesday September 07, 2005 @07:28PM (#13504636) Journal
    I participated in a handful of events at topcoder.com [topcoder.com], including last year's Google Code Jam, for which I got this nifty shirt I'm wearing right now.

    The problems I encountered there (which I solved in java) were far more difficult than the stuff I do at work (as a PHP/Javascript/MySQL lead web dev). One of the Google Code Jam problems was a real brain twister:

    Two rocks are dropped in a pond, and create square ripples. For example, a rock of weight 8 is dropped at a point -- at time zero, it creates a ripple of height 8 at the point it was dropped. at time zero, it creates a 3x3 square ripple of height 7, like so:
    777
    7 7
    777


    The problem: given these rules, find the highest ripple height given the locations, drop times and weights of two stones. (If two ripples overlap, the height is equal to the sum of their heights - i.e. if a height 3 and height 4 ripple both occupy the same point, the height at that point is then 7)

    The solution 90% of us tried was to simply brute force the problem, creating an array, and updating the array over and over again, comparing the ripple heights to the previous max. The maximum area we were supposed to check was 2000 x 2000 -- so the brute force method timed out (there's a pretty short execution time limit).

    The correct solution was to consider time as a third dimension; each rock creates a 4 sided pyramid. Then you only need to check 3 points, which can be done with simple equations: the 'peak' of each pyramid (the height of which happens to be the weight of the corresponding rock) and the intersection of the two pyramids.

    Did I mention that there were 4 problems, of which this was the second, all of which had to be solved in a grand total of 90 minutes? And that your score decreases every minute you spend on a problem?

    Yeah... TopCoder's rough. And no, custom pre-written libraries won't win this for you -- but they will save you a little time.

    • Re:My experience with topcoder (Score:4, Interesting)

      by sydneyfong ( 410107 ) on Wednesday September 07, 2005 @08:07PM (#13504893) Homepage Journal
      > And no, custom pre-written libraries won't win this for you
      Um... those "professional" contestants would have already solved a similar task like you've just mentioned 10 times before... The "libraries" are basically hard-wired into their brains.

      I despise those competitions that put too much restraint on time given to solve the tasks. To get "good" at it, you have to grind through hundreds (if not thousands) of problems to the extent that when you see the tasks in the competition, you can immediately relate: "aha! this is almost identical the XXX that I solved a year ago!". I'd describe these people as "solution generating machines". And the time and effort spent to train to that state is a total waste of human resources, IMHO.

      It's like playing chess with a 5 second time limit for every move...

      And yes, I had been involved in these competitions for years. (A few local/national competitions and the IOI 2003, I wonder if there are any slashdotters who was also there... :-p) It's a good thing that the rules in the "Olympiad in Informatics" give (partial) credit to non-standard, partial or even downright bizzare solutions instead of the rigid rules of the ACM ICPC, Topcoder and the like (to have to solve the problem completely). And 5 hours for 3 problems, plenty of time to think, and that's the part which I think is most fun and challenging.
      • How is what you've just described any different than what "experts" in a field have developed themselves into?

        Being able to take what you've learned (experience), apply it to new situations in new combinations, and to see the relationships and patterns involved, quicker and better than others.
        • At least most other "experts" do contribute (whether positively or negatively) to society and humanity in some ways.

          And these "experts" are "experts in solving algorithmic problems in 30 minutes", yet an intelligent person well versed in algorithms etc would be able to solve them in a few hours without all those mindless grinding that they do.

          I don't doubt that there are people who could become "experts in solving algorithmic problems in 30 minutes" without all that grinding, but from what I've seen this wo
      • I'd argue that becoming an expert TopCoder programmer is no less useless than becoming an expert cup stacker, or an expert Everquest player. Thousands, millions, who knows how many man-hours are devoted to those hobbies... with little real-world application.

        At least an expert topcoder user can write you a string parser that works the first time. I'm currently working with a programmer for whom that'd be a massive improvement.

        In fact, even more, major companies (Google, for one!) are actually using TopCod
    • huh...since we only have to consider two stones, wouldn't the highest peak always occur in an easy to calculate place? Either the point where the heaviest stone was dropped or the point of first intersection? First find the direction from stone 0 to stone 1 so that you may find the distance along the shortest path.

      Now...let's say that stone 1 (weight 12) was dropped at t=3 after stone 0 (weight 15), 20 units away from stone 0. So you subtract 3 from 20, and find the midpoint of the remaining distance o

      • Yes. You have to be a little careful of odd/even distances, and because the proper metric is not Euclidean distance but whichever is longer of the x and y axis distances, and of potential non-intersection (consider e.g. two stones dropped in the same location at different times), but your basic idea is sound. Anyone who tried to simulate to solve this missed the spirit of these competitions---they're really about mathematical modeling more than computer programming.

  • My experience (Score:5, Funny)

    by Reality Master 101 ( 179095 ) <RealityMaster101@gmail. c o m> on Wednesday September 07, 2005 @07:39PM (#13504712) Homepage Journal
    When I was fifteen, I was in a programming team competition (about 25 years ago). I think we all had Pascal computers or some such. We knew going in that there was going to be one "primary" problem, along with several lesser problems. We would be scored based on the "correctness" of the algorithm, the speed of execution, that sort of thing. The team agreed that I would take the primary problem, and others would work on the other ones.

    So I'm a hot shot junior programmer, ready to take on my assignment. Here was the problem: "You have a number of cities mapped on an x,y grid. A travelling salesman wants to find the shortest route between the cities. Calculate the shortest route." We had two hours or something.

    I'd never heard of this problem before.

    So I was like, "Hey, no problem. This is eeeeeasy." So I went off in my youthful exuberance with a blank piece of paper, figuring out how to solve it. Hmmm. That idea was good -- except it wouldn't work for this one case. How about this idea -- nope, that one will hang up on this other case.

    Minutes ticked away as I sweated the problem. There HAD to be a solution to this. Half an hour, then an hour -- I'm growing desperate. What the hell? This problem is freaking hard. Finally I'm like, "screw it" and threw something together at the last minute. We ended up losing because I spent too much time thinking about it.

    I still think it was goddamn unfair to give an UNSOLVED PROBLEM in a programming contest for high school students. I'm still pissed about it to this day. Grrr. :D

    • Unbeknownst to me, my math teacher sent me off to find a counter-example to Femat's last theorem. Certainly kept me quiet for a few hours.
    • Here was the problem: "You have a number of cities mapped on an x,y grid. A travelling salesman wants to find the shortest route between the cities. Calculate the shortest route." We had two hours or something.

      I still think it was goddamn unfair to give an UNSOLVED PROBLEM in a programming contest for high school students.

      Not sure if I'm being pedantic or not, but the problem, as you stated it, is neither NP nor unsolved. The shortest distance between two points is solvable in better than factorial time.
    • Solving TSP is easy:

      1) Compute the list of all possible tours.
      2) Select the shortest tour.

      Granted, there's no efficient way to solve the problem, but that's not the same as unsolvable. In fact TSP is proved to be NP-complete, so there are lots of translations to other solved problems available.

  • I got roped into those computer science contests in highschool. My teacher just told me what time to show up after doing something nice for me.. so I couldnt tell her how lame I thought those competitions were, and how I'd rather stay up all night drinking stolen grocery store alchohol and doing acid. So I went..

    If you're into programming in your spare time, the competitions against other local highschools are embarrasingly easy. I think out of about 13 competitions, my team easily won 1st place in 10 of

  • In 2004, my team won the eliminations in New Zealand and we went on to the ICPC World Finals in Prague. Up to the finals, we were expected to write clever programs using efficient algorithms that ran blazingly fast. Then, at the finals, it was all about hacking up crude semi-brute-force approaches that didn't work efficiently at all but got the job done. We were by far not the only team to do badly because at the finals because it took us hours to figure out that the clever algorithms we were coming up with

    • The 2004 world final was a bit of a marathon. I'm not sure I'd say that any old solution would do, but the contest was overburdened with a large number of tedious case-analysis and geometry problems. It lacked "algorithms" problems.

      I think there's general consensus among the coaches that the 2005 problem set was more appealing. It had brain teasers and algorithms. The top 4 teams were struggling with 3 different problems in the last hour. The winner, Shangai, happened to be the ones who figured out the
  • I wrote the Canadian Computing Competition (Junior Level) last year. I was in grade 10, most of the contestants were grade 11, and I placed tenth out of about 550. If I had read that article beforehand, I would still have placed tenth out of about 550.
  • I have always been reluctant to try a hand at programming competitions because of the time factor that they entail. Different kinds of problems are suited for different kinds of programming languages. In a competition where the programmers are hammered with one problem after another, it is difficult to make a switch from one programming language to the other in a matter of minutes, even if you have been programming extensively in two or three languages. Refering to books and other resources for syntactic re
  • It was a neat thing for students at Stevens Institute of Technology, my alma mater [stevens.edu], who were involved in ACM to take top 10 in the greater New York Regional contest for the last 4 years (while I was in school). Although I would have loved to take part, due to the timing of practice sessions and competition, I couldn't. However, I knew the leadership and others involved, and they became much better programmers as a result of this. We were competing against many larger and more well-funded schools like NYU

  • Some more tips (Score:2, Interesting)

    by ESarge ( 140214 )
    I was part of a University team that did quite well during the years. Our best result was 2nd in New Zealand for one competition.
    Anway - some tips:
    1. Read the question extremely closely before you start. It is frustrating to miss an important detail *after* you've written a lot of code.
    2. Plan carefully before you start. One of my team members was very talented at finding approaches that would work without problems. The other two members of our team could then implement them reliably. You cannot waste time

  • Problem solving is key (Score:3, Insightful)

    by xRelisH ( 647464 ) on Wednesday September 07, 2005 @08:12PM (#13504920)
    I think there was too much focus on the coding itself in the guide. When it comes down to it, its the ability to solve problems.

    The best way to practice for a programming competition is to treat it like a math competition. If you can think of efficient solutions and apply them quickly, you will do well. Remember that a lot of these competitions have runtime limits (usually 2-3 seconds on a predetermied isolated machine), so coding up the simplest solution won't always work.

    Practice is also very important. Try ACSL [acsl.org], there are some sample problems available there, practice doing them and time yourself!

    Also, for those who say that programming competitions are useless, they have no clue what they are talking about. What sets you apart in real-world development involves thinking up efficient solutions to difficult problems. Making the code easy to maintain and expand is just a simple step up when you do development in the industry.

  • Rounders (Score:2, Insightful)

    by Nuttles1 ( 578165 )
    As with many things this story can be understood by relating it to Rounders the movie. When Knish says, "Alimony, child support, my kids eat. I'm not playing for the thrill of f**king victory." Competitive programming, oh my, I program for money, not prizes. Even if those prizes are some cash. At the end of the day I want my check every time, I don't care if I am the absolute best, crap, I am better than most without even putting effort in. If I want to gamble I go to the Hold'em tables.

  • Let your programs fight each other while surreptitiously learning about assembly language.

    www.corewar.info

  • Recently competed in the UNSW ProgComp (Score:4, Interesting)

    by chendo ( 678767 ) on Wednesday September 07, 2005 @09:04PM (#13505226)
    I recently competed in the UNSW ProgComp ('largest competition within Australia'). We only came third place, due to good competition this year (we won in 2003 with VB against Perl, Haskell and C++, heh :).

    Although I think the article fails to mention the organisation of 'computer time'. The Australian Computer Programming Competition and the ProgComp both allow three members in a team, but only one computer between the three of them. This means that you have to organise the priority and the division of problems amongst your teammates. Also, learning to code on paper is another important skill, as you won't have access to a keyboard the whole time. Therefore, having access to a printer is extremely helpful as you can just print and debug your code.

    Due to the nature of some languages, they restrict languages like Java and Python in the bigger competitions (IOI, ACPC) due to the large amount of standard libraries they get to play with. For example, I wasted half an hour coding Task 4 [unsw.edu.au] before I realised we could switch languages halfway through the competition and got it done in 15 lines with Python with regex.

    Finally, you do not need to have a team that consists entirely of programmers. In our team (for this year), we had two programmers, one to do the algorithmic ones (my friend, who represented Australia in the International Informatics and returned with a bronze medal), one to do the string-based ones (me), and another person to solve the problems by hand. Although, due to ProgComp deciding to have less algorithmic questions, my friend was only able to use his skill effectively on one question and the rest were split up between us. We had our third team member solve Task 3 though, and just coded a small program to decode it using the supplied decryption matrix.

    I won't be able to compete in high school competitions anymore as it is my final year, but I wish the rest of you, who are still able to compete, luck.
  • Waterloo kicked my ass.
  • C++/STL/BOOST (graph and multi-index libraries and lambda)

    If the competions gave these as options, there really wouldn't be
    a competition. It would be a battle of who can figure which routines
    to use in which order... Or in other words it would be a slaughtering
    of people using any other language by people using the C++/STL/BOOST combo.
    • Um...have you programmed in anything other than C++? A large chunk of STL and Boost are poor imitations of features found in other programming languages. Much of Boost is quite consciously modeled on functional programming languages. Maybe you should try some of these languages. For example, if you like lambda, why not use a language where concepts from lambda calculus are natural?

  • From the article/post:

    Article looks like a good start
    which may be the overstatement of the posting year.

    For those who don't want to go read the article, here's the summary:

    • he likes languages Basic (apologetically), C++, and Python
    • he recommends a main procedure
    • write a space based parser in advance (is that even fair?)
  • I did a couple Regional ACM competitions, a few local ones, etc. They were fun, after the first one. My recommendations:

    1. Know your environment. The competitions I've been to give you some time on the computers before the competition to get to know the environment, compiler, IDE, etc. Make good use of it. If they have Eclipse, what version of Java, gcc, pascal, etc. Know the editor you are going to use. Do they have emacs, vi, etc? Knowing your environment will greatly reduce your write-compile-te

  • Write some software instead (Score:3, Insightful)

    by burris ( 122191 ) on Wednesday September 07, 2005 @10:32PM (#13505754)
    Competitive programming looks like fun and I think you can learn quite a bit from it. You can also earn reputation capital that can help in getting a job. I would think most employers would be more impressed with a high rank on a competitive site than with paid certs.

    That said, I think "undiscovered developers wanting to get a break" should spend most of their time writing some useful software or web application instead. You get more experience than just solving puzzles at breakneck speed. Writing a good piece of software or site that your interviewer has used goes further than anything short of a personal recommendation. When people use your software and are impressed with your skillz, work comes to you. Plus, you could end up founding a software business that makes you a millionare.

    There are a lot of opportunities out there.

  • Tips (Score:5, Informative)

    by schnitzi ( 243781 ) on Wednesday September 07, 2005 @10:56PM (#13505907) Homepage
    I competed and coached for several years in the ACM Scholastic programming competitions. To this day, my school (the University of Central Florida) routinely places all three of their teams in the top ten of every regional, so it's safe to say that our method is tried and true.

    Some of the major facets that we coach:

    1. Easiest problems first. Appropriately applying a concept from computer science itself, the goal of a contest is to maximize your throughput. Since easy problems are worth as much as hard ones, effort should be made to discern which problems are easiest (as opposed to most interesting!).

    2. Team roles. Back when contests had four people to a team, we had two people as "bangers" (i.e. people who sit at the terminal and quickly compose solutions to the easier problems) and two were "software engineers", who sat away from the terminal and worked on paper. Note that after the first hour or two of the competition, EVERYONE is a software engineer.

    3. Specialize. In addition to roles, team members would typically have a specialty. Some people are good at algorithms; others at text processing; others at math problems, etc... This should all be worked out during practice to the point where every member of the team should be able to read a problem set and immediately tell who on the team will likely end up working on each problem.

    4. Do as much work away from the terminal as possible. Since you only have one terminal (in the ACM contests), it should be considered a scarce resource. Priority should be placed on entering new code; if you are debugging and someone has written out new code that's ready to enter, take a printout of your program and let the other person on. An exception is made when the person debugging feels they are within five minutes of a solution.

    5. Test extensively. This is the difference between a good team and a great team, in our experience. It is extremely tempting to submit your code once your program produces the correct output for the sample data. But it is not worth a failed submission.

    6. Consistency. We didn't mandate particular coding conventions, but we did mandate that team members at least HAVE coding conventions. E.g. array names -- are they the plural or singular form of the word (node[i] vs. nodes[i])? Similarly for variables that keep count, method names, etc. Recalling such things while typing wastes valuable minutes.

    7. Have practices that are genuine contest simulations. We even went so far as to shine lights in team member's faces and make lots of distracting noises, to simulate contest environments. On occasion we would even intentionally make mistakes in the problem sets and judging, just to prepare people for that (since it ALWAYS happens in the actual competition!).

    There were others, but I can't give away all our secrets! Well, okay, maybe I just don't remember them all.

    In our experience, it's the teams that consider contests to be all about "hacking" or "typing fast" that typically do very poorly. Those that apply good coding practices, and are consistent and organized are the ones that come out on top.

  • Coding Competitions Reward Bad Practice (Score:3, Insightful)

    by Jekler ( 626699 ) on Thursday September 08, 2005 @02:11AM (#13506892)
    I'm not a big fan of programming competitions. They score people on bad programming practice. The skills that make you the best competitor are frequently the same habits that make you the guy everyone venomously whispers about in the cafeteria.

    They reward you for coding fast, hacking out make-shift solutions (i.e. Code that could never pass QA), and the given problems are too narrow to be representative of a real programming problem. You can ignore things like portability issues, standards compliance, elegance, orthogonality, modularity and maintainability.

    Real programming skills, the things that really set the master programmers apart, play absolutely no role. Namely: Source control and documentation. Most types of "competitive science" won't work well. At least the type where you can't build your project ahead of time. You're going to get the same quality work out of "speed programming" that you'll get out of "speed chemistry". Wouldn't that be fun? Get a room full of chemists together with a bunch of components and tell them to mix real fast, no time for measuring!

    That's my take on the whole Competitive Coding atmosphere.
  • The most interesting thing I learned at the university later on was it is the cooperation that counts. I do not know why students should compete with each other when they will most often work in a team in their future jobs.

    That is why I value Google Summer of Code so much; because it forces students to work together with ones they do not know: they learn the social part of programming. This is what most programmers lack; including me of course. Or else I would not be reading and contributing to this very
  • People don't realize the power of software: it can change the world, if used correctly. Software must be like air: free for use, for everyone. Stupid competitions like this may enhance creativity but also make people forget how important software is, and how free software must be. For if some top algorithm is found, it must be available for everyone to use without any fees whatsoever.

Slashdot Top Deals

It is easier to write an incorrect program than understand a correct one.

Close