Problem: pond_precipitation (2020 finals)

Cherry the turtle lives in a long, narrow pond. When cross-sectionally viewed from the side, the floor of the pond can be divided into \(N\) columns, each flat and 1 metre wide. The \(i\)th column from the left is at a depth of \(D_i\) metres below ground level, and all \(N\) column depths are distinct. The pond is surrounded by dirt (at ground level), just to the left of column 1 and the right of column \(N\). Cherry loves to sit on the floor in the leftmost column and bask as much as possible — but only when it's dry. Fortunately for her, the pond is initially devoid of water.

For example, if \(D = [3, 5, 4, 1, 2]\), the pond would look as follows (with Cherry's position indicated in green):

{{PHOTO_ID:311416436611683}}

Unusually enormous drops of rainwater are about to begin falling into the pond, one by one, each onto a random column (drawn uniformly at random from the set of \(N\) columns). Each drop contains 1 cross-sectional square metre of water, and obeys the following process:

  1. It falls until it hits a flat *surface*. This surface consists of the highest (least deep) point in its column (which might be either the floor of the pond itself or an existing layer of water atop it), as well as all contiguous equally-deep points to the left and right of it.
  2. If that surface is immediately surrounded by any deeper columns to its left and/or right, then the drop's water flows down onto one of them. If there's only one such adjacent deeper column, then the drop flows onto that one. If the columns to the left and right are both deeper than the surface (note that this can only occur if the surface consists of a single column), then the drop's water all flows to the *left* one. Either way, once the drop flows into a different column, the process repeats back from Step 1.
  3. Otherwise, the drop's 1 cross-sectional square metre of water spreads itself out evenly across the entire surface it landed on (which will never cause that surface to "overflow" by becoming strictly higher than the columns to its left or right).

Cherry will be forced to stop basking as soon as a non-zero amount of water comes to rest atop column 1. She doesn't mind if raindrops fall directly on column 1 but then immediately flow away from it.

For example, if a raindrop were to fall in column 4 of the above pond, it would flow to the left (onto column 3), and then flow left again to settle in column 2:

{{PHOTO_ID:3533638723394837}}

If a raindrop then fell in column 1, it would flow to the right and spread itself out over the surface spanning columns 2 and 3:

{{PHOTO_ID:299743861289784}}

If a raindrop then fell in column 5, it would remain there:

{{PHOTO_ID:1094784447639382}}

Another raindrop falling in column 5 (or *any* column) would then yield the following state:

{{PHOTO_ID:747829032476688}}

And one more raindrop falling in any column would yield the following state (forcing Cherry to stop basking due to column 1 becoming submerged in water):

{{PHOTO_ID:477696676534167}}

Determine the expected number of drops which will fall before Cherry is forced to stop basking. This will always occur after a finite number of drops have fallen, and before any water overflows the pond.

Let this expected number of drops be represented as a quotient of integers \(p/q\) in lowest terms. Output the value of this quotient modulo 1,000,000,007 — in other words, output the unique integer \(x\) such that \(0 \le x \lt 1,000,000,007\) and \(p \equiv x*q\text{ }(\text{modulo }1,000,000,007)\).


# Constraints

\(1 \le T \le 50\)
\(1 \le N \le 30\)
\(1 \le D_i \le 30\)
\(D_{1..N}\) are distinct

The sum of \(N\) across all ponds is at most 1000.


# Input

Input begins with an integer \(T\), the number of ponds. For each pond, there are 2 lines. The first line contains a single integer \(N\). The second line contains the \(N\) space-separated integers \(D_{1..N}\).


# Output

For the \(i\)th pond, print a line containing *"Case #i: "*, followed by a single integer, the expected number of drops which will fall before the leftmost column becomes covered in water, expressed as a quotient of integers modulo 1,000,000,007.


# Explanation of Sample

The first pond initially looks as follows:

{{PHOTO_ID:1173260263089522}}

If the first raindrop falls in column 1, it will settle there, and if it falls in column 2 instead, it will flow into column 1. Either way, Cherry's position will be submerged and she'll be forced to stop basking.

The second pond initially looks as follows:

{{PHOTO_ID:127321889008596}}

The first raindrop will always settle in column 2, leaving Cherry uninterrupted. However, the second raindrop will then always land on the surface spanning both columns, filling both up to a depth of 0.5 metres below ground level and thus forcing Cherry to stop basking.

The third pond only has a single column, and Cherry will need to stop basking as soon as the first raindrop falls in it.

The fourth pond may end up in various states depending on which columns the raindrops fall in. If the first drop falls in either column 1 or 2, then it will immediately settle in column 1, while if it falls in column 3, it will remain there and it will take a second drop to force Cherry to stop basking. The answer is therefore \(\frac{2}{3} 1 + \frac{1}{3} 2 = \frac{4}{3}\). \(4 \equiv 333,333,337 * 3\text{ }(\text{modulo }1,000,000,007)\), meaning that \(333,333,337\) should be outputted.


Sample input:
8
2
2 1
2
1 2
1
30
3
3 1 2
3
1 3 2
5
3 5 4 1 2
8
3 7 5 8 2 6 1 4
15
11 29 12 10 13 28 15 6 5 25 17 8 9 3 24


Sample output:
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 333333337
Case #5: 4
Case #6: 772800010
Case #7: 600238862
Case #8: 777291572


Solution: Let \(C_i\) be the maximum number of raindrops which can fall in the first \(i\) columns without causing any water to settle atop column 1. We can compute \(C_{1..N}\) in \(O(N)\) time by iterating over the columns from left to right, looking for each new highest (least deep) column, and considering filling the columns before it (back to the previous highest column) with water up to the depth of that previous highest column.

Then, let \(\textit{DP}_{i,d}\) be the number of different ways for \(d\) raindrops to fall in the first \(i\) columns without causing any water to settle atop column 1. \(\textit{DP}_{0,0}\) = 1, with the remaining values computable using dynamic programming as follows. We can consider all triples \((i, d, d')\) in increasing order of \(i\) such that \(d\) drops have fallen in the first \(i\) columns (such that \(d \le C_i\)) and \(d'\) drops will fall in column \(i + 1\) (such that \(d + d' \le C_{i+1}\)). This allows us to increase \(\textit{DP}_{i+1,d+d'}\) by \(\textit{DP}_{i,d} * {d+d' \choose d'}\), given that the new \(d'\) drops may be mixed in anywhere amongst the total \(d+d'\) drops. Overall, this process takes \(O(N * \sum(D_{1..N})^2)\) time.

Finally, let \(S_d\) be the probability that, once \(d\) drops have fallen, no water has yet settled atop column 1. Note that \(S_d = \textit{DP}_{N,d} / N^i\). The answer may then be computed as \(\sum(S_{0..C_N})\).


Code: // Pond Precipitation
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x)
{
  char c, r = 0, n = 0;
  x = 0;
  for (;;)
  {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else
      if ((c >= '0') && (c <= '9'))
        x = x * 10 + c - '0', r = 1;
      else
        if (r)
          break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 32
#define LIM2 500
#define MOD 1000000007

int N;
int D[LIM], C[LIM];
int ch[LIM2][LIM2];
int dyn[LIM][LIM2];

int Exp(int a, int b)
{
  LL p = a, v = 1;
  while (b)
  {
    if (b & 1)
      v = v * p % MOD;
    p = p * p % MOD;
    b >>= 1;
  }
  return(v);
}

void Add(int& a, int b)
{
  a = (a + b) % MOD;
}

int Prod(int a, int b)
{
  return((LL)a * b % MOD);
}

int Div(int a, int b)
{
  return Prod(a, Exp(b, MOD - 2));
}

int ProcessCase()
{
  int i, j, k;
  // input
  Read(N);
  Fox(i, N)
    Read(D[i]);
  // compute max prefix capacities
  int p = 0, s = 0;
  Fox(i, N + 1)
  {
    if (i == N || D[i] < D[p])
    {
      FoxI(j, p, i - 1)
        s += D[j] - D[p];
      FoxI(j, p + (p ? 1 : 0), i)
        C[j] = s;
      p = i;
    }
  }
  // DP
  Fill(dyn, 0);
  dyn[0][0] = 1;
  Fox(i, N)
  {
    Fox(j, (i ? C[i - 1] : 0) + 1)
    {
      Fox(k, C[i] - j + 1)
        Add(dyn[i + 1][j + k], Prod(dyn[i][j], ch[j + k][k]));
    }
  }
  // compute answer
  int ans = 0;
  Fox(i, s + 1)
    Add(ans, Div(dyn[N][i], Exp(N, i)));
  return(ans);
}

int main()
{
  int T, t;
  int i, j;
  // precompute choose table
  ch[0][0] = 1;
  Fox1(i, LIM2 - 1)
  {
    Fox(j, i + 1)
    {
      ch[i][j] = ch[i - 1][j];
      if (j)
        Add(ch[i][j], ch[i - 1][j - 1]);
    }
  }
  // testcase loop
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}