Lewin's blog

How to come up with problem ideas
By Lewin, history, 6 years ago, In English

I wrote a post about coming up with problem ideas here with some examples: https://www.topcoder.com/blog/how-to-come-up-with-problem-ideas/

  • Vote: I like it
  • +327
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I love problems like Rainbow Graph, please make more problems about matroids!

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +112 Vote: I do not like it

    I don't like it. I believe that crafting a problem with a somehow advanced algorithm without other insights is not a good practice for problem settings, though I have also done it for many times.

    Personally, I like problems with a modest model which can be solved by some really clever tricks no people have noticed before.

    (feel that I will get many downvotes, lol)

    Anyway, it is still a great post. I am always curious about how different authors set problems. I particularly wonder how jqdai0815 to come up with so many interesting problems I cannot solve.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      (feel that I will get many downvotes, lol)

      Your opinion is much more popular, I can guarantee it.

      somehow advanced algorithm without other insights

      I believe Rainbow Graph does need other insights, although not everyone agrees.

      Problems which are a simple application of some tricks are usually not cool, but sometimes community needs them, and I'm happy if they contain something that's really cool or important. Matroid is both. It's very cool, and it's also one of the most important concepts in theoretical CS.

      I learned about matroids after a problem in PTZ that's "just matroid intersection". The theory behind it was super cool, and I ended up really liking that problem.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +11 Vote: I do not like it

        I think you might somehow misread my comment. I agree the "simple" application of tricks is not cool.

        Talk about the "Rainbow Bridge" problem. The task is fine, even nice. But it's just not of my taste. I agree that matroid is cool. When I firstly encountered matroid several years ago (like in 2010), I was thrilled. I even skimmed through a book titled "Matroid Theory" to learn more. I am doing theoretical cs research, though not in the subfield of combinatorial optimization. I can also recognize the importance of matroid. So in either way, I am not ignorant about or belittle the matroid itself.

        It seems to have a tendency to prefer advanced problem. But it's of personal style, while I am talking in the general competitive programming context. I was trying to make a point that our community should emphasize the problem-solving skill, not laying the hardness of a problem in its sophisticated background.

        In the meantime, I think introducing advanced stuff to our community is necessary, especially in training contests like Petrozavodsk. I personally like BM-algorithm introduced into our community in recent years. It's super nice. But if I find such problems are presented in a serious contest like World Finals, I feel frustrated. I also have to admit I have such feeling because team Dreadnought didn't solve a problem in WF 2016 without a good linear programming solver in their libraries and lost the competition.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        I don't like problems about [obscure mathematical thing] because "can a contestant solve this problem?" very often reduces to "contestant knows [obscure mathematical thing] and how it's used to solve these kinds of problems". Any tricks specific for that problem will usually be trivial compared to being able to spot that it should use that mathematical thing, and if they aren't, the problem is most likely utter overkill.

        You need to know some theory for everything, but it's a question of difficulty. If you don't know Dijkstra, you can figure out the algorithm by yourself in-contest, it's not so hard. If you don't know Grundy numbers, you can... print some patterns and figure out Sprague-Grundy theorem by yourself, I guess? Still, that takes a lot of luck and it turns out that a lot of problems on games are boring applications of that theory, sometimes with heuristics / pattern searching to speed up computing Grundy numbers. It's already skirting the line. If you don't know matroids, you can go outside.

        Fun fact: I had Lewin propose a matroid problem to a contest I tested. I didn't understand the theory and he couldn't explain it in a way that I would understand (intuitively enough), so I couldn't honestly accept it as a contest problem.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it -10 Vote: I do not like it

          In a same way one could come up with matroid intersection, and I know at least two people who can do that in Korea. (or more exactly, solving this one without knowing what matroid is)

          I can imagine someone figuring out matroid intersection easily, but I can't imagine someone figuring out SG that way. It's much less intuitive. (Btw, I don't like to see SG on contest, because I think it's obscure math :D)

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, SG isn't intuitive at all (why the hell XOR?), the most you can do is guess that single games can be described by numbers and look for the relation between them and how they're computed by analysing some small patterns.

            How do you come up with matroid intersection without matroids?

            → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thank you for writing this, this is really helpful. There's a lot of resources for improving in competitive programming, but relatively few for problem creation and judging.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We should try to study your problemsetting strategies before your upcoming contest :P

Jokes aside, very nice article, thanks for sharing it :)

→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Only the 3rd way leads to good problems

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Why is this downvoted? I agree the 3rd way produces the best problems.

    → Reply
»
6 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Years ago, I used to set a lot of problems. I was in the "problem setting mindset" you mention almost constantly. Watching movies, reading sci-fi, working out, and even sleeping generated new problem ideas.

The issue was that I lost the ability to turn it off and just enjoy my surroundings. Some part of the brain constantly interpreted situations as programming contest problem setups. It took me a while to finally shake it off.

Are you able to enter and exit this mode freely? Do you feel like it affects your interpersonal interactions?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I was going to answer this earlier but got a bit busy with some problem preparation :)

    Right now, I wouldn't say I can freely enter/exit this mode, but maybe it's a different experience for both of us since it doesn't seem too distracting to me. For me personally, I'll notice small things to put in the back of my mind. They'll come up later when I sit down and actually want to invent some problems. In the moment, however, I usually don't get too distracted when socializing or doing other activities since I'm able to put it away in my mind.

    I haven't really talked to too many others who have set a lot of problems, so I imagine our experiences could vary a lot. I have also thought about whether I'm spending too much time thinking about new problems. I would want to slow down or take a break if I felt it took away too much from other aspects of my life, and at least for now it is still enjoyable for me, and I have other non competitive programming things that I enjoy.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How I make problems: I pluck out ideas from... somewhere?

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

To create problems, I just sitdown, close my eyes, and suddenly problems come to my mind. The hard part for me is to solve those problems, if I can't solve them I reduce them until problems are solvable.

→ Reply