There are several programming contest books, but what do they contain and how good are they? Of course, it is difficult to know before buying and reading them. In this blog post I review programming contest books that I have read.
Do you know other books or have different opinions?
- Programming Challenges: The Programming Contest Training Manual
- URL: http://www.programming-challenges.com/
- Authors: Steven Skiena & Miguel Revilla
- Year: 2003
- Price (Amazon): 56.67 USD (paperback)
This is a classic book about programming contests, written more than ten years ago.
The book contains 14 chapters that discuss topics such as data structures, combinatorics, dynamic programming, and computational geometry. Each chapter begins with an introduction to the topic, followed by a collection of programming tasks.
A lot has happened in the world of programming contests during the last ten years. While many chapters of the book are still relevant in modern contests, a lot of important material is missing. For example, the segment tree data structure is not even mentioned in the book.
The text of the book is well written and easy to understand. However, the quality of the code examples is not good. For some reason, everything is coded using pure C, and many implementations are cumbersome and unnecessarily long. I was astonished to see implementations of Prim's and Dijkstra's algorithms with quadratic time complexities.
It is clear that the book is outdated, and mastering the techniques presented in the book is not enough today. Still, it is nice to read the book, and it contains some material that I have not seen in other sources.
- Competitive Programming 3: The New Lower Bound of Programming Contests
- URL: http://cpbook.net/
- Authors: Steven & Felix Halim
- Year: 2013
- Price (Lulu): 26.99 USD (paperback), 35.99 USD (hardcover)
This book is an introduction to data structures and algorithms that are needed in modern programming contests. The book is intended for readers who have some background in algorithm programming. Both basic and advanced techniques are discussed.
A lot of material is covered in the book. There are nine chapters, and the first three of them concentrate on problem solving and data structures. After this, the next chapters discuss graph theory, mathematics, string processing and computational geometry. Finally, there are two chapters that contain more advanced material.
The book is a good resource for getting a general picture of the topics that appear in programming contests. However, many algorithms are discussed so briefly that it can be difficult to really learn them from the book. So, while the book tells you what techniques you should learn, there are often better sources where you can actually learn them.
A general feeling when reading the book is that it is a draft of a book instead of a published book. The quality of the text and the pictures is often not good. In addition, there is too little empty space in the layout which makes the book difficult to read.
When I read the book for the first time, I suddenly noticed that I have read the same text before. Unfortunately, some content in the book is copied almost word for word from the USACO training pages without mentioning this to the reader.
While there are severe drawbacks in the current version of the book, it is still the best introduction to programming contests I have read. The authors know what they are speaking about, and the techniques discussed in the book are relevant in modern contests.
- Looking for a Challenge? The Ultimate Problem Set from the University of Warsaw Programming Competitions
- URL: http://www.lookingforachallengethebook.com/
- Year: 2012
- Price: 30 EUR (hardcover)
This book contains a collection of tasks from Polish programming contests organized by the University of Warsaw. The book is written by a group of authors who have studied and worked at the university. There are 53 tasks in total, and for each task, the book contains a task statement and a detailed analysis how to solve the task.
First of all, this is not a beginner's book. Most tasks are difficult, and the book assumes that the reader already has a strong background in programming contests.
An experienced contestant can learn a lot from the book. The analyses are very well written. Typically, an analysis begins with a history how the task was invented. After this, different ways how to approach the task are discussed. The analyses are mathematically rigorous but accessible.
The only drawback in the book is that it is difficult to obtain. It can be ordered through the website of the book, but this is not as easy as one could think. Tip: if you don't get a reply for your order, try to send another order.
By the way, many tasks from Polish contests are available for practice at http://main.edu.pl/. Polish tasks are usually both high-quality and difficult, so they are good material for practicing.