Thinking Competitively

Here’s an exchange that took place last month on Reddit (r/learnprogramming):

Question: Where and how to learn ONLY for competitive programming?

Answer 1: Competitive programming without learning regular programming….good luck with that.

Answer 2: You need to to crawl first before you can even begin to think competitively.

Answer 3: Learn to program first before even thinking about competing.

We can debate the wisdom of the original question, which asks about learning to program just to get good at competitive programming. Nevertheless, the answers reflect a misguided (though common) assumption about competitive programming: that it’s only for programming experts with huge brains frantically typing for 5 hours. Instead, what if we approached competitive programming as a way for beginners to learn to program from scratch? That’s the premise of Daniel Zingaro’s new book, Learn to Code by Solving Problems: A Python Programming Primer.

Programming in Python

Dr. Zingaro’s previous book, Algorithmic Thinking: A Problem-Based Introduction, took a similar approach: He used problems from programming competitions to teach algorithms. But while that book used the C programming language and jumped right in to hash tables in Chapter 1, the new book assumes no previous programming experience, explains solutions in Python, and spends the first four chapters on basic topics like loops and conditionals. Dictionaries (the Python implementation of hash tables) show up late in the book, in Chapter 8.

If you already have some programming experience, you might wonder what this book offers you. While giving it as a gift to the prospective programmer in your life is always an option, you might also find it useful as an introduction to Python, if you mainly program in another language. I don’t use Python much, so I found the chapters on lists, sets, and dictionaries to be useful reminders on how those data structures work in Python (compared to C# and TypeScript, my primary languages). And while the main language that people associate with competitive programming is C++, Python is friendlier for people who are using contest problems to get better at problem-solving or coding fluency. Python is also convenient when you’re writing interview code on a whiteboard. Its readable style makes it easier to explain what you’re doing to the interviewer, and the code tends to be shorter than the equivalent C++ or Java.

The Online Judge Verdict

If you’re on board with the benefits of Python, there are already plenty of books you could use to learn it, some for beginners and others for more experienced programmers. The key feature of this book is the focus on public online judge problems. While programming book authors like to use original problems or sample applications to explain language features, that’s not always the best approach for learning a programming language. Sample applications (e.g., building a simple e-commerce website) have the advantage of presenting a language in a realistic context. But this approach tempts the reader to simply follow along with a step-by-step process, which isn’t the best way to learn. As for standalone programming problems, they can be helpful for testing whether you really understand the contents of a book chapter. But writing high-quality programming problems is hard. And even if the author is kind enough to provide an answer key at the back of the book or on a companion website, that still only gives you one person’s implementation of the solution.

So problems are a good feature of a programming book, but they can be hard for the author to get right. In contrast, using contest problems in a programming book has several advantages. The authors of contest problems know what makes a good problem, since they see their problems being tested by a discerning group: competitive programmers. If the problem had bugs when the problem setter wrote it, someone probably already found them before the problem made it into a major contest. Or even if a bug made it into the contest, a book author can just skip that contest and use another one.

One common complaint about contest problems is that the problem statement can be hard to understand. Dr. Zingaro avoids that concern by rewriting the problem descriptions in a consistent style, so they fit naturally in the chapter. While contest problem setters may like to confuse contestants with long stories and convoluted descriptions, there’s no reason a programming book has to do the same thing.

How to Use Contest Problems

If you’re reading a book that has contest problems as examples, you can use them in several ways that aren’t available for problems written specifically for a book. Contest problems, if chosen correctly, are found on online judges. So you can try solving them yourself before reading the book section. This can help you pinpoint the areas you’re having trouble with, which you can then focus on when reading the section. Once you read the author’s ideas, you can adjust your implementation and re-submit as many times as you want. This is a good way to experiment with language features and learn how an algorithm works. As Dr. Zingaro writes, “If you make changes and the code no longer passes the tests, great! Now you have a new learning opportunity to fix the code and learn why your changes led to undesired behavior.” Finally, publicly available problems often have publicly available solutions, whether on the online judge’s website, or on blogs and in GitHub repos. Once you’re familiar with a problem, you can review other people’s solutions to see what they did differently. You might find the most useful ideas not in the book you’re reading, or in the official editorial, but from a creative programmer in the discussion forums.

Like the well-known competitive programming book called Competitive Programming, Learn to Code by Solving Problems has contest problems both in the main text of each chapter and at the end of the chapter. While you won’t find the same detailed explanations for the end-of-chapter problems as you get for the problems in the main text, it’s still useful to have a curated list of quality problems that illustrate a particular programming concept. And since these problems are also available on online judges, they have the same benefits: automated judging, repeated submissions, and crowdsourced solutions.

Programming Tips

Although Learn to Code by Solving Problems is for beginners, and targets at a wide range of programmers (not just computer science students), it doesn’t avoid discussions of programming fundamentals or algorithm basics. The later chapters cover hash tables, binary search, and big O analysis. And the earlier chapters are careful to explain programming best practices and details of the Python language to help you write idiomatic and reliable code. We learn that Python string comparison is case-sensitive by default, that programmers should “Whenever possible, write code that doesn’t require comments,” that Python supports negative indexes, that the break statement only terminates “its own loop, not any outer loops,” that Python strings are immutable while Python lists are immutable, and how passing by value differs from passing by reference. Dr. Zingaro even takes a position on the great tabs vs. spaces debate (the verdict: spaces, though maybe that’s just because it’s in the Python style guide).

Practice, practice, practice

For someone just learning to program, or learning Python after spending some time with another language, Learn to Code by Solving Problems covers what a programmer needs to know to get started with the language, plus language-independent skills like breaking a solution into parts using functions. But programming can be tricky at any skill level. People learning to program or learning a new programming language in this era have the advantage of an abundance of online judge problems for practice. Programming educators and students would do well to embrace that mode of learning.

As any student pursuing a technical degree knows, problem sets are a big part of math, physics, and engineering classes. Computer science works a bit differently. While CS theory classes use problem sets similar to those in math and science, other classes often require CS students to turn in code that compiles and runs. Some of these programs are for major projects related to networking, operating systems, or graphics, while others are solutions to short algorithm problems.

Because of the way coding interviews work, programmers must be able to solve short algorithm problems even after they graduate and enter the workforce. As a result, coding assignments in these areas have escaped the campus and are available to the public on websites like Codeforces and LeetCode. Anyone who wants to learn these topics can submit their programs to an online judge, which runs them against dozens of test cases that verify correctness, performance, and resource usage.

Despite the popularity of interview prep sites, not all algorithms textbooks have bought into the online judge approach. Introduction to Algorithms (CLRS to those in the know) famously uses pseudocode in its examples. Good luck compiling and running those. Robert Sedgewick’s algorithms books offer actual code in multiple programming languages. But the exercises at the end of each chapter are traditional textbook problems, graded manually by the student (if they can find an answer key) or by an instructor. Even Cracking the Coding Interview, the popular prep book by Gayle Laakmann McDowell, is mostly paper-based. The book includes solutions, which you can compare with your own code. But the only way to find out for sure that your solution works is to come up with test data and run your program against it. (A few years ago, CtCI had an arrangement with HackerRank to host questions in an online judge format, but apparently it wasn’t a permanent deal).

Paper and pencil are good for sketching binary trees, working out the details of an asymptotic analysis, or planning a solution approach. But if you want to verify that you can implement an algorithm correctly and efficiently, the gold standard is running it against a suite of test cases that an expert has carefully chosen. That’s the philosophy behind Algorithmic Thinking: A Problem-Based Introduction, a new book by Daniel Zingaro, Associate Professor of Mathematical and Computational Sciences at the University of Toronto Mississauga.

Algorithms for Competitive Programming

Algorithmic Thinking is not a competitive programming manual. In the introduction, Dr. Zingaro writes, “My goal is not to turn you into a competitive programmer, though I’d take that as a happy side benefit.” But all the problems in the book come from online judges and programming competitions, which means they are self-grading.

The book also isn’t an encyclopedia of algorithms, like CLRS or Sedgewick. It doesn’t cover every algorithm you might need in a class or contest. Instead, it explores a selection of classic algorithms, data structures, and techniques to find out what they can teach about solving problems with computers.

Try the Problem First

Here’s a question from Quora:

• Should I learn all DS and Algos first to start competitive programming? Or I can just start practicing from CodeChef, learn the DS and Algos with it?

Or to put it another way:

• What basic data structures and algorithms should one learn before starting competitive programming?

These are popular questions, maybe because of how technical classes traditionally work: First you attend a lecture to learn some ideas, and then you work on a problem set that uses what you learned in the lecture. Repeat with the next lecture and the next problem set.

Algorithmic Thinking takes the opposite approach: The first thing you encounter in each chapter is a description of the first problem to be solved in that chapter. Algorithms, data structures, and techniques appear only when they’re needed for the problem. For example, Chapter 3 (“If you’re going to read one chapter in this book, read this one”) introduces UVa 10465, the Homer Simpson problem, and uses it to explain memoization and dynamic programming.

Reading Editorials

The best way to read Algorithmic Thinking is to treat it like a problem set that comes packaged with the world’s most detailed answer key. Here’s the plan: Don’t spoil the surprise by reading the answer key first. Instead, before starting the introduction, skip straight to Appendix C, which lists the 25 problems covered in the book’s 359 pages. (That’s over 14 pages per problem. I wasn’t kidding when I said it was detailed). The problems are all available online, so search for the first one (Food Lines from DMOJ) and submit a solution, or spend a reasonable amount of time trying. Once you get everything you can out of the problem, start reading the introduction. If you weren’t able to solve the problem on your own, read just enough to get a hint, which might unblock you. If you did solve the problem on your own, you might still find ideas to make your solution more efficient or elegant.

In competitive programming jargon, an editorial explains how to solve a programming problem. It covers how to approach the problem, which algorithms and data structures to use, and how to write the code to solve it. So you could interpret the chapters in Algorithmic Thinking as editorials for 25 competitive programming problems. But there are a few ways in which this book is preferable to editorials one might find online:

• Problem selection: There are thousands of contest problems out there, but only 25 in this book. As Dr. Zingaro explains in Chapter 1, he didn’t select the problems arbitrarily. Each one had to use one of the algorithms or data structures selected for the book, and it had to be “algorithmically complex” enough to be challenging but also “sufficiently simple” to avoid confusing the reader with irrelevant details. That’s the value that an expert provides when selecting the right set of practice problems. And when those problems are collected in a book, they can be ordered so that subsequent problems build on lessons learned from earlier ones.

• Level of detail: As I mentioned earlier, the book devotes quite a few pages to each problem. There’s enough space to solve the problem in multiple ways, showing how different data structures affect runtime. The text explains each line of code, so that once you finish reading the explanation, you really know what the problem is about.

• Quality control: While you can find an editorial for many contest problems, there’s no guarantee that it will be understandable. In contrast, Algorithmic Thinking offers clear writing and professional editing. Even the problem descriptions have been rewritten to eliminate the notoriously obfuscated prose that competitive programming problems use, so the reader can focus on learning the algorithms.

Topics

Dr. Zingaro chose the 25 problems in Algorithmic Thinking to support the set of algorithms, data structures, and techniques that he thought would best serve the goals of a problem-based introduction to algorithmic thinking. Here are the principal topics in each chapter:

• 0: Arrays; introduction to the online judge problem format

• 1: Hash tables

• 2: Trees and recursion

• 3: Memoization and dynamic programming

• 4: Graphs and breadth-first search

• 5: Shortest paths in weighted graphs

• 6: Binary search

• 7: Heaps and segment trees

• 8: Union-find

Other algorithms, data structures, and techniques also appear when needed. For example, a stack (implemented from scratch) shows up in Chapter 2, and greedy algorithms are used in Chapters 3, 5 (Dijkstra’s algorithm), and 6. But the goal is not comprehensive coverage. There are a lot of algorithm books out there. As explained in the introduction, each topic made it into the book because it was broadly applicable, could be implemented in at most 150 lines of C code, and because a concise argument could be made about correctness without getting into a formal proof. That’s the niche occupied by this book.

The C Programming Language

150 lines of what kind of code? Yes, the only programming language you’ll find in Algorithmic Thinking is the C programming language. Not C++, just C. It’s been a while since I have done any C programming, but according to one measurement, it’s the #1 most popular language as of September 2020, so there you go. (Stack Overflow puts it at number 11. It all depends how you measure).

The choice of C is intentional. Dr. Zingaro says in the Introduction that he wants “to teach you data structures and algorithms from the ground up. When we want a hash table, we’ll build it ourselves.” I understand this decision. Algorithms are a fundamental topic in programming. They’re at a lower level than topics like databases or networking. So building your own data structures and handling your own memory management isn’t out of place in a discussion of algorithms. (And it’s not like we’re being asked to go full Knuth and write all the algorithms in assembly language for a theoretical CPU). The book isn’t even excessively dogmatic about building every tool: A few solutions use the built-in C qsort function rather than implementing a custom sort algorithm from scratch.

In my work, I spend most of my time with languages at a Java level of abstraction. When I’m solving competitive programming problems, I like to have a wide range of built-in collection classes and other facilities available. But I didn’t have any problem following the C code in the book or the explanations. For example, it was interesting to review how hash functions work (Chapter 1) even though I usually rely on library functions to implement them.

Food for Thought

• “While there may be millions of problems out there, there are far fewer algorithms. The best algorithms are often the ones that rest on ideas so flexible that they can ooze beyond their intended purpose” (Chapter 5). Programming contests are all about starting with a limited set of standard algorithms and inventing wacky scenarios to see if contestants can tweak the algorithms they’re familiar with to solve each problem in the allotted time.

• “Hold on! Why are we letting these officious test cases bully us into producing these awful trees?” (Chapter 8). It’s true. If you aren’t careful, test data can mean the difference between Accepted and TLE in a contest.

• “Binary search turns a ‘solve this’ problem into a ‘check this’ problem” (Afterword). I’ll bet you didn’t know that about binary search.

Should You Read It?

If you need to solve coding interview questions on demand (and who doesn’t), you might have to practice with a few hundred problems. If you’re serious about competitive programming, the target is more like a few thousand. Either way, adding the 25 problems from Algorithmic Thinking into the mix should fit into any practice schedule. In return, you get a handpicked set of problems covering fundamental topics. Each solution is explained in considerable detail and has a model implementation that you can translate into your favorite programming language. And if you spend time with a problem before reading about it in the book, the explanation is easy to follow. It’s a good choice for anyone who needs to understand and implement algorithms.

People often use the term competitive programming to refer to any activity (besides homework) where programmers create solutions to made-up puzzles rather than real-world problems. For example, consider this Quora question: Which is the best online judge for competitive programming, HackerRank, HackerEarth or LeetCode? As Bohdan Pryshchenko points out in his answer, these three sites focus on interview practice, not competitive programming in the traditional sense. Their questions cover topics likely to come up in an interview. And although some of them host contests, those contests don’t consistently attract the strong contestants who regularly show up for Codeforces and Topcoder events.

When I’m writing Quora answers, I sometimes point out the difference between competitive programming and interview preparation if it’s relevant to the question. But while I’m always in favor of using terms correctly, I’m not sure how important this distinction is in the scheme of things. Consider that:

• Coding interview questions require knowledge of topics like graphs, trees, and dynamic programming algorithms, all of which are used in competitive programming.

• Participation in competitive programming tapers off quickly as the problems require more advanced algorithms. For example, see the bottom graph in this Quora answer. Red coders on Topcoder are a long tail at the high end of the rating distribution, while the bulk of the contestants are clustered in the large gray-green-blue area. At these levels, competitive programming questions use well-known algorithms, just like interview questions do.

• Competitive programming owes most of its popularity to its association with coding interviews. If it was just about coders solving puzzles, it would be a niche activity even within the software engineering world.

« Continue »

With discussions in progress about creating a competitive programming site on Stack Exchange, I have been thinking about what we get out of technical Q&A sites.

« Continue »

This week, another attempt is underway to create a competitive programming site on the Stack Exchange network.

It’s been tried before. In early 2013, a similar proposal was put forward. But a year later, the proposal still hadn’t met the minimum activity requirements defined by Area 51, the part of Stack Exchange where new sites are proposed and discussed. In keeping with Area 51 policy against keeping old proposals around, the 2013 proposal was deleted. It lives on as a snapshot at the Internet Archive, and as a Codeforces blog post.

Will things turn out differently this time around? It’s not clear that popular demand for a Competitive Programming Stack Exchange (CP.SE) site has increased in the last few years. And if a new site is going to make it past the Definition phase on Area 51, there will need to be demand. Stack Exchange rules require that a potential new community demonstrate that it can sustain question and answer activity. That’s to prevent underused sites from hanging around the network but not providing any value.

So we’ll see what happens as people start following the CP.SE proposal. In the meantime, it’s worth considering what other sites are out there to fulfill the need for competitive programming Q&A, and whether we need another option. That’s the topic for today.

« Continue »

Last month, ITMO University launched an edX course called How to Win Coding Competitions: Secrets of Champions. With this first iteration of the course coming to an end, I thought I would discuss my experience with it.

« Continue »

Programmers get better at competitive programming mainly by solving competitive programming problems. It’s true that there are other activities that go along with problem-solving practice. Reading about algorithms, data structures, and problem-solving techniques is useful to avoid re-inventing the wheel. And it’s even more important to read solutions after you solve a problem, so you can learn from other practitioners and fix your mistakes. But the core of the learning process is solving problems. Without that core, reading textbooks and solutions won’t get you very far.

« Continue »

In January of this year, Jasmine Chen (lnishan) published a Codeforces blog post called An awesome list for competitive programming! Since then, she and a few collaborators have been editing and expanding the list on GitHub.

Awesome list in this context doesn’t just mean “a really great list.” It refers to a project started by Sindre Sorhus in which people create lists of links to useful and/or interesting resources, and publish them on GitHub. There is of course a list of these lists.

Here’s what the Awesome Competitive Programming list offers.

« Continue »

To get better at programming or math, it’s not enough to read about a topic. You have to solve problems. And solving problems is a lot more beneficial if you have access to solutions, especially ones with detailed explanations. But as useful as solutions are, they also present another problem: when is the best time to look at them?

Solving a problem yourself improves your understanding of a concept more than reading someone else’s solution. If that wasn’t true, then it would be possible to learn a technical subject just by reading about it. That would be easier, but it doesn’t work. So you need to struggle with problems.

However, you can’t avoid looking at the solution forever. Problems in textbooks or online judges are intended to be solved in hours or days. They aren’t unsolved research problems that take months or years to solve. (Or if they are, they’re clearly marked as such — e.g., some of the problems in Knuth’s books).

So part of your job as a problem-solver is to settle on the best time to look at each solution.

« Continue »