Lessons from Competitive Programming 3, Chapter Two

CP3Chapter2

This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.

Competitive Programming 3 (CP3) Chapter 2 covers a selection of data structures that are useful for solving competitive programming problems. These data structures are used in the Chapter 2 uHunt problems, and in subsequent chapters in the book. In some cases, Chapter 2 just provides a brief introduction to topics that are covered extensively elsewhere. For example, Section 2.4.1 covers some basic information about representing a graph, while Chapter 4 contains the book’s full treatment of graph algorithms. And Section 2.2 devotes a paragraph each to common data structures like arrays, stacks and queues, which readers are expected to know about already. In other cases, Chapter 2 goes into more depth. For example, it’s harder to find information about the Segment Tree data structure in other sources, so it is covered in more detail in this chapter.

As in the rest of the book, each section in this chapter ends with a list of recommended UVa Online Judge problems. The same list can be found on uHunt, where you can also track your progress.

In addition to UVa OJ problems, each section also has written problems. For example, a question in the section on stacks and arrays asks the reader how to implement a stack using an array. Answers are supplied for some of these problems at the end of the chapter. I have just been skimming these written problems. The appeal for me of the CP3/uHunt approach is that problems are “graded” automatically by a computer. Solving problems and then looking up answers at the end of the chapter is the traditional textbook self-study approach. While that can be useful, especially you have a peer or instructor to review your written answers, my goal in using this book is learning through coding. I found plenty of opportunities to learn about the Chapter 2 data structures while I was solving the corresponding uHunt problems.

« Continue »

Lessons from Competitive Programming 3, Chapter One

CP3Chapter1

This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.

Many of the problems in the UVa Online Judge are taken directly from past ACM-ICPC contest problems. If you’re preparing for this contest or the IOI (which targets a subset of ICPC content), it makes sense to be familiar with these problems. But even if you’re planning to compete on platforms like TopCoder and CodeForces, it can be useful to train using UVa OJ problems, despite the platform’s quirks. Competitive programming problems tend to cover similar topics regardless of the contest platform, especially when it comes to easy and medium problems. The difference is mainly about which topics are emphasized more.

Because UVa OJ has been around for a while, several books use its problems as exercises. One of these is Competitive Programming 3 (CP3), the companion book to the uHunt site. Last week I wrote about the Chapter 1 uHunt starred problems. This week I’m going to cover some highlights from the corresponding chapter in the CP3 book. I’m using the 3rd edition, but you can find similar (but older) content in the free 1st edition ebook.

« Continue »