What attributes does a good problem set have?
If you are evaluating the problem set after its use, you should see the following qualities:
- All problems should be solved by at least 1 team
- No team should solve all problems
- No corrections were necessary to the problem set/example data
- No corrections were necessary to judge data
- All teams solve at least 1 problem
What other attributes could there be?
- Each problem should be focused on one thing (solving a particular algorithm or puzzle, testing input parsing, testing output tricks, validating data, ...)
- Most problems are basically math oriented or string processing oriented. A good problem set will be balanced (about 50% each).
- Since degree of difficulty can vary across a problem set, the problem set should be designed so that the problems are tiered (a pair of problems - one math, one string at each difficulty level)
- Input/output should be simple (unless the focus of the problem is complicated I/O)
- I/O should not impact runtime (make I/O simple enough that an undetectable amount of clock time is consumed by I/O)
- I/O should not favor one supported language over another
- Problem set should include at least one geometric problem
- Problem set should include at least one classic algorithm problem (a problem that essentially tests if the team can code the algorithm -- such as Floyd-Warshall, Dijkstra, ...)
- Solving one problem should not make another one easier. Otherwise, not being able to do one problem eliminates another problem from the field.
- No problem should need more than 20-25% of the time to solve and code.
Additional attributes of a problem set that I prefer:
- If a problem could have multiple answers, change what you want. Instead of asking for the answer, ask for how many steps in the answer. In other words, if a problem is to traverse from A to B and multiple valid paths exist, rather than printing any one of them, make the answer be how many unique paths exist
- Go for concise output, concise input is bonus
- Consistency across problems is highly desirable (similar format of problem statement, similar I/O design when appropriate)
- Blank lines should not be meaningful in input (impacts ease of I/O across languages)
- Use white space of any kind as a delimiter, but not multiple kinds as different delimiters
- All data should use a trailer card or a counted input mechanism (avoid end-of file testing)
- Problems should be 1 to 2 pages long. Longer than 2 pages usually means that the problem is not being expressed clearly or that the problem has too many addons.
- Problems should be perfectly understandable without pictures/drawings/charts/tables/... Printing of problems is not always perfect for these. A problem that requires them to be understood can easily be harder for some (because of printing issues)
- Color can be helpful but should not be required for the problem to be understood (one again -- printing issues)
Odd things that might matter
- As for diagrams and color, we once had a blind participant and provided that competitor a braille copy of the problem set. Think of the impact of color and/or diagrams on visually challenged competitors.
- I suggest double sided printing. It does make the team flip back and forth some. It also is more environmentally friendly. More importantly, it shortens the perceived size of the problem set.
Additional items to read:
- Google Code Jam Problem Preparation Guide
- Guidelines for Producing a Programming-Contest Problem Set - Tom Verhoeff, The Netherlands