Ad Hoc Problems
Author: Michael Cao
Problems that don't fall under any well-defined category.
Most bronze problems fall into specific categories, such as simulation and complete search. Those which don't often require more thought, although they are not necessarily more difficult to implement.
Any problem that doesn't fall under any well-defined category can be labelled as Ad Hoc. Since there is no fixed algorithm or idea to solving these problems, they can be hard to generalize. In this module, we'll go over some general tips that may be useful in approaching these problems.
- Draw lots of small cases to gain a better understanding of the problem. If you're having trouble debugging, draw more cases. If you don't know how to start with a problem, draw more cases. Whenever you don't know how to further approach a problem, you're probably missing an important observation, so draw more cases and make observations about properties of the problem.
- Whenever you find an observation that seems useful, write it down! Writing down ideas lets you easily come back to them later, and makes sure you don't forget about ideas that could potentially be the solution.
- Don't get stuck on any specific idea, unless you see an entire solution. Trying to complete search an Ad Hoc problem could end up wasting a lot of your time in contest.
- Try to approach the problem from a lot of different perspectives. Try to draw a visual depiction of the problem, mess around with formulas, or draw a graph (see Graph Theory module). One of the most helpful things you can do when solving Ad Hoc problems is to keep trying ideas until you make progress. This is something you get better at as you do more problems.
These tips are helpful in solving Ad Hoc problems. However, in the end, the best way to get better at Ad Hoc problems (or any type of problem) is to do a lot of them. Try to solve as many practice problems below as you can, and click the solution sketch tab if you can't figure the solution out.
Don't you love Dhruv Rohatgi problems?
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!
Give Us Feedback on Ad Hoc Problems!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.