From Reading the Problem to Accepted, in C++ and Python — A student submits her first solution to an online judge at midnight and is told, in red, that it is wrong. The program printed the right answers on her laptop.

Overview

Chapter 1 explains what competitive programming is, what SPOJ offers and what the judge actually does with a submitted program. It installs the workbench, solves the first SPOJ problem, TEST, and builds a small judge of your own that compiles, runs and compares programs the way SPOJ does.

Chapters 2 to 4 are about the problem before the algorithm. Chapter 2 teaches you to read a statement like a judge does: its anatomy, a reading checklist, the three shapes of judge input, and the phrases that decide everything, in ADDREV, FCTRL2 and ONP. Chapter 3 turns a time limit into a budget of steps, counts the steps of an algorithm, and shows how the constraints point to the method, with FCTRL, LASTDIG and the segmented sieve of PRIME1. Chapter 4 measures every way of reading and writing data in both languages and draws the rules for enormous input and output, in INTEST and INOUTEST.

Chapters 5 to 8 are about everything that stands between a right idea and an accepted program. Chapter 5 explains what the judge does with your source: compiler flags that find bugs, flags and pragmas that make code faster, a risk ladder for pragmas, and a portability checklist. Chapter 6 spends the second budget, memory: what one element really costs, a range too large to store in PRIME1, a table that does not fit in LKS, and a stack that is smaller than you think. Chapter 7 catalogues the classic implementation gotchas that cause Wrong answer — overflow, numbers beyond every built-in type, zeros that must disappear, state that leaks between test cases, division and floating point, and off-by-one errors. Chapter 8 builds the harness that the rest of the book relies on: a generator, a brute force and a stress test that hunt down wrong answers and hidden slow steps, in INVCNT and PALIN.

Chapters 9 to 11 are the algorithmic core. Chapter 9 teaches dynamic programming through six patterns — a line of choices, counting ways, paths in a grid, a knapsack, two strings and intervals — in FARIDA, ACODE, BYTESM2, KNAPSACK, EDIST and MIXTURES. Chapter 10 shows when a greedy choice is safe and how an exchange argument proves it, in BUSYMAN, FASHION, BAISED and GERGOVIA. Chapter 11 searches for the answer instead of computing it, with binary search on the answer and two pointers, in AGGRCOW, EKO, PIE, BOOKS1 and HOTELS.

Chapters 12 and 13 are toolkits. Chapter 12 assembles the graph algorithms a contest needs most: union-find, breadth-first search, bipartite checking, the longest path in a tree, Dijkstra’s shortest paths, topological sorting and Kruskal’s minimum spanning tree. Chapter 13 does the same for number theory, geometry and strings: fast exponentiation, Euler’s totient, the Miller–Rabin primality test, orientation, the convex hull and polygon area, the closest pair of points, Knuth–Morris–Pratt, the period of a string and the suffix array.

Chapter 14 puts the whole craft together. It turns the chapters into one workflow and follows it end to end on three case studies, PPATH, ABCPATH and ONEZERO, shows what to do when the verdict is not Accepted, and suggests where to go next.

Every chapter follows the same path: a story and the problem it poses, the idea in plain words with a small example worked by hand, real SPOJ problems retold in our own words, the idea argued correct and its cost counted, reference programs in C++17 and Python, running them, testing them against a brute force, making them better, using them for real, common mistakes, a summary, exercises with complete solutions, and references.

Every program in this book was run before its output was printed. The programs are collected, chapter by chapter, in the accompanying code folder, from Chapter01 to Chapter14, each with a cpp folder, a python folder, a tests folder holding the generators, brute forces and stress scripts, and a README that explains how to build and run them in a terminal and in VS Code on Windows, macOS and Linux.

Inside the Book

1. Welcome to Competitive Programming and SPOJ
2. Reading the Problem Like a Judge Does
3. Picking the Right Algorithm for the Constraints
4. Fast Input and Output
5. Compiler Flags, Pragmas and Portability
6. Memory and Data-Structure Choices Under a Byte Budget
7. Classic Implementation Gotchas That Cause Wrong Answer
8. Debugging TLE and WA: Stress Testing and Brute-Force Checkers
9. Dynamic Programming Patterns
10. Greedy Algorithms and Exchange Arguments
11. Binary Search on the Answer and Two Pointers
12. Graph Algorithms Toolkit
13. Number Theory, Geometry and Strings Toolkit
14. Getting to Accepted: End-to-End Case Studies and Where to Go Next