Photoluminescence Math, Machines, and Music

You are given a set \(\mathbf{r}\) representing the elevation map of a linear array, consisting of bars with unit width, with size \(N\). Compute how much water it can trap after raining.

Constraints:

\(1\)\(\;\leq\;\)\(N\)\(\;\leq\;\)\(3\)\(\,\cdot\,\)\(1\)\(0 \vphantom{1 0}^{4}\)\(;\,\)

\(0\)\(\;\leq\;\)\(\mathbf{r} \vphantom{ \mathbf{r}}_{\left[n\right]}\)\(\;\leq\;\)\(1\)\(0 \vphantom{1 0}^{5}\)\(\;\mathtt{for}\;\)\(n\)\(\;=\;\)\(1\)\(,\,\)\(\,\dotsc\,\)\(,\,\)\(N\)\(;\,\)

For brevity, for two lists \(\mathbf{u}\)\(,\,\)\(\mathbf{v}\) we say \(\mathbf{u}\)\(\;<\;\)\(\mathbf{v}\) if \(\mathbf{u} \vphantom{ \mathbf{u}}_{\left[m\right]}\)\(\;<\;\)\(\mathbf{v} \vphantom{ \mathbf{v}}_{\left[n\right]}\) for each \(n\); and we similarly compare a scalar \(\alpha\) with a list \(\mathbf{v}\). Also \(\left\langle\vphantom{\mathbf{u} ,\, \mathbf{v}}\right.\)\(\mathbf{u}\)\(,\,\)\(\mathbf{v}\)\(\left.\vphantom{\mathbf{u} ,\, \mathbf{v}}\right\rangle\) is a concatenated list, with \(\mathbf{u}\)\(,\,\)\(\mathbf{v}\) understood to be flattened; and we similarly concatenate a scalar \(\alpha\) to a list \(\mathbf{v}\). We say a list to be increasing, if its components are increasing with respect to the numbered order; and we similarly say a list to be decreasing.

Suppose \(\psi\)\(\left[\vphantom{\mathbf{v}}\right.\)\(\mathbf{v}\)\(\left.\vphantom{\mathbf{v}}\right]\) gives the amount of rainwater trapped. Let \(M\) be the water level; then \(\psi\)\(\left[\vphantom{\mathbf{v}}\right.\)\(\mathbf{v}\)\(\left.\vphantom{\mathbf{v}}\right]\) may be found as \(\varphi\)\(\left[\vphantom{M ,\, \mathbf{v}}\right.\)\(M\)\(,\,\)\(\mathbf{v}\)\(\left.\vphantom{M ,\, \mathbf{v}}\right]\), by summing the water from the bar to the level in each grid. But how to find \(M\)?

If \(\mathbf{x}\)\(\;=\;\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right\rangle\) with \(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\) increasing, then we may remove u without affecting the result; similar is the decreasing case. this is to say:

Left_high:

\(\;\mathtt{if}\;\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\)\(\,\mathsf{increasing}\,\)\(,\,\)\(\;\mathtt{then}\;\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right]\)\(\;=\;\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right]\)\(;\,\)

Right_high:

\(\;\mathtt{if}\;\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{u}}\right\rangle\)\(\,\mathsf{decreasing}\,\)\(,\,\)\(\;\mathtt{then}\;\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right]\)\(\;=\;\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right]\)\(;\,\)

Or if \(\mathbf{x}\)\(\;=\;\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right\rangle\) with \(\alpha\)\(\;>\;\)\(\mathbf{v}\), then we may break \(\left\langle\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right\rangle\) from \(\left\langle\vphantom{\alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{u}}\right\rangle\), and add the respective answers; similar is the decreasing case. this is to say:

Left_low:

