Editorial for DMOPC '19 Contest 4 P1 - Valid Strings

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

For this problem, note that the only relevant thing is whether the brackets are balanced. Since all characters are either digits or brackets, we don't care about invalid characters. Furthermore, the digits have no relevance to the solution since they can be placed anywhere without problem.

Therefore, we only have to determine if the brackets are balanced. A good way to do this is to keep track of bracket depth. Every time you encounter an open bracket, increase this counter. Every time you encounter a closed bracket, decrease this counter. If the counter is ever negative, the sequence is invalid. Also, if the counter is not 0 at the end of the operation, the sequence lacks closing brackets, and is also invalid.

Comments


  • 4
    c  commented on Jan. 13, 2020, 12:39 a.m.

    Another possible method is using an amazing function in some languages called eval(). This is generally only available in scripting languages like Python, Ruby or JavaScript.

    Simply replace all open brackets with, for example 1*(, all closed brackets with )*1 and all () with 1, then prepend the string with 1* and append *1, and run the eval() function. Catch all exceptions, if an exception occurs, the string is invalid, otherwise it is valid.

    For example, ((1))(2) would be 0*1*(1*(1)*1)*11*(2)*1*0.

    Its a nice trick to learn if you want to solve cheese these kind of validation problems (try bananas!)