Seriously, having competed in only 1 regional ICPC myself, I was blown away at the level of knowledge of some of the students. Some kids were coming in from high school with serious programming skills. Makes me sad when I go back to work now and never get to use any of these interesting algorithms.

NYU team coach here writing from Russia. :)

Indeed, most of the top competitors have been practicing since high school. We were lucky to assemble a team that has been training well before.

MIT's team consists of freshmen who are still in good training since their national high school math olympiad trainings from their respective countries.

What puzzled me is that training for high schools varies so much that not all students interested was given some basic help.

Sounds really interesting. Do you have any links to the resources you found?

I highly recommend the book Competitive Programming 3 by Steven and Felix Halim (https://sites.google.com/site/stevenhalim/). I prefer the larger print version as it's much easier to read and have laying on your desk. It has tonnes of references to problems on the UVa Online Judge (another popular judge site) at the end of each chapter so you can work on problems relating to the covered theory.

My first serious introduction to algorithms was through Tim Roughgarden's 'Algorithms: Design and Analysis' course on Coursera. It's a nice formal introduction and really focuses on and builds an intuition for how to think about problem solving like a computer scientist. I'd also recommend Steven Skienna's Algorithm Design Manual as it's written in a similar style.

As mentioned earlier, the TopCoder Online Judge is a great tool to practice problems as well. I could never find a tutorial which covered how to effectively use TopCoder as a practice tool so I wrote one for my programming club: http://acx0.com/cpc/topcoder.html (note: the rest of my site is a complete mess right now)

Of course, there's tonnes of other resources out there but these would be my top recommendations so far.