Editorial for Lyndon's Golf Contest 1 P8 - Beautiful Brackets
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 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 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 condition. This can be done by initializing a counter variable , and incrementing it by if the current character is )
, and if the current character is (
. Using the fact that the ASCII values of (
and )
are and , respectively, we can write this in code by doing n+=c*2-81
. Then, a bracket sequence is beautiful if and only if and . 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 -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 -byte solution was found during the contest by :
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 by default when put as the first argument to main
.
Comments