Problem Categories
Programming Contest problems come in many shapes and sizes. One step that can help
in successfully solving a problem is to determine the nature of that problem. One
of the easiest ways for people to do this is to make up a list of categories and
then decide which category(s) the problem fits into. So here is a first cut in making
a list of categories.
| Category | Subcategory | Distinguishing Features |
| Geometry | ||
| Packing Problems | Fitting some shaped item into another shaped item | |
| 2-D | Can 2-D object X fit in/pass through 2-D object Y | |
| 3-D Perspective | What is visible, are two items the same | |
| Rotation/Transformation | What happens when a series of rotations/transformations are applied to an object | |
| Lines | Intersection of lines | |
| Curves | Circles, Ellipses, Cones, ... | |
| Triangles | Circumference, area, Right, Isosceles, Equilateral, Scalene, Non-Euclidean | |
| Quadrilaterals | Square, rectangle, parallelogram, rhombus, trapezoid | |
| Polygons | Working with many sided figures | |
| Math | ||
| Combinations/Permutations | Solve some puzzle that requires calculation/production of acombination/permutation of items | |
| Simultaneous Equations | Solve a situation with N unknowns (inequalities also) | |
| Algebraic | Problems that require use of algebra to solve | |
| Number Theory | Problems tht require knowledge of number theory to solve | |
| Trig Relations | Problems tht require trig relationships to solve | |
| Numerical Relationship | Primes, Pascal's triangle, Fibanacci Series, Factorial | |
| Trig Relations | Problems that require trig relationships to solve | |
| String | ||
| String Containment | Is some string(s) contained in another string(s)/matrix | |
| String Manipulation | Heavy string coding: reversing strings, substringing, ... | |
| Parsing | Problems that rely on parsing input data | |
| Algorithmic | ||
| Sorting/Searching | Problems that need data sorted or searched | |
| Data Structures | Problems that require understanding of specific data structures tos solve | |
| Backtracking | Problems that require you to be able to backtrack to solve | |
| Network | Minimum/maximum distance... | |
| Graph Problems | Problems that require you to be able to traverse and translate graphs to solve | |
| Grids | XY grids | |
| Flood Fill | Filling a bounded region | |
| Recursive | Recursion -- cool | |
| Greedy Algorithms | Solve problem by taking best option at each possible step | |
| Other | ||
| Brute Force | Just code away | |
| Inventory | Classic start with a list, add/remove/modify list, display list of state whether operations are possible | |
| Dynamic Programming | Can you think sideways... |
Examples of problems that fit into categories:
| Category | Problems |
| Prime Related | |
| Divisibility Related | |
| Flood Fill |
|
| Computational Geometry | |
| Computational Geometry |
|