home • for students • teaching • research & projects • publications • personal • misc • now

Kattis problem grading system

As an aid to students looking for appropriate problems to solve, I have developed a rough grading system giving an indication of the level of background knowledge needed to solve a problem. This is often independent of problem difficulty: some low-difficulty problems are “easy” only if you only know the right (advanced) algorithm; conversely, some high-difficulty problems have tricky corner cases but can be successfully attacked by someone with only basic programming knowledge.

Each grade consists of a letter and a number, like B/2. Pluses and minuses are sometimes used to denote particularly tricky or easy problems within a certain level of background knowledge. For example, B+/0 would denote a problem which technically only requires knowledge from a Data Structures course but which a typical Data Structures student might find tricky.

• The letter grade denotes the level of data structure or algorithm knowledge needed:

  • A: does not require any special knowledge beyond what is taught in an introductory programming course (CSCI 150 at Hendrix), such as:
    • conditionals
    • loops
    • lists
    • arrays
  • B: requires knowledge taught in a typical Data Structures course (CSCI 151), such as:
    • stacks
    • (priority) queues
    • heaps
    • maps/dictionaries
    • recursion
    • sorting
    • searching
    • trees
    • tries
  • C: requires knowledge typically taught in an Algorithms course (CSCI 382), such as:
    • greedy algorithms
    • divide & conquer
    • graph search (BFS, DFS, Dijkstra)
    • topsort
    • dynamic programming
    • max flow
    • union-find
  • D: requires additional or advanced knowledge of Algorithms topics, such as:
    • interval processing / interval cover
    • ternary search
    • other graph algorithms (SCCs, bridges, Eulerian paths)
    • custom variants of standard algorithms
    • particularly tricky DP variants
    • LIS/LCS
    • bit tricks
  • E: requires knowledge of other special topics, such as:
    • Huffman trees
    • string matching
    • Fenwick trees
    • set cover/DLX
    • 2-SAT
    • generating permutations
    • travelling salesman (TSP)
    • 2D prefix sums
    • suffix tries
    • parsing
    • weighted matching
    • NFAs/DFAs
    • heavy-light decomposition
    • sqrt decomposition
    • Lyndon factoriztion
    • least common ancestors (LCA)
    • graph coloring
    • linear programming (LP)
    • Gauss-Jordan
    • combinatorial game theory (CGT)

• The numeric grade denotes the level of math knowledge needed to solve a problem:

  • 0: no special math knowledge required beyond basic arithmetic.
  • 1: high school math, such as
    • solving linear and quadratic equations
    • trig
    • basic modular arithmetic
    • basic statistics (average, median)
    • basic combinatorics and probability
    • logarithms
    • basic geometry (distance formula, circle formulas)
    • date and time conversion
    • rational numbers
  • 2: calculus, probability/combinatorics, and discrete math, such as
    • optimization, integrals
    • additive & multiplicative counting, permutations, binomial coefficients
    • game theory
    • graph theory (Euler formula)
    • base conversion
    • basic 2D vectors
    • basic number theory (primality, factoring)
    • modular exponentiation
    • bit strings
    • boolean logic
  • 3: more advanced math knowledge, such as
    • computational geometry
    • advanced probability/combinatorics
    • permutations, cycles, inverse permutations
    • advanced number theory (sieving, totient, divisor sum, extended gcd, modular inverses, CRT, continued fractions)
    • hexagonal grids
    • linear algebra, matrix powers