SRM 688, D2, 250-Pointer (ParenthesesDiv2Easy)

James S. Plank

Tue Sep 6 00:32:52 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2016
Competitors who opened the problem: 663
Competitors who submitted a solution: 598
Number of correct solutions: 471
Accuracy (percentage correct vs those who opened): 71.0%
Average Correct Time: 10 minutes, 56 seconds.

This is one of those problems where the challenge is to spot the solution, and not to overcomplicate it. When you read the description, you may be tempted to use recursion, because that is how depth is defined. However, you can measure the depth simply by maintaining a counter while you traverse the string from left to right:

Start with the counter = 0.
When you see a left paren, increment the counter.
When you see a right paren, decrement the counter.

The counter is the current depth of the string, so simply record the maximum as you scan through.

Let's look at examples:


Example 0:  ( ( ) )
            1 2 1 0  -- Max depth = 2

Example 1:  ( ) ( ) ( )
            1 0 1 0 1 0 -- Max depth = 1

Example 2:  ( ( ) ) ( )
            1 2 1 0 1 0 -- Max depth = 2

Example 3:  ( ( ( ) ) ( ) ) ( ( ( ( ) ) ( ( ) ) ) ( ) ) 
            1 2 3 2 1 2 1 0 1 2 3 4 3 2 3 4 3 2 1 2 1 0 -- Max depth = 4

SRM 688, D2, 250-Pointer (ParenthesesDiv2Easy)

James S. Plank

My solution