 # GPNY-Editorials ( UVCE NCode-November 2013)

## Editorials-GPNY

Contest

Author: Bharathkumar Hegde

Tester: Amogh Aithal

Editorialist: Bharathkumar Hegde

### Problem :

``````Volume of a container will vary for certain seconds, find the maximim raise in the volume of container/volume of water in the container, such that volume of container should not be zero in between and at, starting and ending time of maximum raise.
``````

### Solution :

``````<img src="https://fbcdn-sphotos-e-a.akamaihd.net/hphotos-ak-ash3/s403x403/1459344_536697786419852_71001760_n.jpg" alt="Experimental setup">

Volume of <strong>C<sub>2</sub></strong> depends only on the volumes of <strong>C<sub>1</sub></strong> and <strong>C<sub>3</sub></strong> so <strong>Vol_in_C2<sub><i>i</i></sub></strong> can be calculated as follows.
<pre>
Vol_in_C2<sub>0</sub> = Vol_in_C1<sub>0</sub>
for each i from 1 till N :
Change_in_C1 = Vol_in_C1<sub>i</sub> - Vol_in_C1<sub>i-1</sub>
Change_in_C2 = Vol_in_C2<sub>i</sub> - Vol_in_C2<sub>i-1</sub>
Vol_in_C2<sub>i</sub> = max (0 , Vol_in_C2<sub>i</sub> - Change_in_C1 - Change_in_C2)
</pre>

Now we need to find the maximum raise in <strong>Vol_in_C2</strong>, such that volume of container should be greater than zero in between and at starting and ending time of maximum raise.</br>
To simpify the task lets create another list/array <strong>Change_in_C2</strong>.
<pre>
Change_in_C2<sub>0</sub> = 0
for each i from 1 to N
Change_in_C2<sub>i</sub> = Vol_in_C2<sub>i</sub> - Vol_in_C2<sub>i-1</sub>
</pre>
Now to find the maximum raise in <strong>C2</strong> we need to find a Continues Subset of <strong>Change_in_C2</strong> whose sum is maximum possible and <strong>Vol_in_C2</strong> should be greater than 0, in the corresponding interval.
Sum of Maximum continues subset can be found with time complexity of O(n<sup>2</sup>), which takes lot of time. Instead we may find the same in time complexity of O(n) with the following algorithm, which is similar to <a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem"> Kadane's Algorithm</a>.
<pre>
in_the_fesible_interval = 1
max_gopalency = 0
max_sum_here = 0

for each i from 1 to N

//if not in the fesible interval
if Vol_in_C2<sub>i</sub> equals 0
in_fesible_interval = 0
continue the loop

// entering the fesible interval from non fesible interval
if in_fesible_interval equals 0
in_fesible_interval = 1
max_sum_here = 0 //assume that first number is smallest

// if alreday in the fesible interval
else
max_sum_here = max (0, max_sum_here + Change_in_C2<sub>i</sub>)

// keep track on maximum max_sum_here
max_gopalency = max (max_sum_here, max_gopalency)

return max_gopalency
</pre>

I thought the question given in the contest is sufficient to explain the problem, but many participents found it difficult to understand. I am extremely sorry for keeping the question in terrible way. I tried my best to explain all confusions in the comment section of the problem.
``````