\(\;\mathtt{if}\;\)\(\alpha\)\(\;>\;\)\(\mathbf{v}\)\(,\,\)\(\;\mathtt{then}\;\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{v} ,\, \alpha ,\, \mathbf{u}\right\rangle}\right]\)\(\;=\;\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{v} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{v} ,\, \alpha\right\rangle}\right]\)\(\,+\,\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right]\)\(\;=\;\)\(\varphi\)\(\left[\vphantom{\alpha ,\, \left\langle\alpha ,\, \mathbf{v} ,\, \alpha\right\rangle}\right.\)\(\alpha\)\(,\,\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\alpha ,\, \mathbf{v} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\alpha ,\, \left\langle\alpha ,\, \mathbf{v} ,\, \alpha\right\rangle}\right]\)\(\,+\,\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(\left.\vphantom{\alpha ,\, \mathbf{u}}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{u}\right\rangle}\right]\)\(;\,\)

Right_low:

\(\;\mathtt{if}\;\)\(\alpha\)\(\;>\;\)\(\mathbf{u}\)\(,\,\)\(\;\mathtt{then}\;\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha ,\, \mathbf{u} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right]\)\(\;=\;\)\(\psi\)\(\left[\vphantom{\left\langle\alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u} ,\, \alpha}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\alpha ,\, \mathbf{u} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right]\)\(\,+\,\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right]\)\(\;=\;\)\(\varphi\)\(\left[\vphantom{\alpha ,\, \left\langle\alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right.\)\(\alpha\)\(,\,\)\(\left\langle\vphantom{\alpha ,\, \mathbf{u} ,\, \alpha}\right.\)\(\alpha\)\(,\,\)\(\mathbf{u}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\alpha ,\, \mathbf{u} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\alpha ,\, \left\langle\alpha ,\, \mathbf{u} ,\, \alpha\right\rangle}\right]\)\(\,+\,\)\(\psi\)\(\left[\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right.\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\)\(\left.\vphantom{\left\langle\mathbf{v} ,\, \alpha\right\rangle}\right]\)\(;\,\)

We begin by examining \(\mathbf{x}\) from the left end. Cases LeftHigh and LeftLow are mutually exclusive, and the situation that neighboring components are equal doesn’t matter. But there is a remaining case, that \(\mathbf{x}\)\(\;=\;\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(\left.\vphantom{\alpha ,\, \mathbf{v}}\right\rangle\) with \(\alpha\)\(\;>\;\)\(\mathbf{v}\) . When this happens, we turn to the right end to examine cases RightHigh and RightLow which is analogous.

A moment of thought reveals that the overall time complexity is \(\mathscr{O}\)\(\left[\vphantom{N}\right.\)\(N\)\(\left.\vphantom{N}\right]\) . Suppose we are examining \(\mathbf{x}\)\(\;=\;\)\(\left\langle\vphantom{\mathbf{v} ,\, \alpha}\right.\)\(\mathbf{v}\)\(,\,\)\(\alpha\)\(\left.\vphantom{\mathbf{v} ,\, \alpha}\right\rangle\) from the left end; when \(\mathbf{v}\) is removed in case LeftHigh, it takes \(\mathscr{O}\)\(\left[\vphantom{\,\mathrm{size}\, \mathbf{v}}\right.\)\(\,\mathrm{size}\,\)\(\mathbf{v}\)\(\left.\vphantom{\,\mathrm{size}\, \mathbf{v}}\right]\). Or else when \(\mathbf{x}\)\(\;=\;\)\(\left\langle\vphantom{\alpha ,\, \mathbf{v}}\right.\)\(\alpha\)\(,\,\)\(\mathbf{v}\)\(\left.\vphantom{\alpha ,\, \mathbf{v}}\right\rangle\) with \(\alpha\)\(\;>\;\)\(\mathbf{v}\), it takes \(\mathscr{O}\)\(\left[\vphantom{\,\mathrm{size}\, \mathbf{x}}\right.\)\(\,\mathrm{size}\,\)\(\mathbf{x}\)\(\left.\vphantom{\,\mathrm{size}\, \mathbf{x}}\right]\), but RightHigh or RightLow must happen; component \(\alpha\) won’t be examined again. Hence any component has to be examined twice at most.

The validity of algorithm appears obvious; it would be able to write a proof by a generalized induction on the length of the list, according to the steps LeftHigh, LeftLow, RightHigh, and RightLow displayed above.

❧ August 14, 2021