Competitive Programming

This is the companion web site for a book: "Competitive Programming 4: The Lower Bound of Programming Contests in the 2020s" and its three past editions written by myself (Steven Halim - UVa status, Kattis status), my younger brother (Felix Halim - UVa status, Kattis status), and my friend (Suhendry Effendy - UVa status, Kattis status) in 2010 - present. This book is used in my course in School of Computing, National University of Singapore: CS3233 - Competitive Programming (2009-present) and available for wider audiences since 2010. This book contains a collection of competitive programming skills gained by solving more than 3458+ UVa (1999-present) plus Kattis (2015-present) online judge problems and being involved in the ICPCs (since 2001) and the IOIs (since 2009) in various roles: contestants (long ago), coaches, judges, Regional Contest Director, and/or International Committee member.

Objectives

Our objective in writing this book is similar with the IOI objective+ICPC vision: to further improve humanity by training current students to be more competitive in programming contests. The possible long term effect is future Computer Science researchers who are well versed in problem solving skills. We use C++ (primary), Java, Python, and OCaml code to illustrate the algorithmic concepts, i.e., we dislike vague pseudo-code commonly found in many other Computer Science textbooks. We also use visualization tool: VisuAlgo to help explain the data structure and algorithm concepts to our audiences and beyond.

Target Audiences

This Competitive Programming book, 4th edition (CP4) is a must have for every competitive programmer. Mastering the contents of this book is a necessary (but admittedly not sufficient) condition if one wishes to take a leap forward from being just another ordinary coder to being among one of the world's finest competitive programmers.

Forewords for CP4

"The authors are seasoned competitive programming experts who have dedicated decades of work to help at all levels of the sport."

Bill Poucher, ICPC Executive Director and President of ICPC Foundation

"Steven, Felix, Suhendry in the past two decades, have grown from contestants, to coaches and, finally, masters in the art of competitive programming."

""Competitive Programming" and Kattis share this motivating principle: to make learning computer science and programming accessible for everyone."

"As director of the USA Computing Olympiad and coach of my University's ICPC teams, I have seen firsthand how competitive programming has become a key part of the global computing talent pipeline - both academia and industry are now filled with present-day superstars who were formerly superstars in competitive programming."

Selected Testimonials for CP1/2/3

"Competitive Programming 3 has contributed immensely to my understanding of data structures & algorithms. Steven & Felix have created an incredible book that thoroughly covers every aspect of competitive programming, and have included plenty of practice problems to make sure each topic sinks in. Practicing with CP3 has helped me nail job interviews at Google, and I can't thank Steven & Felix enough!"

Troy Purvis, Software Engineer @ Google

"Steven and Felix are passionate about competitive programming. Just as importantly, they are passionate about helping students become better programmers. CP3 is the result: a dauntless dive into the data structures, algorithms, tips, and secrets used by competitive programmers around the world. Yet, when the dust settles on the book, the strongest sillage is likely to be one of confidence---that, yes, this stuff is challenging, but that you can do it."

Dr. Daniel Zingaro, Associate Professor Teaching Stream, University of Toronto Mississauga

"CP-Book helped us to train many generations of ICPC and IOI participants for Bolivia. It's the best source to start and reach a good level to be a competitive programmer."

Jhonatan Castro, ICPC coach and Bolivia IOI Team coach, Universidad Mayor de San Andrés, La Paz, Bolivia

"Reading CP3 has been a major contributor to my growth, not just as a competitive programmer, but also as a computer scientist. My entire approach to problem solving has been improved by doing the exercises in the book; my passion for the art of problem solving, especially in contest environments, has been intensified. I now mentor several students using this book as a guide. It is an invaluable resource to anyone who wants to be a better problem solver."

Ryan Austin Fernandez, Assistant Professor, De La Salle University, Manila, Philippines

"I rediscovered CP3 book on 2017-2019 when I come back to Peru after my master in Brazil, I enjoyed, learned and solved many problems, more than during my undergraduate, coaching and learning together in small group of new students that are interesting in competitive programming. It kept me in a constantly competition with them, at the end they have solved more problems than me."

Luciano Arnaldo Romero Calla, PhD Student, University of Zurich

"CP1 helped my preparation during national team training and selection for participating the IOI. When I took the competitive programming course in NUS, CP2 book is extensively used for practice and homework. The good balance between the programming and theoretic exercises for deeper understanding in the book makes CP book a great book to be used for course references, as well as for individual learning. Even at the top competitive programming level, experts can still learn topics they have not learnt before thanks to the rare miscellaneous topics at the end of the book."

