Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 63 ยท Practice and Review

CSES Introductory Problems Walkthrough

Work through the classic CSES introductory problem set with original explanations and tested Python solutions: math tricks, constructions, backtracking and digit queries.

The CSES Problem Set is a free collection of about 400 well-known contest problems, grouped by topic and used by many programmers as a training ladder. Its first section, Introductory Problems, has around 20 short problems. They look easy, but they quietly teach the habits that every later problem needs: find the formula, build the answer instead of searching for it, and know when brute force is enough.

This lesson walks through most of that section. The statements below are my own short paraphrases (read the originals on the CSES site, and submit your solutions there), and every solution is original code that has been run against a brute force. Try each problem for ten minutes before reading the idea.

flowchart TD
    A["Read constraints"] --> B{"n up to 10^6 or more?"}
    B -- "yes" --> C["Need a formula or an O(n) pass"]
    B -- "no, n is about 8 to 20" --> D["Brute force over permutations or subsets is allowed"]
    C --> E["Find the invariant or build the answer directly"]
    D --> F["Backtrack, and prune obviously dead branches"]

In introductory problems the constraints almost always tell you which of the two worlds you are in.

Group 1: formulas, greedy passes and constructions

Missing Number. You get n - 1 distinct numbers from 1..n; find the absent one. The sum n(n+1)/2 minus the sum you were given is the answer. In Python, big sums are never a problem. With XOR, xor(1..n) ^ xor(given) also works and is a good place to remember the XOR identities.

Increasing Array. You may add 1 to any element; what is the fewest operations to make the array non-decreasing? Sweep left to right keeping the largest value seen so far. If the current element is below it, raise it up to that value and pay the difference. Raising an element never hurts the elements to its right, and lifting anything higher than needed only costs more, so this greedy is optimal. (See Greedy Algorithms and How to Trust Them.)

Trailing Zeros. How many zeros end n! for n up to 10^9? Zeros come from factors of 10, and factors of 2 are plentiful, so count factors of 5: n/5 + n/25 + n/125 + ... using integer division.

Coin Piles. Two piles a and b. One move takes 2 coins from one pile and 1 from the other. Can both be emptied? Each move removes 3 coins in total, so a + b must be divisible by 3. And neither pile can be more than twice the other (a pile with more than double the other can never be reduced by those 2-and-1 moves). Those two conditions are also sufficient, which the brute force below confirms for all small pairs.

Permutations. Output a permutation of 1..n where no two neighbors differ by exactly 1, or say it is impossible. For n = 2 and n = 3 it is impossible; for n = 1 the single number works. For n >= 4, write all evens, then all odds: neighbors inside a group differ by 2, and the single join between the groups is a large even next to a small odd (4 next to 1 for n = 4, differing by 3).

Two Sets. Split 1..n into two sets with equal sums. The total n(n+1)/2 must be even. Then greedily take numbers from the largest down into the first set while they still fit in the remaining target; the leftover target is always reachable because the remaining numbers 1..k can make every sum from 0 to k(k+1)/2.

Python Introductory problems 1: formulas and constructions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The checks use real brute forces: all increments for the Increasing Array problem, a flood-fill of reachable pile sizes for Coin Piles, and all permutations for the neighbor problem. Whenever you find a clean formula, a small brute force like this costs a few minutes and removes all doubt.

Palindrome Reorder. Rearrange the letters of a string into a palindrome, if possible. Count each letter. At most one letter may have an odd count (it goes in the middle). Otherwise write half of every letter, the odd letter, then the half reversed.

