Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

When to Peek at the Solution

By Duncan Smith May 4 1

GardenChess

When I’m solving competitive programming problems for practice, I follow a specific series of steps to help me get the most out of the process. My current process ends with submitting an accepted solution and recording my stop time (for measurement purposes). But there really should be another step: find someone else’s solution and compare it with mine.

Arduous Chess Study

Serious chess players spend time doing what Cal Newport describes as “the arduous task of reviewing past games of better players, trying to predict each move in advance.” Here’s how it works: Given a chess position in a game between experts, come up with what you think is the optimal move. Compare your move with the expert’s move. If they differ, think about the pros and cons of each one. What made the expert choose their move? Is there a flaw in your reasoning that led you to choose your move? Repeat this process until the end of the game.

Let’s think about how to adapt this process for competitive programming practice. When you make a submission to an online judge, you get two pieces of feedback: a verdict (Accepted, Time Limit Exceeded, etc.) and a runtime measurement (e.g., 0.531 seconds). If you don’t get an Accepted verdict, you can keep trying until you do. If your runtime is under the time limit but higher than other submissions in the same language, you can try to improve the efficiency of your implementation.

One way to get more specific feedback on your submission is to find someone else’s solution and compare it to yours. Fortunately, there are a lot of sample solutions available. Some online judges, like CodeForces, let you see everyone’s submissions once a contest is over. To take advantage of that feature, you could pick a contestant and follow their work across contests. Or you could just pick any top contestant and see what they have to offer. In my practice, I’m using the uHunt problems, which are well-known and often have editorials and solutions available on blogs and GitHub.

Like going over expert chess games, analyzing someone else’s programming puzzle solution is hard work. Most people just post their code with minimal explanation, so you have to figure out what the code does on your own. If you’re looking at a contest submission from a top contestant, the code will be optimized for coding speed and runtime efficiency, not readability. Extracting algorithms and design choices from code is good experience, but it takes time and effort. If you’re doing it after you already have your own accepted solution, it’s tempting just to move on to the next problem.

To Compare or Not To Compare

Why go to the trouble of figuring out someone else’s solution when you have already finished yours? Because getting an accepted solution doesn’t mean you have extracted everything you can out of a problem. Here are some things you might have missed:

  • Your solution might run under the time limit but still not be optimal. A future problem might use a similar algorithm with test data that requires a more efficient solution.
  • You might find a less verbose way to express the solution, which would save you coding time in the future.
  • Your algorithm might work for this problem but might not be general enough to work for all similar problems. Looking at another solution can be a more efficient way to get experience than doing a set of additional practice problems on the same topic.

This isn’t to say that you should use this process for all of your solutions. The time you spend comparing your solution is time you could be spending solving another problem on your own. So you have to consider what you’re getting out of the process for each problem. Solving a problem and analyzing someone else’s solution provide two different types of experience. Being able to quickly and accurately solve a problem from scratch is the fundamental skill you are working on. If you finish a problem and feel like you have a good command of the topic that it’s based on, it’s probably best just to move on to the next problem.

An Example: UVa 10567

Two weeks ago, I posted an editorial on UVa 10567, a string processing problem in uHunt Chapter 3. Has anyone else done the same? A Google search turns up a small number of solutions, including mine. I picked one by Sai Cheemalapati.

Sai’s editorial includes a brief explanation of the algorithm, and a short C++ solution. My solution is in Java, so I decided to translate Sai’s solution, to make it easier to compare, and to better understand it. Here’s what I found:

  • We both use lists of lists of integers (vectors of vectors of ints in C++) to store the positions of characters in the input string.

  • However, my version does a bit more pre-processing, storing “segments” of consecutive characters (start and end positions) rather than just start positions. This makes the code more verbose: the core algorithm in my version is about 60 lines of Java, vs. 30 lines of Java for his (translated) version.

  • His version (translated to Java) runs a bit faster on the online judge than mine does — 0.700 seconds vs. 0.920 seconds. However, his was slower when I ran it on a local test file that I generated, probably because my test data had longer runs of characters than the data used by UVa OJ.

Comparing Solutions

The usual reason for looking up a programming puzzle solution is that you’re having trouble figuring out how to solve it. There’s nothing wrong with peeking at answers, especially if you have already put a lot of effort into your own solution. But it can also be profitable to look up a solution to a problem you have already solved. For my UVa 10567 example, I found a solution with 50% less code than I used. My solutions tend to be verbose, so for me, it’s good to study examples of how to solve the same problem with less typing.

(Image credit: Everyman Films)

Categories: Competitive Programming

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode Tip 11: How To Use Spaced Repetition (Part 1) March 22, 2023
  • LeetCode Tip 10: Planning a Spaced Repetition Schedule March 15, 2023
  • Book Review – Algorithmic Thinking: A Problem-Based Introduction, Second Edition March 9, 2023
  • LeetCode Tip 9: Spaced Repetition March 8, 2023
  • LeetCode Tip 8: Anatomy of a Model Solution March 1, 2023
  • LeetCode Tip 7: How to Write a Model Solution February 22, 2023
  • LeetCode Tip 6: Model Solutions February 15, 2023
  • LeetCode Tip 5: Choosing a Model Problem February 8, 2023
  • LeetCode Tip 4: Model Problems February 1, 2023
  • LeetCode Tip 3: A Goal for LeetCode Practice January 25, 2023
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2023 Duncan Smith