May 2, 2019 How to Come Up With Problem Ideas
Over the past few years, I’ve written a lot of problems for Topcoder SRMs, codeforces rounds, ICPC contests, and various other online platforms. When I get asked how I come up with problems, I usually don’t know where to start. I decided to sit down and write some of my thoughts on the matter.
Before getting into any specific examples, I want to explain something I call a “problem setting mindset”. Everyday, I look at ordinary objects and my mind will automatically start thinking about framing it as a competitive programming problem. When I’m competing, I’m also thinking about how the techniques that are being used in the current problems could be featured in new problems. There are problem ideas everywhere! It is my way of seeing the world. I’ll show you some examples, and there is so much more compared to what I’m about to write down.
1. Work from a solution and go backwards
This technique is best for trying to learn something new. I would learn a new trick and then write a problem about it to reinforce my learning about it. I usually find these topics when I encounter a problem I can’t solve in a regular contest or when I read some codeforces blogs. I internalize it by writing a problem about it.
One example of this is Yet Another Tree Problem. I had recently learned about centroid decomposition. I looked at some examples of how it worked, and thought of extensions of it. The new twist I added was the convex hull trick. I realized how to link the two techniques and now I understand both techniques even better. I thought the combination of the two was an interesting application, and the statement turned out to be pretty short which is also a plus.
Most of these problems don’t feel too original to me. They use more well known techniques, and are usually around medium to hard in difficulty. It’s hard to write a good easy problem at this level, since it usually requires some specialized knowledge. Personally, I don’t think these problems are necessarily bad; they are needed in order to keep up a high volume of contests, and could be good introductory problems to some more advanced topics.
Some other example problems I’ve written using this technique:
– Uniform Trees. I came up with this since I recently learned about the smaller to bigger trick. The key idea that I wanted to use was keeping dp on only necessary states to also count.
– Hamiltonian Spanning Tree. I knew about the greedy solution for finding a matching in a tree, and saw that it could generalize to find two matchings in a tree as well. I disguised the problem a bit so the correspondence wasn’t completely obvious.
– LoopyPath. I wanted to write a problem about winding numbers. I had to add the constraint that we had to visit each grid cell at least once in order to make it tractable (otherwise it is equivalent to steiner tree on a grid graph).
– TrianglePainting. I learned about Minkowski sums and saw that you could also apply linearity of expectation to the area of a convex polygon to get this problem.
– Robot Arm. This is probably the first data structure problem I wrote. I combined a segment tree with matrix operations to rotate/translate in a 2d plane.
– SegmentCutting. I wanted to write something about sweeping in a circle. I thought hiding some part of it as “square of euclidean distance” was nice, and it works for arbitrary polynomial functions on the difference of x and y coordinates separately.
Usually, I’m excited when I first come up with a problem like this since it is a new technique to me. It does have higher risk of colliding with something that has been set previously, however. It’s hard to keep track of what’s new and original, and I’m still trying to improve over time. I think almost anyone can use this technique to make new problems, and it will help you improve if you’re trying to learn standard algorithms.
2. Take some random concepts and mash them together
This is the reverse of the previous technique. There are a lot of building blocks that you can use and combine in different ways to come up with new problems ideas. Some examples might be trees, arrays, subsequences, XOR, palindromes, and much more. You can combine random ideas together and see if the result is possible and interesting to solve.
One example of this technique is BridgeBuilding. I wanted to write a problem about minimizing diameter after adding some edges to a graph, but it seemed tedious with small bounds, and it seemed very hard to do generally in a clean way. I tried to look for special graphs where it still might be interesting to solve instead. I settled on this variation after seeing a ladder that was missing some steps and that made me think of two parallel line graphs with edges going in between some places. It took me a while to actually get a full working solution, and I had a lot of false starts when I tried to first solve it. It turned out to be a nice problem for the hard slot.
For these problems, it’s usually enough to make it so the bounds are big enough to time out very naive solutions. Sometimes you might get some cool easy problems from it. Occasionally, you’ll also get an interesting hard problem also.
Some other examples:
– Subsequence Reversal. I combined the concept of “reversing”, “subsequence” and “increasing”.
– Increasing Xor Sequence. I combined the concept of “increasing” and “xor” on a sequence.
– ParenthesisRemoval. There are a lot of things you can do with parenthesis.
– InterleavingParenthesis. Another example of parenthesis problem.
– Expected Earnings. I expected that this would be a known problem and was surprised that there wasn’t anything similar when I tried to look. The solution also looked a bit hard.
– Hongcow Draws a Circle. Geometry problems usually aren’t that hard to come up with, the main problem is actually solving them. Luckily, most problems can be solved with sweeps. A tester found an inversion solution which was nice and not intended.
This also has some risk of overlapping with previously set problems, since someone might have put together the same topics. This risk is a bit smaller than the previous technique, but it is unfortunately unavoidable. I try to mitigate it by participating in a lot of contests to get a sense of what other problems have already been set.
This method is also a lot more inconsistent and harder to use and requires more creativity. I would say it is closer to solving really hard ad hoc problems. You also gain some better intuition on what types of problems are solvable, and this helps with general problem solving skills and facing unknown problems in actual contests.
3. Take everyday entertainment and turn them into problems
There are a lot of problem ideas that come from watching tv, playing games, or listening to music. There is a lot of strategy in some of these games, and it is usually not too hard to extract out an interesting programming puzzle from it.
I used to like watching game shows when I was younger. I remember watching “The Price is Right” when I was in middle school. I would watch it when I was at home sick from school, since it only aired in the afternoon on weekdays, and I would never have the opportunity to watch it any other time. Some of the strategy in the game can be interesting. Several years later while trying to think of problems, I thought of games from that show. That’s how I came up with AnyNumber. It’s an actual game on the show and the rules are here. There might be some strategy to this game, but I wasn’t able to figure it out, and the problem seemed hard enough without that getting to choose an order.
Some more examples:
– WheelOfFortune. This is also a game show, and I only really just used their name. It has almost nothing to do with the actual show.
– BipartiteGraphGame. I got this from watching Futurama in their brain swap episode.
– AToughGame. I was watching someone play dark souls and they explained the soul collecting mechanic to me. I almost immediately thought of this problem and was distracted by trying to solve it.
– ReverseMancala. Inspired by the game mancala.
– Hongcow Buys a Deck of Cards. This is inspired by the board game Splendor.
– Combining Slimes. This is inspired from the 2048 game. It turned out to be a lot harder than I expected.
– Farmville. This is some facebook game that used to be really popular when I was in high school.
– Rainbow Roads. This is inspired from this puzzle game. The mechanics in the problem are a bit simplified, but I generalized it to multiple colors.
– Hot is Cold. This is inspired from this puzzle game. After playing this game, I mostly thought in sentences like [noun] is [noun], so I made a problem based on what I thought those sentences meant.
– Satanic Panic. Song titles can also help. I heard it here. When I saw this title, I liked that it rhymed and started thinking about what it actually meant. I imagined a person getting panicked because they were seeing symbols of Satan everywhere. Then, I thought about counting pentagrams.
This technique is easy to use and can generate a lot of interesting problems. I get to practice my problem solving skills in slightly more structured contexts. This is probably most similar to the second technique, and the main difference is that you don’t generate the ideas yourself but look to other sources to help. It does also have elements of the first technique if you are trying to use showcase the strategy of a game in a problem.
4. Pick your favorite topic and explore it further
This is a bit similar to the first technique. Sometimes it’s easy to take some topic that isn’t too popular at present in contests and write more problems about it. It also helps if you like the topic. In the following topics, I feel I write a disportionate amount of these problems compared to other setters.
For example, I like bitmask dp problems. They are satisfying for me to solve, and I can usually think of new ideas using it pretty easily. Here are some examples: 1, 2, 3, 4, 5. I also like digit dps. I especially like it when I can combine these with bitmask dps. Some examples: 1, 2, 3, 4, 5.
On the topic of bitmask dps, one extension is the fast walsh hadamard transform. I’ve come up with a few problems about it, and they usually are called hard even though I don’t think the main idea is that hard. Here are some examples: 1, 2, 3, 4, 5. I could probably write a blog post on it to explain more applications at some later point if there’s interest in it, but there is already a good one here.
One last example is matroid problems. I tried to bring matroid intersection to some contests last year. I think these problems can be pretty interesting like flow, in that the reduction is interesting in itself and you can use matroid intersection as a black box. The problem is nobody has matroid intersection book code, so this didn’t seem to work out very well. The proof also seems pretty hard to grasp with only elementary knowledge, so it seems it will stay out of reach for now. Maybe we will see it more in the future if it ever becomes easier to understand or more mainstream. Here are some matroid intersection problems that I set last year: 1, 2. I’m not sure if it’ll be a topic that people are interested in solving, and maybe there just needs to be more education about it to make it more popular.
5. Look at papers and other sources
Sometimes, reading other things can help with making problems. I think it is ok to use papers as sources of problems sometimes, but it should just extract out the interesting problem solving part and make sure it is approachable using known techniques in competitive programming. It should also be the case that knowing the specific paper shouldn’t give a significant advantage (though this is sometimes unavoidable, so the best you can do is make sure the source is obscure enough).
I don’t actively read papers. Instead, I usually stumble upon something when I’m trying to solve something unrelated in contest and get ideas. One example is Xor Game. I found Shannon’s switching game while trying to read about matroids during a contest. I modified it a bit to use a different matroid instead. I don’t think this is that great of an example though, since the proof was too hard to understand and explain, and isn’t really solvable using elementary techniques.
The two problems below are better examples of using other papers:
– New Year and Rainbow Roads. This was a subproblem from a paper, and I don’t remember what the original was about. I think this one is better to use since it’s hard to find the original source, and it’s also easily solvable without needing to know anything from the paper.
– StonesOnATree. This came from a paper in machine learning about trying to minimize the amount of memory needed when training a model. You can treat it as some dag; you need to store some state for each node, and you need to store all of the predecessor’s state to compute a node’s state. This paper claimed the problem is not easily solvable, but I thought it would be easier on a tree. It turns out it’s hard for a tree also, and you need to add some other conditions on the weights of the tree. This is an example where I would not have thought of this idea without reading the paper, but I was able to turn it into an approachable problem.
Sometimes problem writing involves looking at other external sources for ideas, and doesn’t have to be just copying them directly from their sources. It is still possible to write interesting problems without using things from papers directly, since there are interesting problem solving aspects to extract.
6. Look at previous problems and see if the titles can inspire you
Finally, this one is kind of silly and I thought I should include it. It might only work for me though. Sometimes just reading some words makes me think of problems. Some titles resonate with me more (especially ones that alliterate or rhyme).
– RainbowRoads: 1, 2, 3, 4, 5, 6. The concept of having colors on a graph or tree can lead to a lot of different problems.
I’ve also done this by looking at titles from other authors.
– LimitedMemorySeries2 was inspired from LimitedMemorySeries1
– Constellation came from Constellation
Conclusion
To wrap up, there are a lot of different ways to make problems. I used to worry about running out of problems and ideas in competitive programming. However, whenever I start worrying about this, I can almost always come up with more ideas after a week or so. Next time you see me as a problem setter, you can guess what to expect. It might include some bitmask dp problems, and maybe a problem about rainbow roads.
Harshit Mehta
Sr. Community Evangelist