Jonathan Irvin Gunawan, Software Engineer, Google

"Dr. Steven Halim is one of the best professors I have had in NUS. His intuitive visualizations and clear explanations of highly complex algorithms make it significantly easier for us to grasp difficult concepts. Even though I was never fully into Competitive Programming, his book and his teaching were vital in helping me in job interviews and making me a better coder. Highly recommend CP4 to anyone looking to impress in software engineering job interviews."

Patrick Cho, Machine Learning Scientist, Tesla

"Flunked really hard at IOI 2017, missing medal cutoff by 1 place. Then at the beginning of 2018 Steven Halim gave me a draft copy of CP3.1 / CP4 and I ended up getting a gold medal!"

Joey Yu, Student, University of Waterloo, SWE Intern at Rippling, IOI 2018 Gold Medalist

"As a novice self-learner, CP-book helped me to learn the topics in both fun and challenging ways. As an avid and experienced CP-er, CP-book helped me to find a plentiful and diverse problems. As a trainer, CP-book helped me to plan ahead the materials and tactical strategies or tricks in competition for the students. As the person ever in those three different levels, I must effortlessly say CP-book is a must-have to being a CP master!"

Ammar Fathin Sabili, PhD Student, National University of Singapore

"I've been in CP for three years. A rookie number for all the competitive programmers out there. I have a friend (still chatting with him today) who introduced me to this book. He's my roommate on our National Training Camp for IOI 2018's selection. I finally get a grab of this book in early 2019. To be honest I'm not the `Adhoc' and good at `Math' type of CP-er. I love data structures, graph (especially trees) And this CP3 book. Is a leap of knowledge. No joke. I met Dr Felix when I was training in BINUS, I also met Dr Steven when I competed in Singapore's NOI and one of my unforgettable moment is, this legend book got signed by its two authors. Even tho the book is full of marks and stains, truly one of my favorite. Kudos for taking me to this point of my life."

Hocky Yudhiono, Student, University of Indonesia

"I bought CP3 on 7th April 2014 on my birthday as a gift for myself and it has been the most worth-it 30USD spent by me on any educational material. In the later years, I was able to compete in IOI and ICPC WF. I think CP3 played a very big factor in igniting the interest and providing a strong technical foundation about all the essential topics required in CP."

Sidhant Bansal, Student, National University of Singapore

"I have always wanted to get involved in competitive programming, but I didn't know how and where to get started. I was introduced to this book while taking Steven's companion course (CS3233) in NUS as an exchange student, and I found the book to be really helpful in helping me to learn competitive programming. It comes with a set of Kattis exercises as well. This book provides a structured content for competitive programming, and can be really useful to anyone ranging from beginners to experts. Just like CLRS for algorithms, CP is THE book for competitive programming."

Jay Ching Lim, Student, University of Waterloo

"My memories about CP3 is me reading it in many places, the bus, my room, the library, the contest floor...not much time had passed since I start in competitive programming reading CP3 until I got qualified to an ICPC World Final"

Javier Eduardo Ojeda Jorge, ICPC World Finalist, Universidad Mayor de San Simón, Software Engineer at dParadig, Chile

"My name is Alisia Maria Lupidi and I am an ICPC contestant. I take part in the SWERC and this month (July 2020) I won the gold medal at the Girls ICPC ACPC. My boyfriend, who is a bronze medalist at the SWERC, gave me the CP4 yesterday (30 July) as a present for my birthday (soon). I would like you to know how important your work is for us contestants and to thank you for writing the best birthday present ever!"

Alisia Maria Lupidi, Gold medalist of Girls ICPC ACPC July 2020

Errata

While we strive to minimize the number of errors in the book, it is near impossible to have 0 error in a 681 pages Book 1+2 dispite of multiple re-reads.
Here are the list of known (minor) issues that are found after Sunday, 19 July 2020 initial release.

Daily CP4 publicity hype, skipping Sundays (in reverse chronological order) --- publicity campaign ended:

Major update (Wednesday, 01 January 2020): CP3 (2013 edition with a bit of 2018 upgrade) is now available in Spanish language. If you are a Spanish-speaking programmer, we recommend that you get the Spanish version that has been translated over the past 1+ year by Miguel Revilla Rodriquez (the current admin of (UVa) Online Judge). Here is the Amazon Link, ISBN: 978-1711024813.


Major update (Tuesday, 24 October 2017): CP3 is now available in Korean language. If you are Korean, we recommend that you get the Korean version that has been translated over the past 1+ year by lewha0. Here is the publisher link: Insight Book, Korea.