The course looks really interesting to be frank. I've recommended it to my college's competitive programming team actually!
ITMO did not get 1st place this year because the team changed, and I believe tourist graduated. Last year [1] for example they solved all 13 problems, while the 2nd team solved 11; there simply was no competition.
7th is still an excellent result. Let's see what they do next year!
Why are Russians so historically good at these competitions?
China have raw numbers, America has the resources/ecosystems to train and prepare these programmers. Russia seems to have neither and regularly outperform both nations.
There is a math culture among Russians that helps here. The whole phenomenon of Math Circles that are coming up now in the US were a Russian idea that the (now, not so) recent immigrants brought with them. US math education is too much about the mechanics of arithmetic. Russian math education is more about creative problem solving using real math. If you go to a Math Circle, you see that the kinds of problems the kids are working on require the same kind of problem solving skills that you engage when programming.
The difference is evident when you observe the typical sophomore-level discrete math class in US universities. Most of the students have that deer-in-headlights look that shows they are struggling with the basic concepts of logical reasoning and how to write a proof like a grown-up. Kids from what I'll call "enriched" or "non-traditional (in the US)" math education have been doing that stuff since middle school and are a little bored.
(Off-topic asides: 1) If your kid likes math, look for a local Math Circle. They all vary, but hopefully you live near a good one. 2) If your kid is a middle-schooler and really likes math, I highly recommend the MathPath camp -- see mathpath.org.)
I believe that it is because of two reasons [massive generalization follows...] (1) emphasis on math and physics (2) stress on discipline and rote learning. US students have (1), Chinese have (2), Russians have both. You would realize that most competitors in these contests end up doing pattern matching with previously solved problems. In addition, they keep a catalogue of most asked questions, common codebase, etc. for reference and pulling out code. I do not think that these competitions produce good programmers as they incentivize writing quick, ugly, non-resusable code.
While you are correct in pointing out that these contests only test a relatively narrow subset of the skills needed for good programming, I don't think it would be correct to say it's based on "rote learning". There can be some amount of pattern-matching, but it's not as if you can just read the solutions to 100 problems and expect to do well.
Also, I know for a fact that many (but not all) people who were good at these contests are also good all-around programmers. (In fact, you probably do better at these contests by writing more readable code, even accounting for the time cost. But some people can get by with messy code as well.)
Once you have solved your first 1000 problems in programming competition situations, you become really good at writing code that compiles and even is correct in the first go.
For me, practicing for programming competitions alongside the job as a software library maintainer really boosted my C++ skills faster than anything else could have.
Absolutely true! Competitive programming is shear waste of time. While it's necessary to know basic algorithms that get used in day to day work, there is no point memorizing all the algorithms. Sadly, most technical interviews pay a lot of importance to this kind of memorization. For solving real world problems one needs to research and find the right solutions as and when the need arises. This is what real learning is all about.
I don't think raw number explains the Chinese performance. India has a comparable population, arguably better positioned to do well in ACM (English-speaking country with a strong IT sector). However you don't see many Indian universities here.
On interesting thing to note is the ACM World Final ranking usually doesn't correlate perfectly with perceived ranking of the school, even the ranking of its CS department.
Another point is, ACM is fun, but if you purposefully train for it, you reach the point of diminishing return quickly. Being a former Olympiad in Informatics contestant (high school equivalent of ACM), I find these kind of competition absolutely not helpful in real world programming. It does help me pass the interviews.
In China at least, ACM is perceived a way to prove oneself to potential graduate schools in America and employers. And I do know employers give very high priority to these students - even Google.
So, the reason the Chinese is good at it is mostly, this is not a hobby, but a high stake exam. It is a way to land at prestigious graduate program or job.
Why isn't the US, and why aren't top universities doing as well as we may think they would be? Because they have better options than ACM.
As a former participant in these types of competitions, I can confirm.
The teams that win are the teams that practice extensively. Universities like St.Petersburg care a lot and have official programs for preparing for the ACM competition. The students care a lot too as the competition is a way for them to distinguish themselves.
US universities, at least the top ones, don't care that much. American students have better things to do, as you said. If you look at a typical US university team, you'd see a lot of Chinese and Eastern European students that have done IOI in high school. Their advisor would be a professor who typically just signs the paperwork.
The Chinese will get there, if they haven't already. They have got top universities, the economy rivals Japan and Germany and soon the US; the tech powress is on display with giants like JW, Baidu, Ali Baba, Tencent making mockery of the competition. Not to leave out the hardware sector-- Lenovo, Acer, Asus, Xiaomi and countless other companies gaining market share from their US counterparts world wide...
Are an overwhelming number of Chinese ladder climbers? I don't think so.
Posting nice sales numbers does not equal to organic strength. On the other hand, numbers alone do not provide insights.
I know many Chinese are feeling strong with just numbers since we did not have that kind of numbers for a long time. But we are still playing games invented by other explorers mainly in our backyard.
We are so used to playing existing ones that numbers became the only thing matters. What is invention? Never thought of it.
Sure, current Chinese elites can enjoy high life while having a decent way out. A nation not wanting to face its true weakness and strength is going nowhere.
Strong tradition of STEM education, back from the Soviet times. Military complex was very strong in the USSR, which resulted in quality education (again, just STEM, not so in humanities) - basically, you need to know physics and maths very well to build the bomb.
I guess that applies to other Eastern bloc countries to some extent (see Polish universities at ##5, 9 and 25, Ukraine at #11, Belarus at #17).
In case of Poland it helps that algorithm competitions are popular in high school. Each year top winners get a free pass to entry any CS university. So if you SAT style exams are not your thing there is an alternative way.
> Why are Russians so historically good at these competitions?
Memorization of algorithms.
In addition, programming competitions always seems to have an overabundance of Computational Geometry problems which are really hard if you have never seen them before but relatively straightforward if you know the correct algorithm off the top of your head.
I prefer to see the "head-to-head" competitions over some competitive task than these. Sometimes, a simple but clever hack does better than advanced algorithmic programming (and sometimes not).
That's not really true. The selection of computational geometry problems on the ICPC tends to be limited because testing and implementing numerical algorithms is really difficult in a competition environment. When you do see geometry algorithms they tend to be "trick" problems or else don't use any really deep or hard results.
You don't need to memorize them. You can have some amount of printouts with you, which teams usually use for having a bugfree implementation of stuff like arbitrary graph matching, maximum matching of lowest cost, 2SAT or just Gauss elimination.
At the same time these advanced algorithms do not get used very often -- in the 2 finals I took part in we've used something from out printouts maybe once.
I can confirm. Itmo normally has at least 3 equivalent teams at any time that compete against each other during the regional stage. There are also specialized study groups and slight preferences (exam and schedule-wise) for those who are serious about competing in team contests.
I guess it's the same reason why Indian Americans here in the US win spelling bees. They care about it more than others. These students go through a ton of training with coaches and camps specifically conducted for this purpose. There's a lot of nuances and tricks to be learned in competitive programming.
So while the participants obviously have a high aptitude, it's the training that puts them on the top.
In the US, the smarter students don't generally waste their time with these programming competitions. Grades, research, and extra credit would matter more towards a student's academic success. These contests generally appeal more to "hobbyists" or those who have nothing better to do with their time, and so you get biased results.
Can someone explain the significance of this competition? I've never heard of it before and am just looking for a little understanding of what, if anything, there is to read into the results.
Competitive Programming is a sport where teams(or individuals in some instances) compete with each other to solve a set of algorithmic questions in the shortest time. This generally happens on a system called the Online Judge which is basically a system for code evaluation.
ACM ICPC is basically the Olympics of Competitive Programming.
The significance can vary from person to person but sometimes Universities and Companies look favourably at good results in such competitions.
So, like the olympics, the important member organizations put a reasonable enough amount of effort into it to ensure they're represented well? Like, I really should be looking at UCF as a college that produces some of the best programmers in the US?
The members that perform well are those who have the organisations which care. It doesn't necessarily translate to a great CS program at the university. Sometimes teams are also carried by one or two brilliant competitive programmers that crop up from somewhere and then disappear in four years time.
If you attend UCF, join the programming team, and make it to regionals your peers will be some of the best programmers in the US and you will be able to rely on those connections for the rest of your career. Just attending UCF guarantees little.
So it's taken seriously by universities? Like CalTech really put its best foot forward and got smoked by UCF? And American Universities really are doing this poorly in CS competitions relative to the rest of the world?
UCF is a great example and one that I'm familiar with. UCF has a faculty member that's very involved in their programming contest program. That brings a lot more consistency, probably a little money, makes it easier to recruit students, etc. They have a great library of problems to practice on. They also run a high school programming contest which helps identify talent and recruit, but also helps get more UCF students involved.
When I was at nearby USF, our programming contest teams were student-run. It's not a priority for the department and there is a lot of inconsistency as students come and go. There's also a smaller pool of participants to draw from. We did reasonably well for a little while when I was there and put a bunch of time into it, recruiting, teaching, running practices with and without other unis. But it takes a lot of effort.
I have always found a lack of books on advanced things that I've encountered in competitive programming like Fenwick trees, link-cut trees, rmq etc. Can anybody recommend book(s) that contain these things?
I don't know how many books there are on those topics. A lot of the data structures in higher level competitive programming problems have pretty niche uses. It might be best to look at papers instead. Here's one on the Fenwick/Binary Indexed Tree:
Check out Competitive Programming by the Halim brothers. One of the best books on the subject, explains many algorithms and different problem types you will find in a competitive setting. The book also includes solutions to 100s of UvA problems.
Would like to give my congratulations to my school, the 99th place University of British Columbia. The team is composed entirely of first-time World Finals participants!
I did a competitive programming course in undergrad, these problems are really interesting if you're not familiar with it. I highly recommend folks try a few problems and look at the solutions. It can be really eye-opening.
However, I really haven't applied much of what I learned doing the problems to "real" work. It's cool to see methods of looking at things differently, but just doesn't translate well to software development.
Speaking as a former ICPC competitor/coach, I think the aspect that most directly translated to professional software development was getting practice at quickly writing and reviewing code for performance and correctness.
A bit of background about ICPC, for those who don't know: It's a team competition. You have 3 contestants on a team, but only one computer on which to write, test and submit your code. Most of the work of solving a problem is usually done in your brain or on paper, so typically, one person will be coding at a time while the other two think about problems and get ready to rotate to the keyboard.
But although the primary scoring criterion is number of problems solved, you also get penalized for time taken and incorrect attempts. So it's really important to be able to glance over someone else's shoulder and notice things like "oh, there's an off-by-one error in that loop condition" or "you forgot about such-and-such an edge case".
That's fair. It's definitely good for training/exercising the syntax parser and debugger in your head without relying on an IDE or compiler errors. And you definitely have to plan ahead to complete the problems in the time allotted. Debugging in my head has always been one of my strong suits so I tend to forget that other people have other strengths first. :)
I look at these rankings, and can't help but notice that it's basically whatever school has a club that really cares. Looking at the American schools, no one is going to rank the computer science program at the Illinois Institute of Technology above the University of Illinois Urbana-Champaign.
Surprised that Kaist is so far up there. While they are the best in science in Korea and they do have a dedicated team that practices, they still have very few students in undergrad.
I organized these for freshmen at my school. Reading through these comments we had small chance of getting to these levels since other places offered competitive programming courses.
[1] https://www.edx.org/course/how-win-coding-competitions-secre...