dalex's blog

Beauty of problem statements
By dalex, 6 years ago, translation, In English

Some weeks ago I read a Quora answer by I_love_Tanya_Romanova (link). The 4th paragraph attracted me, here is it's short content:

There are jokes about these typical problem statements: “Little Rohit got an array as a birthday present”. I’m also not getting why these trashy statements should be writtten instead of formal model of the task. It is awesome to have fictional statement when it makes sense, or when it comes from real life; it is at least funny to have stuff like problems I mentioned above. And I know that some of the platforms I mentioned are requiring problems with fictional statements and say that formal models are bad. Well, OK, “Parents asked little Chandan to perform following operations…”. May I go to some other site and solve normal problems, please? That’s a matter of taste — but for me this kind of statements is something that makes strong negative impression, and I think I’m not the only one.

I also don't like statements where characters were added just because there were no characters originally. You read such statement and think: "Why do they added this Alice with her birthday present? It has nothing to do with the problem".

I think there must be some rules that authors should use when they write a problem statement:

  1. If the problem comes from real life or from some situation that may appear in real life / fiction book / computer game — use the original statement. Those who will solve this problem will be clearly understand what's going on.
  2. If the problem originally had the formal statement (e.g. you have an array and you have to answer some queries, you have an array and you have to find a subarray with maximal xor / and / or, and so on): use formal statement.
  3. Never introduce a setting if the problem originally had formal statement.
  • Vote: I like it
  • +116
  • Vote: I do not like it

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

I always thought that the reason why we do have stories rather than formal statements is to make it accessible for everyone. When you give the statement formally, you assume that everybody knows the notions you use.

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

    Interesting. I always thought that this is the cause of this phenomenon, but as far as I can see I should have been embarrassingly wrong ;).

    What's the explanation, then?

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

    What's the difference between

    "you are given an array, find subarray with maximal sum"

    and

    "olekluka got array on his birthday and he loves to find an array with maximal sum. Help him to find it!"

    accessibility-wise?

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

      There is a kind of misunderstanding here.

      I just expressed my belief about why these kind of stories even appeared (for the first time) in competitive programming tasks. Why problem-setters once introduced this approach rather than keeping formal statements like most of the mathematical competitions do.

      If it's right or wrong, if people abuse it or not, if I support it or not, etc. — these are completely different stories and I didn't address any of them in my comment.

      I wrote what I wrote. No more, no less.

      I admit that I just didn't feel like being comprehensive when I wrote it. But I hoped that such a laconic statement would be sufficient to express what I wanted to express.

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

Here is a good example: http://codeforces.com/contest/879/problem/B.
The problem statement looks great without any Boris or Petya.

Here, on the other hand, is a bad example: http://codeforces.com/contest/877/problem/B.
There was no need in introducing Nikita to the problem. It looks artificial and worsens the perception of the problem.

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

I'm not sure whether this statement is good or bad, but I would prefer it with a setting than in a formal style. Because it's funny.

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

    Sometimes it is not funny and doesn't make any sense, just bunch of sentences and waste of time...

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

      Sometimes? It's more like in 75% of the problems.

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

    I think it is a good statement. It describes a fictional situation which is easy to understand.

    If it was about queries like "treat teeth from L-th to R-th where the cost of treatment is bitwise OR of A[i]" — then I'd say it's bad.

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

Could you please explain what you mean when you say "originally" or "problem comes from" in your post? You state:

If the problem originally had the formal statement

twice in your post. I'm not quite able to understand this, how can the problem "originally" have a formal statement if the author just created it?

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

    Some ideas for problems come from real-life situations. For example if you start wondering where to put a firefighters station to make city safest, then it's reasonable to keep the story about firefighters, even if the final problem ends up quite far away from the original idea.

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

It seems to me that it is not that easy. The statement “Little Rohit got an array as a birthday present (...)” sounds worse than "You are given an array (...)". On the other hand "Rohit and Chandan play a game. Rohit goes first and chooses (...)" seems better than "There is a game. A player on their turn can choose (...)". The level of fiction seems similar for these two, yet I see them different. Probably the biggest difference here is that playing games is what we expect to be done by humans (or maybe foxes too) while receiving an array for birthday is not. But we already need to judge by very slight differences and it's not as obvious as you propose.

I can't agree with point 3, there are many good statements that make sense but were introduced after having a formal statement. I also can't agree that this should be anything more than a friendly suggestion. The fact that some people create this kind of statements means there are also people who enjoy them. We may want to satisfy the majority most of the time, but there is nothing wrong in satisfying minority from time to time. It's not like a problem becomes harder to solve when you don't like the statement.

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

Let me recall one of my favourite statements:

"There are c! snukes in a room whose sides are a! and b! meters. Determine whether snuke's density per m^2 () is an integer."

This statement is so made up it makes it pure gold xD

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

    Hi, so to me seems like a notorious coincidence. 869B - The Eternal Immortality has an even shorter formal statement involving factorials, yet its far longer description makes it pure platinum.

    The point is, it makes no sense to people who don't know about the original plot. I've also seen situations where authors just want to include their own/favourite/whatever character they want with complex plots interesting to only a small fraction of people, and consequently leading to confusion. Authors should bear in mind that problems are not for "sharing plots".

    Thanks comminuty, your views are thought-provoking. Expect better statements next time :)

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +119 Vote: I do not like it