Digit Queries. Consider the infinite string 123456789101112.... What is its k-th digit, for k up to 10^18? Group numbers by length: 9 one-digit numbers use 9 digits, 90 two-digit numbers use 180 digits, 900 three-digit numbers use 2700, and so on. Subtract whole groups from k until it falls inside one, then compute which number it is (start + (k - 1) // length) and which digit of it ((k - 1) % length). This is O(log k), and it is the standard shape of "skip over blocks of known size".

Creating Strings. List every distinct permutation of a string of up to 8 letters, in alphabetical order. Backtracking over a letter-frequency table, always trying letters in sorted order, produces distinct strings already sorted, with no sorting or set needed. The count is the multinomial n! / (c1! c2! ...).

Apple Division. Split up to 20 apples with given weights into two groups with the smallest possible difference in total weight. With n at most 20, try all 2^n subsets; for each, the difference is |total - 2 * chosen|. (In Python 2^20 subsets with an inner loop is slow; use the incremental forms from Bitmask and Digit DP, or recursion that adds or skips each apple.)

Chessboard and Queens. An 8 by 8 board has some blocked squares. Count the ways to place 8 non-attacking queens on free squares. Place one queen per row, and keep three sets: used columns, used r - c diagonals and used r + c diagonals. Any attempt that clashes is skipped immediately, so the search tree is tiny (an empty board has 92 solutions).

Python Introductory problems 2: strings, digits, subsets, queens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The rest of the set

A few more problems in the section have been covered elsewhere in this course, so here are only the pointers:

  • Weird Algorithm follows the Collatz rule, and Repetitions is the longest run of equal letters: both are single passes, see Implementation Problems.
  • Bit Strings asks for 2^n modulo 10^9 + 7: one call to pow(2, n, MOD), see Modular Arithmetic.
  • Gray Code lists n-bit numbers so neighbors differ by one bit; the formula i ^ (i >> 1) is in Classic puzzles.
  • Tower of Hanoi prints the optimal moves, which is the recursion move(n-1); move disk; move(n-1); the same section covers its structure.
  • Grid Paths counts the paths of length 48 on a 7 by 7 grid that match a pattern with ? wildcards. The brute-force walk has too many branches, so the solution prunes. If the path enters a cell where it is forced to split the unvisited area into two parts, or if it hits a wall with both side cells free, it can no longer visit all cells and should stop. This is a lesson in pruning, and it is a Python-hostile problem: a careful solution is fast in C++ but needs optimization in Python, so use it to practice C++ or accept slower runs.

What these problems teach

Habit Where you saw it
Derive a formula, then test it on small values with brute force Coin Piles, Trailing Zeros, Missing Number
Build the answer directly when "exists or not" has a structure Permutations, Two Sets, Palindrome Reorder
Skip blocks of known size Digit Queries
Backtrack with constraint sets for tiny n Creating Strings, Chessboard and Queens
Enumerate subsets when n <= 20 Apple Division

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Trailing Zeros, why do you count factors of 5 only?

    Zeros come from pairs (2, 5). In n! there are always at least as many 2s as 5s, so the number of 5s limits the zeros.
  2. 2. Which pair of conditions decides Coin Piles (take 2 from one pile and 1 from the other)?

    Every move removes 3 coins, and a move reduces a pile by at most twice as much as the other, which gives the 2:1 bound.
  3. 3. How does Digit Queries reach the k-th digit of 123456789101112... for k up to 10^18?

    Numbers of equal length form blocks of size length * 9 * 10^(length-1). Skipping blocks takes O(log k) steps.
  4. 4. When is full brute force over subsets or permutations appropriate in these problems?

    2^20 subsets or 8! permutations are small enough. For n around 10^5 or more you must find a formula or an O(n log n) pass.

Summary

  • Introductory problems are won by reading the constraints: small n allows brute force, large n demands a formula or a linear pass.
  • Greedy passes (Increasing Array), counting arguments (Trailing Zeros, Coin Piles) and direct constructions (Permutations, Two Sets, Palindrome Reorder) all need a short proof or a tiny brute-force confirmation.
  • Digit Queries skips blocks of known size; Creating Strings and Chessboard and Queens use backtracking with frequency or constraint sets.
  • Apple Division enumerates all subsets, feasible for n <= 20.
  • Always cross-check a clever solution against a slow and obviously correct one on small inputs.

Next: CSES Sorting and Searching Walkthrough