Guide to Competitive Programming: Learning and Improving Algorithms Through Contests

by Antti Laaksonen

Building on what already is the most comprehensive introduction to competitive programming, this enhanced new textbook features new material on advanced topics, such as calculating Fourier transforms, finding minimum cost flows in graphs, and using automata in string problems. Critically, the text accessibly describes and shows how competitive programming is a proven method of implementing and testing algorithms, as well as developing computational thinking and improving both programming and debugging skills.

Topics and introduces dynamic programming and other fundamental algorithm design techniques, and investigates a wide selection of graph algorithms; compatible with the IOI Syllabus, yet also covering more advanced topics, such as maximum flows, Nim theory, and suffix structures; surveys specialized algorithms for trees, and discusses the mathematical topics that are relevant in competitive programming; reviews the features of the C++ programminglanguage, and describes how to create efficient algorithms that can quickly process large data sets; discusses sorting algorithms and binary search, and examines a selection of data structures of the C++ standard library; covers such advanced algorithm design topics as bit-parallelism and amortized analysis, and presents a focus on efficiently processing array range queries; describes a selection of more advanced topics, including square-root algorithms and dynamic programming optimization.

















Fully updated, expanded and easy to follow, this core textbook/guide is an ideal reference for all students needing to learn algorithms and to practice for programming contests. Knowledge of programming basics is assumed, but previous background in algorithm design or programming contests is not necessary. With its breadth of topics, examples and references, the book is eminently suitable for both beginners and more experienced readers alike.

Genres: Programming, Computer Science, Algorithms, Science, Coding, Technical

330 pages, Kindle Edition

Published May 8, 2020

Reviews

[Max Pietsch · Rating 5 out of 5]

This book could be better. Specifically it could have questions and solutions for each section. However it has some info I haven't found elsewhere, and definitely had good insight into some types of problems.

[Mikhail Filatov · Rating 3 out of 5]

Описание задач на международных олимпиадах по программированию, основанное на std C++.
Ряд интересных алгоритмов, с которым не встречался раньше - например, counting sort.
Из минусов - много опечаток в листингах. Несколько раз думал, что я совсем тупой, пока не убеждался, что i и j перепутаны.
Главный же недостаток - эта книга больше похожа на шпаргалку, так как содержит информацию совершенно разного уровня абстракции - для каких-то задач автор описывает детали реализации в C++, обсуждая нюансы std, где-то приводит псевдокод, где-то лишь идею алгоритма.

[Vladimir]

Really good book for people that aren't complete beginners but aren't that advanced either. The explanations, illustrations and implementations are all pretty good.

[Michael · Rating 4 out of 5]

Good overview of algorithms, but is much easier to read if you already know derivations and proofs. A lot of details are omitted about formality, but it helps keep the book short.

I like this book more for how compact it is and groups algorithms together, rather than how it teaches content, which I think would be very dense for someone new to the subject.

There are also a lot of more complicated algorithms that might be used in competitive programming that were not covered, e.g. maximal matching, augmenting paths, blossom algorithm, geometry, etc.

There also felt like a lack of formal proofs in the book for why algorithms worked. This is fine given the conciseness, but I felt a lot of times wondering if algorithms were meant to work or not (e.g. I was not convinced. Ofc it's supposed to work, but a short proof or intuition would be nice).

I think it would also be nice to explain tradeoffs between using different languages, e.g. C++ vs. Java vs. Python, and also maybe some basic concepts related to performance, such as memory management, instruction execution, locality, etc.

[Monirul Haque · Rating 5 out of 5]

Those who are interested in competitive programming can kickstart with this book.

[Vlad Cainamisir · Rating 5 out of 5]

Probably one of the most underrated books for algorithms and data structures