Intermission, the Sequel

We already know how to solve the second half of this problem using simple Dynamic Programming. If we can compute, for a given number of columns $C$ , $P(x)$ for all $x \in [0, C]$ , where $P(x)$ is the probability that $x$ people in a given row are 'forced', then we can easily compute the probability that at most 10% of customers are 'forced' across 25 rows. For details on this part of the solution, read my solution of the previous problem.

---

The challenge, thus, in this problem, is to compute $P(x)$ for arbitrary $x$ . There is no simple closed form for this value, and, meta-gaming a bit, since we can see that the answer is $47$ , solutions which are exponential in the number of columns are not feasible! Below, I will present a way to pre-compute all $P(x)$ for a given $C$ , in time $O(C^3)$ , which is tractible.

---

Observation 1: The number of 'forced' in a given row is equal to $C - k - q$ , where $C$ is the number of columns in the row, $q$ is the number of givens, and $k$ is the maximum length of any segment in the row of consecutive non-givens.

It's simple to show this is the case.

• The 'forced' in a given row are uniquely determined by the directions in which all givens proceed. If a given proceeds to the left, all non-givens between him and the left aisle are 'forced', regardless of what other givens do. Likewise, towards the right.
• Thus, the non-givens, which are not forced, must form a continuous segment between a given going left, and a given going right, with all givens past them going in the same respective directions. There cannot be a discontinuous segment of non-givens which are not forced, because they must, by definition, be split in the middle by a given, which must force one side of them to stand up.
• The customers are 'really smart', and force the fewest number of people to stand. Thus, the largest, or one of the largest, continuous segments of non-givens will be left to sit, as minimizing the count of the 'forced' is tantamount to maximizing the number of non-forced. In the cases where multiple segments tie for the largest, it is not defined which will be forced to stand, but this does not matter, as the statistical outcome is the same.

---

Now, let's define a function, $P(N, k, q)$ . We'll define this function to represent the probability that:

• When $N$ customers are in a row,
• There is at least one segment, of size $\geq k$ , of consecutive non-givens,
• AND at most $q$ of the customers in the row are givens.

It turns out this function is actually relatively simple to define recursively. If you start changing the $\geq$ , $\leq$ semantics in the restrictions, or try to get exact requirements, you'll find the formula gets quite ugly. There are numerous nuanced base cases for this $P(N, k, q)$ function which we'll gloss over here - if you're curious, look at the code sample at the end of the solution. The recursive definition for all other cases is thus:

$P(N, k, q) = \frac{1}{100} P(N-1, k, q-1) + \frac{99}{100} P(N-1, k, q) + (P(N-k-1, 0, q-1) - P(N-k-1, k, q-1)) \left( \frac{1}{100} \right) \left( \frac{99}{100} \right) ^ k$

Broken down into English, we're adding up:

• The probability that the $N$ -th customer is a given, times the probability that the previous $N-1$ customers yielded at least one segment of $k$ or more continuous non-givens, as well as at most $q-1$ givens,

• the probability that the $N$ -th customer is not a given, times the probability that the previous $N-1$ customers yielded at least one segment of $k$ or more continuous non-givens, as well as at most $q$ givens,

• the probability that this particular row yielded a continuous segment of $k$ or more non-givens only at the very end, with at most $q$ givens elsewhere in the row, expressed as:

• the probability that, for the first $N-k-1$ customers, the longest contiguous segment of givens had length at most $k-1$ , and after those $N-k-1$ customers, we find a single given, and then $k$ non-givens.

Meaningful values for $P(N, k, q)$ occur in $0 \leq k, q \leq k + q \leq N$ . For a given $C$ , this space of $(N, k, q)$ tuples has size $O(C^3)$ , and so all these values can be computed in $O(C^3)$ time. Additionally, following the exclusion principle, we can now easily compute the more useful function, $E(N, k, q)$ , which is the probability that, in a row of $N$ customers, the longest segment of contiguous non-givens has length exactly $k$ , and there are exactly $q$ givens in the row:

$E(N, k, 0) = P(N, k, 0) - P(N, k+1, 0)$

$E(N, k, q > 0) = (P(N, k, q) - P(N, k+1, q)) - (P(N, k, q-1) - P(N, k+1, q-1))$

Now, we're ready to compute the function we need for the last step of the problem: $P(x)$ , the probability that $x$ customers are 'forced' in an arbitrary row of length $C$ . To do this, first initialize all $P(x)$ to $0$ , then, loop over all $(k, q)$ tuples that satisfy the inequality $0 \leq k, q \leq k + q \leq C$ . Compute $E(C, k, q)$ for each tuple, and since $C - k - q$ customers in the row are forced, add that value to the running total for $P(C - k - q)$ .

When we're done, we'll have a fully defined $P(x)$ function, and we're ready to run the final dynamic programming step. Doing so for each possible $C$ incrementally will eventually yield:

$f(47) \approx 0.495232$

$f(48) \approx 0.514838$

Where $f(c)$ is the probability that, given $c$ columns of seats in the theater, more than 10% of customers will be 'forced'. Thus, since the function is, again, clearly increasing, we provide $\boxed {47}$ as our answer.

---

Here is the Java program I wrote to compute the answer. I like to use Guava and AutoValue, sadly, so if you don't, you won't be able to paste-and-run this as-is.