More programming problems

I kinda failed today's round. But oh well.

Problem A:

This is very simple implementation.

Problem B:

We just keep track of the sum of the differences between increasing columns for all intervals $[0,i]$ in an array $d$. Then we can get the jump damage for any $[i,j]$ interval using $d[j]-d[i]$.

Problem C:

A bracket sequence is regular (RBS) if and only if:

1. number of '(' = number of ')',
2. for every prefix: number of '(' $\geq$ number of ')'.

Idea 1: Iterate from left to right through $s$, whenever we meet a '?' determine if it may be replaced by a '(' and a ')'.

Replacing '?' with '(' can never break condition (2), however to satisfy (1) we need to ensure that we do not replace so that number of '( > number of ')'.

Replacing '?' with ')' requires that the current nesting depth is $>0$. Furthermore, we must not use too many such that we number of '(' < number of ')'. Additionally, we need to ensure that this replacement does not violate (2) which can occur even if the nesting depth is $>0$. For example in '(?)?' the first question mark is at nesting depth $1$, however if we replace it with ')', the sub-segment $[1,3]$ has more ')' than '('. However, I am not sure how to make this work.

In the end I used a hint from the editorial. Apparently problem D was easier than C, I noticed this in contest but was too stubborn to switch.