Yes, they had also algorithmic problem solving skills. But they learned huge amount of algorithms and datastructures so that they don't have to derive them each time. And they spend time literally training how to write them fast without mistake.
It was not just about problem solving skills. It was a lot about knowledge base.
You can read one moderate length book and know all of the DSes and algorithms you'll need for 99.9% of the time. cses.fi/book is a good one with a free version if you're curious.
https://github.com/kth-competitive-programming/kactl may also be of interest, it contains a good amount of the algorithms/DSes you'd ever need on a few printable pages (20ish).
Not sure why would that be surprising. Same thing happen in chess, scrabble, anything competitive. Once there is enough competition, you can't go in with hope and talent alone. You have to train specifically for competition format.
Chess players don't base their play on pure problem solving either. They memorize and train specific plays.
It's surprising because I also do competitive programming, and I know many people who do it, and I haven't encountered anyone in those circles memorizing algorithms. In fact, many competitions explicitly allow you to use a pre-written library. Some IRL competitions even allow you to bring in written materials. (Not all competitions allow this, I know.)
That's not the point of competitive programming. If you talk to anybody who is good at competitive programming, they will tell you it's _not_ about memorizing algorithms and datastructures. It's about developing algorithmic problem solving skills; skills that you can leverage to design (create) algorithms, in order to solve problems.