Slashdot Mirror
Introduction to Competitive Programming
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.
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.
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
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.
- ACM International Collegiate Programming Contest: http://icpc.baylor.edu/icpc/ (Big competition between colleges worldwide - sort of the equivalent of the IOI at the university level).
- TopCoder: http://www.topcoder.com/tc (weekly matches, yearly competition with large cash prize, also hosts the Google Code Jam (http://google.com/codejam)).
Just one tip:
Needs more Caffeine.
using namespace std; ...
...
#include
is wrong, it should be
#include
using namespace std;
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.
Now there's a scary yearbook shot
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.
Competitive programming differs from the normal corporate paid programming practice. Competitive programming requires you to be real fast at arriving and implementing solutions and almost always the stress levels are high. In the corporate world there is an essential latency from design to implementation so the programmers have in effect more time and resources to perform their actions.
http://topcoder.com/ is a good starting point for experiencing competitive programming although the paradigm is a little different.
Want to get involved with some competitive programming, right now?
TopCoder 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.
sounds cool
;)
:(
I got distracted trying to figure out if a programming competition was nerdier than math or not
Too bad i'm old enough to have been out of school before programming anything was common
On the other hand we did win one of the earliest regional math competitions.
Throwing down the gauntlet here. Who can code support for a new BIOS chip into flasher for linux the quickest? Extra points for adding new hardware support.
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.
I used to compete in programming competitions during my junior and senior years in a Texas high school. I competed in TCEA and UIL. 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 programming contests held by other high schools about once or twice a month. HP (previously Compaq) also holds their own annual competition in Houston, called Code Wars. I guess it was easy for me to get involved because this was part of a school club.
Now I'm in college and the ACM ICPC and high level TopCoder problems kick my butt. I need to learn more algorithms.
Fetch Text URL - Firefox Extension
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.
If you're not interested, don't read it. Some of us do find it interesting, either because we're programmers or because we like to compete. Slashdot carries many articles on different topics, making it more interesting for more people. If all you want is stories that interest you, and don't want any others posted, why don't you found your own site, so that you have the final editorial say?
Good, inexpensive web hosting
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.
No, I will not work for your startup
Me and my friend used to try this, pitting ourselves against each other (and sometimes against our Intro C++ Prof) to see if the psychology of direct competition generated more enthusiasm for clever coding ideas. However, instead of being isolated bitter enemies (within the code world) we ended up cooperatively competing and made a final, ultimate frisbee of a whirly executable. I guess, as they say, I made the butter, he made the jelly, they didn't mix, but the roll (as in electrons 'rolling' with holes, on/off) tasted guuuuuuuuuud.
When I was in high school the competitions were conducted in ugh Pascal. It shifted to C after I graduated. If you can pick a language why not use perl with all of cpan at your disposal you should be able to crush the competition.
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.
Your hair look like poop, Bob! - Wanker.
One of the best known contests is the ICFP (International Conference on Functional Programming) Contest. 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.
0 5/30/036201&tid=156&tid=162
1 8252&tid=156&tid=8
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/
http://it.slashdot.org/article.pl?sid=05/06/26/00
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:
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.
When I was in high school the competitions were conducted in ugh Pascal. It shifted to C after I graduated. If you can pick a language why not use perl with all of cpan at your disposal you should be able to crush the competition.
Ah, but in college when I went in 1980, it was in Algol, as only math dweebs used Pascal, and then it became C.
I agree about perl - both elegant and powerful, and it's a true test of programming. But I still hate the fact it treats zero (0) values as nulls - have to alter database queries to return zero (0) values as negative one (-1) instead or it ignores them.
-- Tigger warning: This post may contain tiggers! --
You could read TFA - This isn't a documentation of a one-off event, rather many. I only found myself entered in the first one unexpectedly...
In Ontario (Canadian province in case you are wondering) there is highschool competition organized by the ECOO (Educational Computing Organization of Ontario) http://www.ecoo.org/ecoocs/Contests.html. when I took part in them there was no age restriction, I took part in all of them once I knew of their existance.
;D ... we calculated the volume, and then just always said 'yes' that the 5th point was within. We got volume properly on all counts and 3 of the points properly. The Judge told us that our neighbouring team coded 'no' for the answer, hence got only 2 of the points right and was contemplating weather to rerun the test (judges have alternative data sets for second runs) and hope if they could get better results ;D.
Its generally is in teams of 4 and you are provided a set of 4 problems and have 2 hours to solve them. 4 people 4 problems, does not sound bad, until you notice you have 30mins to code and test. There are bonus points for handing in sollutions earlier (the faster you do, the better bonus), also, there is bonus for flawless first attempt.
As per the language, I dont think there is a restriction. First year we wrote in QuickBasic (closest to my c64 basic), the other years we wrote in Turing (another Ontario specific thing, Turing is a language developed for Ontario Highschools by HoltSoft / University of Toronto http://www.holtsoft.com/turing/).
Choose a language you know well and dont have alot of trouble getting to work with. One year a team showed up with their own pc (requirement at higher levels), but could not work with their tools.
Some questions are simple, here are some I remember:
1) draw a star provided you know the number of spikes
2) game of life
3) kernel / process simulation
It is assumed you know what a highschool student should know, hence trigonometry is not explained, but for game of life or the kernel/process simulation the problem was explained in detail.
One question we were given (third stage) was:
1) here is a formula for volume of tetrahedron
2) here are 4 points, calculate the volume
3) here is another point, tell us if this point lies within the tetrahedron
we were at a loss, how were we to know if the point lies or not? My friend who had this problem (I had kernel/process simulation, but was writting way too verbose code that amounted to nothing) knew that answer lies within the question, and tried to get us to help him, but 4 people 4 problems, everyone had own thing to do.
So what we did? cheated...
For Canadian Highschoolers there is another contest being run, this time by one of the Worlds best computer universities, the University of Waterloo (watcom = Waterloo Compilers, Sybase and RIM are also Waterloo graduate startups). Its called Canadian Computing Competition http://cemc.uwaterloo.ca/ccc/index.shtml. Unfortunatelly I never took part in this as no one at my school knew of it, and when I became informed it was too late.
Finally, for university studs there is the ACM competition, the mother of all computer competitions. Checkout the problems archive, if you solve one question a day you will have years of fun http://www.inf.bme.hu/contests/tasks/
Both in my highschool and my university people who were interested in competition banded together and ran clubs that were mentored by knowledgable people who were out to help us.
In highschool by last grade we coded basic stuff in ASM, C, C++, Watcom Basic, QBasic, Watcom Pascal, Borland/Turbo Pascal, Turing, OOTuring. I with my friend for class project did simple statistics based AI in bp. Heck, we went through all sorting methods. I had nothing to do at University for first 2 years, computer programming wise.
ahh, those were the times...
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
Sometimes it's best to just let stupid people be stupid.
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 them. I live in Houston, Texas and the only real competition we'd ever have is when sometimes the science+engineering magnet school in Dallas would drive down for some competitions. The local public highschools are a joke.
I was even in a winning senior division team of the US National ACSL competition. For the higher up competitions, its important to know the style of each competition and what kind of problems they give. ACSL even has a written section of the competition with strange concepts, it helped by just going through all their old written materials.
If you're in teams, it also helps to have the badass fast typer for those simple programs, in addition to the brilliant minded programmers to think about the hard ones while the others are typing.
Its good experience and usually a fun time I guess. But in the end, even winning a national competition usually doesnt do anything for you. I think my school won a scanner and some software that I never saw again. Yay
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 were not necessary here at all.
So, my advice is, try to find out as soon as possible (preferably before the competition, at the very beginning otherwise) whether they want smart algorithms or just something that works. It can save you a lot of time during the contest.
Online contests are a good practice. For example, the Saratov State University (http://acm.sgu.ru/) has harsh time and memory limits while other contest sites give you heaps of resources to use.
Live online contests are also great fun and practice. I remember winning a T-Shirt and some money at Bitwise a couple of years ago solving some neat problems in the process.
Finally, practice makes perfect. Get old problems and practice, practice, practice, ...
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.
What the hell is ?
Shouldn't his template use instead of and instead of , not to mention probably #include'ing ?
General Relativity: Space-time tells matter where to go; Matter tells space-time what shape to be.
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 reference doesnot do good as it takes time. I find these competitions more a measure of typing speed and quick fix solutions rather than an assessment of creativity, quality programming and problem solving skills. In my opinion, a problem solving contest would be a better idea, where contestants could write down or type algorithmic solutions to problems and the most efficient solution would get rewarded. Ofcourse, evaluating such a contest would be more difficult too.
It was a neat thing for students at Stevens Institute of Technology, my alma mater, 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, Cornell, Yale, Columbia, and so on. One major organizer behind it all is now working at Amazon right out of college, for what it's worth.
This sig donated to Pater. Long live
Is this anything like the UFC?
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 on an incorrect approach.
3. Have some algorithms pre-prepared. Examine previous questions for clues. Generally, we always saw date style problems (what day of the week is 24 November, 3100?) and area style (take a sheet of metal, cut out some shapes, what area is left?) problems. Both of those tended to be difficult and worth a lot to fix. Having an infinite precision math library ready to go is very useful.
4. Keep track of time and don't ever give up coding. You might get the answer in just before the deadline and that can be the difference.
Some people appear make a living out of it.
Top Coder run competitions on a monthly basis (e.g. who can write the best version of a s/foo/bar).. It's not open to people outside the US though.
thank God the internet isn't a human right.
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, 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.
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 micromouse that has long-range sensors and variable-speed motors. The days you could get away with stepper motors, simple switches on each side and a crude hardwired brain (no cpu) are long passed, although plenty such mice are run in the contests and are surprisingly close to being in the running.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
when you're a developer and aim for interesting projects, it's always pure competition. someone reviews your code behind your back and decides wether you stay two weeks or two years on that project. i got used to it, i do not recognize it anymore. and i never lost :)
On second thought, let's not go to Camelot. It is a silly place.
To be fair, the TSP is not an unsolved problem: it can be naively solved solved by using factorially many steps in the worst case (*grins and ducks*). Perhaps you meant unsolved in polynomial time? :)
These days most people believe it's not possible to solve the TSP in polynomial time, but maybe they still thought it might be possible in 1980, and they were trying to get "fresh eyes" to find the solution? Today we have (very good) polynomial approximations for the TSP based on minimum spanning trees, and there are also solutions to NPC problems that are faster than strict exponential time, so you could reduce the TSP to one of them and beat the naive factorial solution.
Anyway, you forgot to tell us how many cities and roads were involved. If it was only 5-6 cities, you might have been able to do it by hand even fully connected. If it was 10 cities, then you could have easily solved it on machines of the day using the brute force method. However, if it was 50 or 100, then you were probably SOL unless there weren't many roads.
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.
> why don't you found your own site, so that you
> have the final editorial say?
I've been thinking (fantastizing) of this for quite some time lately.
I mean, I come to slashdot to read the comments, not to see what the lame editors have to say. All they do is clicking the "approve" button from the submissions they get, and god knows what they do with their spare time. Quoth the famous saying "I could replace you (editors) with a very small shell script.".
It would be great if somebody with a big pipe and a few machines would start an alternate slashdot and dump this crap filled (as regards to "stories") one for good.
(Yes I know kuro5hin, but it's different...)
Don't quote me on this.
Let your programs fight each other while surreptitiously learning about assembly language.
www.corewar.info
i will build this site. i shall call it dotslash.org
"news for me,stuff that matters"
I won first place in both the ACTE, as well as the Computer Olympiad programming compteitions, years later they asked me to judge them both.
I'd be happy to answer any questions.
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 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.
Founder of Mirror Moon - Tsukihime Game Trans
Waterloo kicked my ass.
-Reid
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.
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
From the article/post:
which may be the overstatement of the posting year.For those who don't want to go read the article, here's the summary:
The shift key is only several centemeters from home position. Give it a shot so next time you do not come off as another clueless idiot.
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-test time, which is critical during a competition.
2. If writing templates beforehand is not allowed, bring one in on paper and take the 2 minutes beforehand (with the fastest typest in the group) to type it up. Ours consisted of an input loop/string parser with a loop that could be easily changed to accept input from the terminal (required for submitted programs) or a file (easier for testing sample input files.)
3. Know your language(s). Know what's allowed in the competition, have several references handy for each language you plan to use. My team tended to use Java, but at the time there wasn't a built-in priority queue in Java. Dijkstra's shortest path algorithm requires a priority queue, so I spent some time before hand coming up with a very easy to type ( 1 page) general purpose priority queue. We weren't allowed any electronic resources, but if you can type fast enough, you can create any basic structure you need very quickly. When built-in structures are available, USE THEM, and use them extensively.
4. Do the easiest problems first. Simple math will show you that you get the most points this way.
5. Study existing problems. The local competitions tended to repeat problems from other regional (or national) competitions. We used those to practice from, so it made it a breeze when those problems came up.
6. Don't get hung up on a problem. You'll waste tons of time, and there's ALWAYS the possibility that the submission checker is WRONG and your problem is right. Its happened at both regional competitions. They eventually find their mistake and your previous submission will be counted as correct.
7. Practice. You'll get used to the problems and be able to analyze how long a particular problem will take much easier. You'll get to know your teammate's strengths and weaknesses. One teammate of mine was very good at solving problems but his coding skills were a bit off. He'd write up the solution, I'd debug his programs. We did quite well that way.
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.
I'm feeling a little competitive today, so I think I better keep my tricks to myself. As the saying goes, "my win, your loss", right?
Have a nice day.
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.
I object to that article, and to the next reply.
I'll be honest when I say I at least skimmed the article, and my post wasn't meant to be a troll or point the finger at you so much.
What I said at the bottom part is true, so often, someone who knows barely anything writes the definitive guide- apparently though this does not apply to you and I'm sorry I got that wrong.
Bastards. :)
Sometimes it's best to just let stupid people be stupid.
btw, I just looked at the article again, maybe I missed it, but I still don't see anywhere that gives any indication of how many events you went/have been to?
The article mentions about three comps that I've been in, but they were fairly well hidden. SOrry for the confusion. Over the past year, I've been involved in about 4 (Australian Computer Programming Competition, twice, UNSW ProgComp and the SEARCC comp). Sorry for the confusion.
The thing that most seems to separate programming contest problems from real world problems is the "dirtiness" of real-world (rw) problems. Most abstractions one finds in rw often fall victim to the 80/20 rule, where 80% of instances fit the abstraction, but 20 percent don't. Most of the fiddle-faddle is dealing with the 20%.
Languages and techniques that make for snap-together abstractions needed for contests may not necessarily be the best to deal with the rw deviations from the abstractions, ie the "messy parts".
This seems to be because programming contests have to make the problem statements relatively short. If's, and's, and but's make for hard to read, hard to write, and hard to varify programming contest problems.
Table-ized A.I.
The Mathematical Contest in Modeling is a highly competitive worldwide contest that relies heavily on programming skill. In the 84 hours after the question is revealed, teams of 3 must formulate a modeling approach to the problem, implement it and write a paper on their method. An average winning paper will be a 60-90 page research paper plus 3-5K lines of source code.
Senior undergraduates are most successful as the problems require some sophistication to approach. In the end, it's probably a way for the sponsor to cheaply generate an enormous amount of quick research on their selected topic.
PS. Thank you, TopCoder, for paying for a semester of my college education! Yay competitive programming!
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.
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 forum...
Here are some more contests, accessible to everybody (not only students):
http://www.mathworks.com/contest/
which is a collaborative(!) competition
http://codewalkers.com/php-contest.php
holds a nice PHP contest, but seems to be inactive
http://dinsights.com/POTM/
holds a nice permanent contest, but there is nothing to win
http://www.recmath.org/contest/index.php
holds a tough contest, which just finished.
With IFCP, it's the hardest contest I'm aware of.
Do these competitions have rules dictating what languages one is allowed to use.
Seems it would be a bit unbalanced to force C paradigm coders to spend 15 minutes haggling thier way through something that a K guru or APLer could bang out in 30 seconds.
Just wondering.
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.
No worries ;o)
I (as well as other slashdotters probably) have varying levels of 'reading'. My first pass, I probably read about 40% of it, my second pass I probably read about 75% of it, and perhaps if I get a chance Ill do a more focused read and take in all of it.
As for my original post, it does bug me when there's someone who writes about their first and yet somehow definitive experience with something. I really did not intend to sound like a troll, but I suppose my wording left a stabbing tone- again 100% unintended.
-Looking forward to your next post.
(*cuts this sub-thread*)
I'm guessing from your comment that you know how to do this now but, for the less mathematically-literate slashdotter, here's the solution, in words of one syllable.
:)
In vector maths, one of the most useful operators is the dot product. It is useful because it has both an algebraic and a geometric formulation. The algebraic formulation is that (a,b,c).(d,e,f) = (ad,be,cf) - this allows you to calculate the damn thing on a computer. The geometric formulation is that, for two vectors X and Y, X.Y = |X| |Y| cos theta, where |V| gives the length of a vector V and theta is the angle between X and Y.
Say you have a plane in space, passing through the origin (the zero point). Consider a vector N that's normal to the plane (at right angles to every vector that lies on the plane). From the geometric formulation of the dot product, you can see that the set of points {X such that X is in the plane} is precisely the set of points {X such that X.N = 0} because, if a point is in the plane, the vector from the origin to that point is at right angles to N.
Unfortunately, we can't assume that our plane passes through the origin, so we need to generalise this a bit. What we find is that a plane is a set {X such that X.N = k}, where k is a constant equal to the minimum distance from the plane to the origin, or minus that distance (depending on which way the normal points).
So, we can now develop a strategy. If the corners of the tetrahedron are points A, B, C, D and we're trying to determine whether point X is in the tetrahedron, we need to figure out , for each set of three corners (for example A, B, C), whether X is on the same side of the plane generated by those points as the fourth point (for example D). You'll note that three points are sufficient to determine a plane.
If we can figure out the normal to that plane, we can take any point in it (A, for example) and thus find the magic constant k representing the displacement of the plane from the origin. We can then compare that constant to the values X.N and D.N - if X.N and D.N are on different sides of the constant k then the point X is definitely outside the tetrahedron; otherwise, X may be inside.
So now all we need to figure out how to do is find a normal to the plane. Sounds easy, but I'd wager that you won't be able to easily do it without the operator I'm about to describe: the cross product.
The cross product is the other important operator in vector maths. Just as the dot product represented (broadly speaking) the extent to which two vectors point in the same direction, so the cross product represents (broadly speaking) the area mapped out by the two vectors. The difference is that the cross product returns a vector rather than a scalar, and that vector always points at right angles to the two input vectors - it's normal to them. See what I'm getting at here?
I'll forgo long discussion of what the cross product is used for; I'll just say that it's often used to find volumes and is, in fact, the easiest way to find the volume of the tetrahedron. It is calculated as follows: (a,b,c)*(d,e,f) = (bf-ce, cd-af, ae-bd). I'll leave off describing where that expression comes from - the important thing is that we now have a normal to the plane generated by two points and the origin.
So, our algorithm will look something like:
- for each corner of the tetrahedron (call it D), take N = (B-A)*(C-A).
- calculate k = A.N
- if X.N k > D.N then X is not in the tetrahedron. Otherwise, repeat the above, choosing a different corner to start with.
- if none of the four iterations fail, the point is inside the tetrahedron.
And we're done
For the love of God, please learn to spell "ridiculous"!!!
http://dinsights.com/POTM/ is a semi-monthly contest that I have been watching for a while now. The problems are fun and interesting. The main objective is get the best "score" in the shortest amount of time. The solutions to past problems are very interesting reading. It's amazing what people do in the various languages. There was a problem several years ago that I still remember and think about: Take a map that gives various terrain altitude changes and find the shortest route (including distances traveled up and down) from point A to point B and back without crossing your "path".
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 science fair. Our FORTRAN code was functional and the results were there, but we were unable to present our results effectively.
In a coding comp. it is unfair to fight different styles agains each others in the same way that F1, monster truck and rally cars rarely compete.
So here are the 3 groups I want:
Text Book Class The code should be well laid out, commented, structured, follow and approved methodology and have full documentation.
Freestyle This is how you code at home and only has occasional comments, there are a few messy bits and losely follows a methodology, documentation optional.
Real World Work Place (RWWP) There is a design document but it bare little or and resemblence to the finished product and cyrptic comments. At random intervals the edjudicators will randomly change the specification and the competion .
In the not too distant future, next Sunday A.D.
Not sure if I'm being pedantic or not, but the problem
n script
Lois: Ah, what's the worst that could happen?
PETER ( to " Rock Me, Amadeus" ): I'm a tumor, I'm a tumor I'm a tumor, I'm a tumor, I'm a tumor I'm a tumor, I'm a tumor, I'm a tumor Oh, oh, oh, I'm a tumor.
The Administration's plan for peace in the Middle East is shallow and pedantic. I agree. Shallow and pedantic.
Peter: Mmm, I agree, as well. Shallow and pedantic. Hmm.
Lois: Everything all right, Peter?
Peter: Well Lois, since you asked, I find this meat loaf rather shallow and pedantic.
Brian: What is this? You're gonna talk down to everyone just because you won a game of Trivial Pursuit?
Peter: Perhaps.
http://familyguy.wikicities.com/wiki/Petarded/Tra
When I did my undergrad I spent my last 3 years doing the IBM competition. It was limited to a 3 person team, so many questions and a 5 hour time limit. Written materials allowed, no internet access or digital material (ie pre made code). My team got pretty Successful by our last year, just finishnig 7 seats out from going to worlds (not bad for a school nobody had ever heard of). Anyways, I found success in team programming competitions came from a bit of experience and building the right team. Since there was only one terminal you only need one person that knows the language you're coding. We had 1 guy that was truely amazing with C, and he did all the coding. the other two of us were much better problem solvers. The key was having a bit of practice and knowing how to pick out the easiest problems. Solve those as fast as you can, to rack up points quick. Then once we'd get a couple and be semi-stuck our coder would find one that wasn't too hard but would take a while to hack out. He'd work on that while the other 2 of us started tackling the difficult ones burning chalk on the blackboard and writing Pseudo code. By the time the easy one was done one of the other two could have pseudo code that the coder could quickly code while the other both problem solvers finished the partially solved one, or if too stuck could move on to any problems left. I think our team was successful because of balance, something any team benefits from. While I was a descent coder and so was the other problem solver, neither of us could code a doubly linked - circular linked list in a matter of minutes with no reference like the 3rd guy. However he would never have solved the problem to a point that he knew he needed that datastructure as fast as myself. So competative coding needs experience, balance of skills, and in a team situation, keep someone coding at all times if possible!
There is also this book on Amazon:
/ ref%3Dnosim/thealgorithmrepo/104-6058907-6739947
http://www.amazon.com/exec/obidos/ASIN/0387001638
I figured I'd get something wrong, but that's just... blatant :(
For the love of God, please learn to spell "ridiculous"!!!