Editorial for Lyndon's Golf Contest 1 P8 - Beautiful Brackets


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: Dingledooper

68 bytes

For this particular problem, there are several different approaches that lead to a high score, but may not necessarily be optimal. The intended solution relies on the two conditions that define a beautiful bracket sequence:

  • The sequence must be in lexicographically sorted order.
  • The number of (s and )s must be equal.

To handle the 1^\text{st} condition, we can write a for-loop, which exits as soon as the previous read character is lexicographically greater than the current character. If the bracket sequence is not in sorted order, then the current character must have stopped on either ( or ). Otherwise, if it is in sorted order, the for-loop would terminate upon reading the newline character, so it would stop at \n. A simple ternary condition to check that the character's ASCII value is greater than 10 suffices:

main(c){for(;c<=(c=getchar()););puts(c<11?"YES":"NO");}

Note that this solution works in Clang but not GCC, since for some reason GCC evaluates the right side of the comparison first. Next, we need to integrate the 2^\text{nd} condition. This can be done by initializing a counter variable n, and incrementing it by 1 if the current character is ), and -1 if the current character is (. Using the fact that the ASCII values of ( and ) are 40 and 41, respectively, we can write this in code by doing n+=c*2-81. Then, a bracket sequence is beautiful if and only if c \ge 10 and n = 0. These conditions can be implemented in the code as c>10&!n?"YES":"NO", but a byte can be saved by reversing the condition: c<11|n?"NO":"YES". Finally, here is the 68-byte solution in full:

n;main(c){for(;c<=(c=getchar());n+=2*c-81);puts(c>10|n?"NO":"YES");}

66 bytes [*]

Although not necessary to score full points, a 66-byte solution was found during the contest by JoKing:

c;main(n){c>(c=getchar())?puts(c*n-10?"NO":"YES"):main(n+2*c-81);}

The idea is to use main recursion to loop instead of a for-loop. The argument n passed to main updates the bracket count after each iteration. It should be noted that the formula used the check the final condition is different, since n equals 1 by default when put as the first argument to main.


Comments

There are no comments at the moment.