You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

asked 23 Mar '16, 17:14

mesksr's gravatar image

5★mesksr
3
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,652
×643

question asked: 23 Mar '16, 17:14

question was seen: 521 times

last updated: 23 Mar '16, 17:14