Problem: tree_training (2020 finals)

The great Canadian log drive is [coming to an end](https://www.youtube.com/watch?v=7AheBqBk0iQ&feature=youtu.be&t=1634), for this season at least. Next year, a new crop of log driving hopefuls will compete for their own spot on the river. 

As every Canadian knows, to stay afloat in the forestry industry's competitive job market, you need to familiarize yourself with all kinds of trees. Hoping to land her dream log driving job, Louise was researching online when she stumbled upon an article about [*binary search trees*](https://en.wikipedia.org/wiki/Binary_search_tree) (BSTs). Determined to become a true expert on all there is to know about trees, she decided to continue reading.

In case you're unfamiliar, Louise learned that a BST is a data structure holding nodes that each store a key (in this case, a non-negative integer). A BST may be empty (that is, holding no nodes), or otherwise consists of a root node that is optionally connected by edges to left and/or right child nodes (which are themselves each the root nodes of "subtree" BSTs, recursively defined in the same fashion). For each node, if its key is \(k\), all keys in its **left** child's subtree (if any) must be **less than or equal** to \(k\), while all keys in its **right** child's subtree (if any) must be **strictly greater** than \(k\). The **height** of a non-empty BST is defined as the **number of edges on the longest path from its root node to any other node** (or 0 if there are no other nodes).

In practice, BSTs start out empty and are constructed by having nodes inserted into them, one by one. When inserting a new key \(k\) into an existing BST, one compares the root node with \(k\):

- If the root node doesn't exist, then a node with key \(k\) is created in its place and the insertion is complete.
- Otherwise, if \(k\) is less than or equal to the root node's key, then \(k\) is recursively inserted into the left subtree.
- Otherwise, \(k\) must be greater than the root node's key, in which case it is recursively inserted into the right subtree.

The following diagrams illustrate the insertion of keys 3, 6, 0, 5, 0, and 3 into an initially empty BST, ending up with a height of 2:

{{PHOTO_ID:493376864970463}}

Intrigued, Louise borrowed a data structures textbook from her local library. Upon flipping to the chapter on BSTs, she came upon the following exercise:

> Given a length-\(N\) string \(S\) in which each character is either `"0"` or `"*"`, please answer the following question for each of the \(N*(N+1)/2\) non-empty substrings of \(S\).

> For a given substring of length \(x\), choose a sequence \(K_{1..x}\) of integer keys. If the substring's \(i\)th character is `"0"`, then \(K_i = 0\). Otherwise, if it's `"*"`, then \(K_i\) may be chosen to be any positive integer. Suppose the chosen sequence was inserted into an initially empty BST, in order from \(K_1\) to \(K_x\). What is the minimum possible height of the resulting BST?

For example, if \(S\) = `"0**0*0**"`, then one of the 8*9/2 = 36 substrings for which the above question must be answered is `"**0*0*"`. For this substring, one possible choice of \(K_{1..6}\) would be \([3, 6, 0, 5, 0, 3]\), yielding a BST of height 2 (as illustrated above). This is the minimum height that a BST could have for any possible choice of \(K_{1..6}\) for this substring, meaning that 2 is the answer to the question for this substring.

Louise would like your help with computing the sum of the answers to all \(N*(N+1)/2\) of these questions. As this sum may be large, you should only compute its value modulo 1,000,000,007. Please help her complete this exercise — the fate of her log driving career rests in your hands!

# Constraints

\(1 \le T \le 85\)
\(1 \le N \le 1,000,000\)
\(S_i \in \{``0", ``*"\}\)

The sum of \(N\) across all exercises is at most 10,000,000.


# Input

Input begins with an integer \(T\), the number of exercises. For each exercise there is a single line consisting of the string \(S_{1..N}\) as specified above.


# Output

For each exercise, print a line containing *"Case #i: "*, followed by a single integer, the sum of the answers to all \(N*(N+1)/2\) questions, modulo 1,000,000,007.



# Explanation of Sample

In the first exercise, the 3 substrings present are `"*"`, `"0"`, and `"*0"`. The first two each result in a BST with just 1 node (and therefore height 0), while the last one yields a BST with 2 nodes (and therefore height 1). The final answer is therefore \(0 + 0 + 1 = 1\).

In the second exercise, there are 3 `"*"` substrings, 2 `"**"` substrings, and 1 `"***"` substring. The minimum height of a BST yielded by this last substring is 1 (for example, if \([1, 1, 2]\) is chosen for \(K\)). The final answer is therefore \(0 + 0 + 0 + 1 + 1 + 1 = 3\).

The third exercise is similar to the second, except that the substring `"000"` must yield a BST with height 2, resulting in an answer of \(0 + 0 + 0 + 1 + 1 + 2 = 4\).

In the fourth exercise, several of the substrings present are explained below:

- `"*0*"` can yield a BST with height 1 (for example, with \(K = [1, 0, 2]\))
- `"0**"` can yield a BST with height 2 (for example, with \(K = [0, 1, 1]\))
- `"*0**"` can yield a BST with height 2 (for example, with \(K = [1, 0, 1, 2]\))


Sample input:
7
*0
***
000
*0**
0**0*0**
********0*0*****00*00********0
*000000*0000*0000000000**00**0


Sample output:
Case #1: 1
Case #2: 3
Case #3: 4
Case #4: 8
Case #5: 47
Case #6: 1519
Case #7: 3691


Solution: Let \(E(Z, S, H)\) be the maximum number of `*`s which can fit alongside \(Z\) `0`s, with \(S\) `*`s before the first `0`, in a BST of height at most \(H\) (only relevant for \(Z > 0\)). To compute this in \(O(1)\) time, we should arrange as many `*`s as possible as ancestors of the first `0` (\(\min(S, H-Z+1)\) of them). We can then compute the maximum total number of nodes in a BST of height \(H\) (\(2^{H+1} - 1\)), subtract the number of nodes in the first `0`'s subtree, and potentially add back the number of nodes in the first `0`'s right subtree (if it's possible to get any `*`s there.

Let \(F(P, Z, S)\) be the minimum BST height for \(P\) `*`s and \(Z\) `0`s, with \(S\) `*`s before the first `0` (again only relevant for \(Z > 0\)). This can be computed in \(O(log(P + Z))\) by simply binary searching for the minimum height and evaluating \(E(Z, S, H)\).

Finally, let \(G(P)\) be the minimum BST height for \(P\) `*`s and no `0`s. This can similarly be computed in \(O(log(P))\) using binary search or simple math.

Now, letting \(Z\) be the number of `0`s present in any given substring, we'll we'll separately consider 3 categories of \(Z\) values and add their results up.

**Category 1:** \(Z = 0\)

Let \(C_P\) be the number of substrings with \(P\) `*`s and no `0`s. We can compute \(C_{1..N}\) in \(O(N)\) time relatively simply, by iterating through the string and dividing it into intervals of consecutive `*`s (noting that an interval of \(P\) `*`s should increase `C_P` by 1, `C_{P-1}` by 2, and so on, with `C_1` increased by `P`).

After that, we only need to add up \(C_P * G(P)\) for each \(P\), taking \(O(N log(N))\) (or as little as \(O(N)\)) time.
  
**Category 2:** \(1 \le Z \le 20\)

The significance of the cutoff of \(20\) (\(\lceil log(N) \rceil\)) is explained in Category 3 below.

For now, for each such value of \(Z\), we can sweep through the string and find the \(O(N)\) possible intervals of `0`s which it could span. Each such interval may be described by the triple \((L, M, R)\), such that there are \(L\) `*`s just left of the leftmost `0`, \(M\) `*`s in total between the leftmost and rightmost `0`s, and \(R\) `*`s just right of the rightmost `0`.

For each interval, we'll consider each possible number \(S\) of `*`s left of the leftmost 0 to use (such that \(0 \le S \le L\)). Note that this amounts to \(O(N)\) \(S\) values considered across all intervals for any given \(Z\) value. For each \(S\), we need to include \(F(P, Z, S)\) for each \(P\) such that \(S+M \le P \le S+M+R\). This amounts to \(O(N^2)\) \((P, Z, S)\) triples in total, which is too many to individually consider. However, \(F(P, Z, S)\) for fixed values of \(Z\) and \(S\) is monotonic over \(P\) and only takes on \(O(log(N))\) distinct values (dictated by \(E(Z, S, H)\) for \(0 \le H \le \lceil log(N) \rceil\)). These computations can therefore be done in \(O(log(N))\) time for each \(S\). The total time complexity is then \(O(N log(N))\) for each value of \(Z\), and \(O(N log^2(N))\) across all of Category 2.

**Category 3:** \(Z > 20\)

For each such \(Z\), there are enough `0`s that the BST's height is entirely dictated by them, no matter how many `*`s there are. In particular, when \(Z > 20\), \(F(P, Z, S)\) equals \(Z-1\) if \(S = 0\), or otherwise equals \(Z\).

To arrive at the sum of these \(F\) evaluations across all strings with more than 20 `0`s, we'll independently count the "contribution" of each `0` in the string. We'll begin by adding on the total number of intervals containing it (easily computable in \(O(1)\) time), and then subtracting the number of intervals containing it which have no more than 20 `0`s (doable in \(O(log(N))\) time by considering each possible leftmost `0` in such intervals (of which there are at most 21 options). Finally, we'll subtract the number of intervals which begin with it and have more than 20 `0`s (to account for cases in which \(F(P, Z, S)\) equals \(Z-1\) rather than \(Z\)), which is also easily computable in \(O(1)\) time. In total, then, Category 3 can be handled in \(O(N log(N))\).

Putting all of the above together, the time complexity of this solution comes out to \(O(N log^2(N))\).


Code: // Tree Training
// 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 <set>
#include <unordered_map>
#include <unordered_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 MOD 1000000007
#define LIM 1000005
#define LOG 20

int N, M;
char S[LIM];
int Z[LIM];
int DS[LIM];

int TreeCnt(int h) // # of nodes in binary tree with height h
{
  return((1 << (h + 1)) - 1);
}

// E(z, s, h) = max. *s which can fit alongside z 0s (with s *s before the 1st 0) in a tree of height at most h (only relevant for z > 0)
int E(int z, int s, int h)
{
  if (h >= LOG)
    return(N);
  int left = min(s, h + 1 - z); // *s at root and along leftmost branch
  int cnt = TreeCnt(h); // full tree
  cnt -= TreeCnt(h - left); // subtract subtree of 1st 0
  if (cnt >= s)
    cnt += TreeCnt(h - left - 1); // add back right subtree of 1st 0
  return(cnt);
}

// F(p, z, s) = min. tree height for p *s, z 0s, and s *s before 1st 0 (s ignored if z = 0)
int F(int p, int z, int s)
{
  int r1 = z ? (s > 0 ? z : z - 1) : 0;
  int r2 = max(r1, min(LOG, p + z - 1));
  while (r1 < r2)
  {
    int m = (r1 + r2) >> 1;
    if ((z ? E(z, s, m) : TreeCnt(m)) >= p)
      r2 = m;
    else
      r1 = m + 1;
  }
  return(r1);
}

int ProcessCase()
{
  int i, j, z;
  // input
  scanf("%s", &S);
  N = strlen(S);
  // find 0s
  M = 0;
  Z[M++] = -1;
  Fox(i, N)
    if (S[i] == '0')
      Z[M++] = i;
  Z[M++] = N;
  // A) z = 0
  int ans = 0;
  int v = 0, s = 0;
  Fill(DS, 0);
  Fox1(i, M - 1)
  {
    int x = Z[i] - Z[i - 1] - 1; // sequence of x *s before ith 0
    v += x;
    DS[2]--, DS[x + 2]++;
  }
  Fox1(i, N)
  {
    s += DS[i];
    v += s;
    ans = (ans + (LL)v * F(i, 0, 0)) % MOD;
  }
  // B) 1 <= z <= LOG
  Fox1(z, LOG) // z 0s
  {
    Fox1(i, M - z - 1) // ith 0 as the leftmost 0
    {
      int j = i + z - 1;
      int c1 = Z[i] - Z[i - 1] - 1; // c1 *s to the left
      int c2 = Z[j + 1] - Z[j] - 1; // c2 *s to the right
      int m = Z[j] - Z[i] + 1 - z; // m *s in between
      Fox(s, c1 + 1) // use s *s to the left
      {
        int p = s + m, mp = s + m + c2;
        int h = F(p, z, s);
        while (p <= mp)
        {
          int p2 = min(mp, E(z, s, h));
          ans = (ans + (LL)(p2 - p + 1) * h) % MOD;
          p = p2 + 1, h++;
        }
      }
    }
  }
  // C) z > LOG
  Fox1(i, M - 2) // count contribution of the ith 0
  {
    // add # of intervals containing it
    ans = (ans + (LL)(Z[i] + 1) * (N - Z[i])) % MOD;
    // subtract # of intervals containing it, with <= LOG 0s
    FoxI(j, max(1, i - LOG + 1), i) // jth 0 as the leftmost 0
    {
      int k = min(M - 1, j + LOG); // first disallowed 0
      int c = (LL)(Z[j] - Z[j - 1]) * (Z[k] - Z[i]) % MOD;
      ans = (ans + MOD - c) % MOD;
    }
    // subtract # of intervals starting with it, with > LOG 0s
    int j = i + LOG;
    if (j < M)
      ans = (ans + MOD - (N - Z[j])) % MOD;
  }
  return(ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}