Editorials-GPNY
PROBLEM LINK:
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.
If you feel difficult to under stand the above algorithm please read about Kadane’s Algorithm and go through the editorial once again.