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 »

Lessons from uHunt Chapter One

uHuntChapter1

This post is part of a series that considers what can be learned from the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt post category.

This week, I submitted the solution to the last of the 39 starred problems in uHunt Chapter 1. This is part of a learning project that I’m calling Project 462, after the 462 uHunt starred problems.

The problems in uHunt Chapter 1 are introductory and ad-hoc problems. They help uHunt users get familiar with the UVa Online Judge system, and they don’t require any specific competitive programming techniques to solve. Nevertheless, there were quite a few challenging problems in this chapter.

How to Attack a Programming Puzzle contains six tips for using UVa OJ. This post contains my remaining thoughts on solving the types of problems found in Chapter 1.

« Continue »

Productivity Habits

Elephant

When you’re working on a serious learning project, especially if you’re applying deliberate practice techniques, it’s essential to have a set of core habits that you can rely on. Deliberate practice is intended to be a demanding process (see elements #4 and #5 from the linked post). This is good because it makes you push against your limits, but it can also make it difficult to maintain a schedule if you’re just using an ad-hoc process. Experimenting with habits and selecting a few that work for you makes it more likely that you’ll be able to continue working on your project for as long as it takes to complete it.

A productivity habit is something you do on a regular basis (often daily) to help you be more productive. Although the habit may have some value on its own, what’s more important is the effect it has on your work. For example, I find it useful to keep track of how long it takes to complete various tasks. Analyzing this data over time can uncover some interesting trends. But it’s even more powerful to use time tracking for setting time goals, like the number of hours per day that I commit to spending on a project.

Here are the habits that I have found to be the most useful as I work on Project 462.

« Continue »

What Are the Important Problems of Your Field?

Science Fish

Do these questions sound familiar?

  • What are the important problems of your field?

  • What important problems are you working on?

  • If what you are doing is not important, and if you don’t think it is going to lead to something important, why are you … working on it?

They come from a 1986 speech by mathematician and Turing award winner Richard Hamming. Hamming originally asked them in the dining hall at Bell Labs, but they have since inspired other people who are interested in finding the best way to spend their work hours.

« Continue »

Building Mathematical Thinking Skills

Pumpkin Pi

When people hear the term competitive programming, they naturally think about programming contests and rankings. People who are encountering the term for the first time are just using the literal meaning, while those who are familiar with the topic think about the top competitors that they hear a lot about. But someone who is just starting to learn to solve the types of problems found in programming competitions may see things differently. In my experience, introductory problems often challenge mathematical thinking skills more than programming skills. Only a small subset of a programming language is required to solve these problems, and there’s plenty of time to look up syntax (since beginners are often not taking part in a timed competition). However, most problems (other than the very easiest ones) are structured to require mathematical thinking.

« Continue »