royappa's blog

Question about problem statement
By royappa, history, 7 years ago, In English

In a topcoder problem recently, there was this definition:

Correct parentheses sequences can be defined recursively as follows:
* The empty string "" is a correct sequence.
* If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
* If "X" is a correct sequence, then "(X)" is a correct sequence.
* Each correct parentheses sequence can be derived using the above rules.

What is the purpose of the last line?

I've seen this type of extra condition many times and have to spend time thinking about whether it means something for the solution. Usually I can't think of something, and so (for me) it wastes time during a contest.

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

Comments Comments (3)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

This just means there are no other bracket sequences: all bracket sequences that exist can be generated this way.

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

    Suppose we deleted that last line. Is there some bracket sequence that does not fit the first three conditions? Thanks.

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

      Any sequence, like ())))(. If that sentence wasn't there, then that might also be a correct bracket sequence, because there's nothing explicitly saying it isn't.

      → Reply