Talking about wasting kilobytes of pdf size

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

    Where is it from? Looks like a fake (or not) acm joke

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

      http://opencup.ru/files/ocg/gp5/problems1-e.pdf

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

        So it is real. One of the stupidest jokes ever. Once we encountered such a task during Polish summer camp. Not a pleasant experience. Some teams got it in the very first try, some had +20. Truly destroying the competition sometimes...

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

          Why? Everyone solved it: link

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

            So how to solve this problem???

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

            Still, it isn't as clear as you might think. I wasn't sure if we should print "Pfff" only for "I am Groot" or maybe for anything that is not of form "I am Groot!...!". Maybe some other input is allowed in tests, maybe not.

            I wasted an extra minute or two for that, just to be sure. It isn't very important but I wouldn't want this problem in an important competition like the acm-icpc qualifiers.

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

          Watch out, we got Mister Serious here. I dont know which problem you're talking about, but I am sure you're talking about some of team competitions on ONTAK. This is always meant to be a contest with a few funny problems, not a competition for golden underpants, so calm down.

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

            I'm pretty sure that "golden underpants" is a polish idiom. But it looks pretty cool in English :D.

            I remember the task "count the number of balloons in the room" during my first competitive programming camp ever. It was fun :).

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

            Ehh.. Maybe you would look at it differently if you were with Radewoosh forcing you to sit a whole 5hr contest on it (and you end up sitting on it instead of admiring his magnificence) If a competition is known to feature such problems then fine (ipsc), but otherwise it can be irritating

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

              Lol, ipsc is not known for featuring funny problems, it is known for featuring not typical and creative problems which is not the kind I am talking about. On the other hand, team competition on ONTAK in fact is known for featuring funny problems (like "What kind of soup is served today?" where contestants needed to run all the way to the dining place or solving some puzzles in form of digit crosswords or some clearly trolls or many more examples). Which problem are you talking about? Tapczany :P? But in general, yeah, sitting 5hrs on a joke problem is not a good idea, you should have done something else and some of your teammates should have looked at it.

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

    I remember seeing this in a contest... I do not know who made it, but I got a meme for him

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

I think csacademy has the best form of direct statements.

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

This is a problem from 2017 Xi'An regional ICPC.

( Fun fact, LoL worlds semifinals were held in the same weekend. )

Problem J: LOL

My team's reaction:

Teamate A: I don't play video games, pass.

Teamate B: I don't play video games, pass.

Me the nerdy gamer: Dude this is NOT League Of Legends.

Before the clarification was made have no idea how did that random number showed up. I think if someone is following rule 1, they better make sure that they stick close enough to the rules, or else it will confuse the readers even more. ( but sure, don't ask the original statement, or else it's just free to whose thought about this in their free time )

This problem from 2014 Xi'An regionals is another case: UVA5047

The problem statement is packed with Chinese memes, and since the problem statements are in English, the original references are translated and slightly altered based on their pronunciation. I had a hard time in understanding the problem statement since I am terrible in Mandarin.

Anyways, this problem is a filler question without a doubt, all it asks is just return if all elements in the list is divisible by 3.

What will you choose:

  1. Don't even ask this question, instead of providing 10 problems, 9 will do.

  2. Give a formal statement so everyone could solve it instantly.

  3. Put it at the front so every team can notice this problem immediately, and use it as a buffer question to slow down teams a little bit, just a little.

( 4. Aww all these options are so bad aren't they? )

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

As a mere purple, here are my two cents on the issue.

I'll start by saying that I prefer solving problems with short, formal statements. They are easier to parse and understand, and a problem with a short formal statement will always have more appeal to me than one in which you've got two read two pages of text to even begin to understand what you have to do.

However...

I guess to get to my point, I first have to talk a little bit about competitive programming in general. I've heard many people (including competitive programmers who arr better and more involved than me) saying that competotive programming is "useless" in real life. That most tasks that arise are simple and if you don't know an algorithm you can just google it. While that is partly true, I have to strongly disagree against the "useless"-ness of competitive programming. Through personal experience, I've noticed that competitive programming has helped me a lot. Not directly, but via the algorithmic and logical thinking, via the approach to problem solving, via how I view competition and many other things it has "injected" in my brain. The very nature of competitive programming makes you solve brand new and unknown problems everytime. This, up to an extent, emulates life itself. In life, you are often put in situations that you've never seen before, that you don't know how to react to. If your brain is trained to deal with this type of situation (for example, through competitive programming), you will find that you will very often find a way to solve said situation (maybe not the prettiest way, but definitely one that works).

I've noticed that when performing routine, daily tasks, competitive programmers perform pretty much the same as everyone else. However, when it comes to learning new skills (new programming languages, new frameworks, or even playing some new game), competitive programmers very often catch on way quicker to what's happening and manage to aquire said skill faster than "regular" programmers.

With all of that in mind, back to the subject at hand, in real life situations your task will most often not be stated formally. In life, you won't know exactly what you have to do. You might not even know that there's a task to begin with (you might look at some part of your job and say "hey, an efficient automation could be implemented for this" and as such create a task yourself). This is the reason why I think informal problem statements are good. They train the brain in a certain way. They train the brain to be able to interpret whatever situation it is put in and find a solution for it, no matter how clearly the situation is "stated".

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

    I think it's the other way around. Competitive programming doesn't make people "learn faster", it's just that people who learn faster like competitive programming because they're able to get good faster, and so they stick with it as opposed to quitting early.

    As for the problem statements, I don't think it is related to real life at all -- in these statements it is just a bugger to sift the information from the pointless story. You still have all this concrete information such as the data size and time limit, most of which isn't given to you in real problems. Competitive programming doesn't really train the brain to interpret a real-life situation, only to interpret meaning from fluff.

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

Well, I like these two: 414B - Mashmokh and ACM, 414C - Mashmokh and Reverse Operation

→ Reply