Lynbrook Computer Science

The November USACO is over, and preliminary results have been released! Good job to everyone who participated!

In today’s meeting, we went over solutions to one bronze, one silver, and one gold division problem from the last USACO. We also went over the solution to last week’s Problem of the Week, and introduced the new problem, which is as follows:

• One day, at school, Bessie wrote a string of matching ‘(‘s and ‘)’s. As soon as she got home, however, she noticed that she had definitely made some mistakes!
• She plans on covering this up by simply erasing some of the parentheses on the left and right, while aiming for the longest substring.
• The substring she obtains must be a valid sequence of parentheses – each ‘(‘ must match to a ‘)’ to its right, and vice versa. Tell Bessie the length of the longest valid substring.

• For 15 points, implement a solution for length < 100.
• For 25 points, length < 1,000.
• For 35 points, length < 1,000,000.

For input/output examples, and to look over the solutions presented at this meeting, see the meeting slides.