## Arup's Problem Rating System

I designed a rating system for my competitive programming summer camp, and this is the system I have used to rate the following problems. The scale goes from 1-9. It can be broken down into 3 general groups:

1-3: These are easy problems. Generally speaking, no specific algorithmic knowledge is necessary to solve them. Awareness of how to use built in data structures or custom sorting may be necessary, but most of these problems describe some process and then you just have to implement what is described in a straight-forward manner.

4-6: These problems can be solved using classical techniques taught in a standard state school Data Structures or Algorithms class. This includes: graph algorithms (DFS, BFS, Top Sort, MST, Shortest Distance, 2 Coloring, etc.), dynamic programming, brute force, divide and conquer, etc.

7-9: These problems either (a) require techniques that aren't taught in UCF's standard undergraduate data structures or algorithms curriculum, (b) have very ugly implementation details or corner cases, or (c) have a very high level of problem obfuscation. Admittedly, most college regional contests almost entirely live in this category now, so only giving 3 different difficulty ratings doesn't do difficult problems justice. Also, since I largely include problems I have solved (there are some I haven't but I've done most of these), I don't have really hard problems on this list. So, my distinction between 7s, 8s and 9s might not be quite as good as my distinctions between 1-6. All of these are problems that I probably would not have solved in contest and if I did solve them, I did so over multiple sittings, maybe even getting help from the real judge data. I tend to put anything with Segment Trees, Binary Lifting, String Algorithms (hashing, suffix array, etc.) and most Geometry in this category. Many of these problems combine multiple techniques as well.

Now a full breakdown:
RatingDescription
1 Easiest problems. Just do what it says and there really aren't any corner cases or implementation snags for the average competitor.
2 Algorithmically easy, but maybe small implementation details (how to convert 'a' to 0, 'b' to 1, etc.) are not known to some beginning programmers.
3 Straight-forward, but maybe requires an observation, along with things like a sort or the use of a built in data struct like a set or map.
4 Tests something taught in Data Structures or Algorithms. Has a relatively straight-forward implementation. Has relatively little problem obfuscation. Something that looks like a great assignment for a regular data structures or algorithms course.
5 Tests something taught in Data Structures or Algorithms. Has some annoying implementation details or observations to be made that the average student might not be able to do without TA help.
6 Tests something taught in Data Structures or Algorithms. Requires non-trivial observations and/or really detail oriented code with corner cases. Might include bitmasks and other things that many students have difficulty applying seamlessly.
7 Uses at least some idea or data structure not taught in standard undergraduate courses, such as a binary index tree, segment tree, range minimum query, binary lifting, etc. Often times, these problems can be solved by regular undergraduates if an O(n^2) run time was allowed, but the advanced material is necessary to bring down the run time to O(nlgn). But, if you identify the efficient technique, the code is reasonably clean in most cases.
8 Like a 7 but with more problem obfuscation and more difficult to code.
9 Very few get these in contest and most of the time, they are learning tools for later!