Introduction to ICPC algorithm problem solving
Roadmap for learning how to crack coding challenges in a competition or interview!
I will assume that you know how to code. My goal will be to list cool material to master algorithms problem-solving. That will help you if are:
- preparing coding interviews.
- training for competitive programming.
- just wanna improve your problem-solving skills.
I will focus on competitive programming as I had a great experience and trajectory on this (I was ICPC Finalist, LATAM champion, World Final coach, interned at CodeJam, international professor at Training Camps, etc).
If you are preparing for interviews you will be a very good shape by following this guide. But remember to practice on the whiteboard and sharpen your communication skills also, they will evaluate if you like you as a potential teammate.
There are many online sites with algorithms problems but many of them will not be useful if your objective is succeeding in ICPC (for example problems from project Euler are definitely fun, but not the optimal way for training ICPC). In the same way, other hobbies like math competitions or chess will help you to develop a logical way of thinking but they are not optimal if your #1 objective with them is to prepare for a programming contest.
Submit, submit and submit
It’s fundamental to always solve problems available on an Online Judge. They are sites that will automatically correct your solution. This is very important to:
- Learn how to code bugless and not forget corner cases.
- Be sure your idea behind is correct and efficient enough.
Remember: online judges are very strict. Even if you do a case mismatch or put in an extra space it will correct your solution as wrong.
What should I do?
- Read the 3 books listed in the material section. All of them have code and are oriented to programming challenge solving. Do not try to read heavy algorithm books like Cormen, they are good for looking for specific references (when we need help with some topic) not for covering them. I will recommend starting with “Programming Challenges”. Read the books in parallel: first, read the introductory chapters of all three, then cover the initial problems of all, and then start studying topic by topic from all three. That way you will enrich by comparing different devices and points of view of each topic or concept.
- Create an account on Codeforces. They organize contests regularly and the problems are, in general, amazing! Don’t forget also to search in Codeforces for any theoretical concept you like: they have blog entries written by the users, and many of them are really good. For example, look for “Codeforces string hash” on google, and you will find many results.
- If you are training for ICPC, try looking for ICPC contests in the Codeforces Gym section. where you can simulate being in a contest: virtual participation, with the score as if you assisted the real contest! Many ICPC regionals are available in this section.
- Always do up-solving: you become better only by solving the 25% of the contest you didn’t solve during the competition time. So if you are in a team competition (10–12 problems) do 2–3 problems with your team from the one you didn’t solve. If you are competing for individual competition (~5 problems), solve 1–2 from the ones you didn’t. You only improve by solving problems that are challenging for your current level. So facing too easy or too hard problems is useless for improving.
- If you really are into Competitive Programming, consider assisting to a Training Camp. They are a really intensive course (typically 2 weeks with theoretical classes in the morning and contests during the afternoon). You and your team will make boost knowledge and problem-solving each time you assist one of them. Take the competitions seriously and compete as if you were in a real contest. Argentinian Training camp is great (you have the PDF of all classes from all the editions uploaded). Brazilian UNICAMP Summer training camp is amazing (usually assist top competitors from the strongest regions of East Europe or Russia).
- Each time you learn some technique, algorithm, or data structure, you must submit many problems. If not is useless!
- Surround by a community enthusiastic about problem-solving. This will enhance constantly beating yourself. That’s why is good to participate in communities like Codeforces.
Recommended books and other material:
- “Programming Challenges” — Steven S. Skiena
The introductory section is SUPER friendly. It doesn’t cover very advanced topics. Recommended for starters. They use problems uploaded to UVa online judge.
- “Competitive Programmer’s Handbook” — Antti Laaksonen
I like the style of the book and the introductory section is very nice for newcomers. I recommend the section Time Complexity for anyone who is not familiar with big O notation. It has a very simple and short intuitive explanation.
The problems that appear in this book (and some others!) are compiled on the site: https://cses.fi/problemset
At the same time is very complete so be aware that advanced chapters can be hard, read them only when you cover the basics from all three books.
- “Competitive Programming” — Steve Halim
Great book for ICPC. The introductory section contains many tips for competitors. It covers all the necessary topics from achieving a very good result in competitive programming and has a section with more advanced topics.
- e-maxx.ru: A collection of MANY posts about different algorithm topics (many very advanced but well explained). You must translate it from Russian.
- URI online judge: A Brazilian judge I like because it has problems sorted by hardness. Seeing the problem difficulty is especially good for beginners because when you start you don’t have an intuition of the hardness of a task. There are problems that can look pretty easy and are really hard of solving correctly.
If you liked this post / my style follow me.
I will try to keep on posting regularly about Algorithms, SE, Web, and ML always with these objectives in mind:
- keep it short
- being meaningful
- explain with examples