Simulation Problems

Recently when we designed the problem set for the CMU Spring Invitational the topic of simulation problems came up. We had 10 problems, and not a single one was a simulation. It took us about 45 seconds to dismiss the concept of a simulation problem. Our team and coaches are all fervently against simulation problems.

The reason is really quite simple, simulation problems aren't interesting problems. They don't require any insight to solve them. All that is required is to accurately translate a set of (usually very complex) rules into code. The solutions tend to not be elegant. The console time needed to solve them is terrible. They are usually very long, and have enough special cases to force more than a couple of resubmissions.

While I think a majority of people will agree that simulation problems are not very interesting, we still have to deal with them. My view has shifted recently, I think that simulation problems are interesting because they are problems from world finals or regionals. We are going to have to compete with this problems, so we need to get better at them. Which of course begs the question, how can you get better at simulation problems?

I have yet to really try and get better at these, but that won't stop me from throwing around a few ideas. I think that solving a bunch of simulation problems will help, but not that much. Simulation problems are rarely similar to other problems, so solving one won't really help you in another one down the road.

Alan came up with, what I think is, a much better way to practice these problems. Assign one problem to your team/coaches every week. Everyone individually solves the problem (while attempting to still write code on paper and minimize console time), then everyone gets together and talks about how the implemented in and what cool tricks they used, and what tripped them up.

For these types of problems we don't need to get together to figure out how to solve them, but we can still get value out of seeing other people's ideas. I think what we will see is that most simulation problems, while lacking an elegant solution, have some solutions which are significantly easier to code and debug than other solutions.

I'm interested to see how much better we can get at simulation problems by putting some time in to practice on them. If anyone has put in a tone of time I would love to hear from them about how much better they are. My best guess is that we won't save too much on the amount of man hours it takes to solve the problem, but that we can cut the console time the problems take down significantly.