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