BEATRICE - Editorial

PROBLEM LINK:

Practice
Contest

Author: mesksr
Editorialist: mesksr

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

Given a series of “i”(s) and “d”(s). We have to increase the value by 1 when it is “i” and decrease it by 1 when it is “d”.
We have to find the minimum sum of start and end value. We also need to make sure that the value does not become negative at any step.

EXPLANATION:

We need to understand that start and end value are directly related.
end value = start value + constant (based on “i”(s) and “d”(s))
So, it is safe to say that we just need to have minimum start value.

In order to have the minimum value, we should encounter 0 at least one in the sequence.
We set the start value and answer (answer is the final value) both to 0 — The condition for empty string.
We move forward following the rules, whenever the value goes below 0, we increment the start and reset the answer value to 0.
This ensures that answer is never becomes negative and while keeping the starting value minimum.

AUTHOR’S SOLUTION:

Author’s solution can be found here.