Algorithms

In some cities, the sewage system does not work properly and every time it rains, water accumulates on the streets and in between buildings, blocking traffic and causing distress.

You have an N number of buildings and an array with the height of every building.

You want to find out what is the maximum volume of water that would hypothetically accumulate after heavy rain, in between 2 buildings.

Input: N > 0 on the first line, array of N integer elements on the second line.

Output: integer positive X units of water.

Example: The following sequence of heights will generate the structure below:

Sequence: 1 2 1 5 2 4 1 0 1 2 6 4 5 2 3 4 1 2

The biggest block of water would contain 20 units of water.




<pre>using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace heavy_rain{
    class Program{
        static void Main(string[] args){
            System.IO.StreamReader sr;
            int n = 0, i = 0, result = int.MaxValue;
            int[] buildingHeights = null;
            try {
                sr = new System.IO.StreamReader(args[0]);
                String[] lines = new String[2];
                String line = null;
                while ((line = sr.ReadLine()) != null) {
                    lines[i++] = line;
                }
                n = int.Parse(lines[0]);
                buildingHeights = new int[n];
                String[] heights = lines[1].Split(' ');
                for(int j = 0; j < heights.Length; j++) {
                    buildingHeights[j] = int.Parse(heights[j]);
                }
                /* YOUR CODE HERE */
                Console.WriteLine(result);
            }
            catch (Exception e) {
                System.Diagnostics.Trace.WriteLine(e.Message);
            }
        }
    }
}

Before we start, my textbook declares lgn as base two. 

I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter? Below is a link of the equations. 

vmax = maximum allowed speed for the movement.
x0 = initial position.
xf = destination position.
v0 = initial speed.
vf = end speed (final).
ta = acceleration time from v0 to vmax.
da = distance to accelerate from v0 to vmax.
tf = braking time from vmax to vf.
df = braking distance from vmax to vf.
dist = total distance I want to move the motor xf-x0

LimitIterations = 1000
    ' Search the amount of time and distance we use to accelerate from v0 to vmax.
    ta = Abs((vmax - v0) / a)
    da = (v0 * ta) + (0.5 * a * ta * ta)
    ' Search the amount of time and distance we use to brake from vmax to vf.
    tf = Abs((vmax - vf) / a)
    df = (vf * tf) + (0.5 * a * tf * tf)
   
    ' If da and df are bigger than the distance to run...
    If (da + df > dist + 0.000000001) Then
      ' WRONG APPROACH STARTS HERE --->
      ' adapt the acceleration and braking distances to the distance we must run.
      DistTotal = xf - x0 - da - df
      RelAccDec = da / (da + df)
      dist_corr_acc = DistTotal * RelAccDec
      da = da + dist_corr_acc
      dist_corr_dec = DistTotal * (1 - RelAccDec)
      df = df + dist_corr_dec
      ' <---- WRONG APPROACH ENDS HERE

      ' **** See explanations under the code about the WRONG APPROACH.

      ' This is something that you

      ' Now that we know the correct distances it should be easy to find the needed time and therefore the reached vmax after the acceleration stage.
      taux = Sqr(da / (0.5 * a))  ' Normal formula that doesn't work when v0 > 0
      taux = (Sqr((2 * a * da) + (v0 * v0)) - v0) / a  ' Rare formula that nobody understands...
      vmax = v0 + (a * taux)  ' Easy way to calculate the vmax.

      ' Ugliest code in the world... this works, not always but mostly, but of course it is not the way to go...
      Do
        ' refresh the values (time, distance...) to find the maximum allowed speed for that movement vmax...
        ta = Abs((vmax - v0) / a)
        da = (v0 * ta) + (0.5 * a * ta * ta)
        tf = Abs((vmax - vf) / a)
        df = (vf * tf) + (0.5 * a * tf * tf)
        If (da + df > dist + 0.000000001) Then
          vmax = vmax - 1   ' Decrease the vmax till it works... 
          iterations = iterations + 1
          If (iterations > LimitIterations) Then
            ErrorID = 1
            Exit Do
          End If
        Else
          Exit Do
        End If
      Loop
    End If

// STAGE A
vp = v0 + (a0 * t0)  // Acceleration stage
vp = v1 + (a1 * t1)  // Brake stage
v0+(a0*t0) = v1+(a1*t1)  // vp = vp
t1=((v0-v1)+(a0*t0))/a1  // Get the t1 in terms of t0 (braking time in terms of accelerating time).  ==> Note v0 is the starting speed and v1 is the ending speed.

// STAGE B
d0 = (v00 * t0) + (0.5 * a0 * t0 * t0) // Distance while accelerating.
d1 = (v01 * t1) + (0.5 * a1 * t1 * t1) // Distance while braking.
D = (v00 * t0) + (0.5 * a0 * t0 * t0) + (v01 * t1) + (0.5 * a1 * t1 * t1)  // Total distance is the sum of both equations.

// At this point is only a matter of sorting the values to get the shape of the quadratic equation Ax^2 + Bx + C = 0

And solve the quadratic equation to get the positive value (as we are speaking of time).