## 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