0
$\begingroup$

Over winter break, I have been working on a few programming questions and I came across this one, which has me a bit stumped:

As you ponder sneaky strategies for assisting with the great rabbit escape, you realize that you have an opportunity to fool Professor Boolean's guards into thinking there are fewer rabbits total than there actually are.

By cleverly lining up the rabbits of different heights, you can obscure the sudden departure of some of the captives.

Beta Rabbits statisticians have asked you for some numerical analysis of how this could be done so that they can explore the best options.

Luckily, every rabbit has a slightly different height, and the guards are lazy and few in number. Only one guard is stationed at each end of the rabbit line-up as they survey their captive population. With a bit of misinformation added to the facility roster, you can make the guards think there are different numbers of rabbits in holding.

To help plan this caper you need to calculate how many ways the rabbits can be lined up such that a viewer on one end sees $x$ rabbits, and a viewer on the other end sees $y$ rabbits, because some taller rabbits block the view of the shorter ones.

For example, if the rabbits were arranged in line with heights $30$ cm, $10$ cm, $50$ cm, $40$ cm, and then $20$ cm, a guard looking from the left side would see $2$ rabbits ($30$ and $50$ cm) while a guard looking from the right side would see $3$ rabbits ($20$, $40$ and $50$ cm).

Write a method answer $(x,y,n)$ which returns the number of possible ways to arrange $n$ rabbits of unique heights along an east to west line, so that only $x$ are visible from the west, and only $y$ are visible from the east. The return value must be a string representing the number in base $10$.

If there is no possible arrangement, return "$0$".

The number of rabbits (n) will be as small as $3$ or as large as $40$

The viewable rabbits from either side ($x$ and $y$) will be as small as $1$ and as large as the total number of rabbits ($n$) $4$.

I know this questions boils down to a combinatorics problem. The tallest rabbit should be somewhere so that the problem is broken down into two subproblems. I figure that it is the number of permutations of rabbits that satisfy the necessary conditions, but I am not sure how to generalize that. Any help would be great! Thanks

$\endgroup$
1
$\begingroup$

You can first solve the simpler problem of looking only from one side, with k rabbits of unique height, let's call $T(k, x)$ the number of ways to arrange the k rabbits so that seeing from one side x of them are visible.

The we ask where to place the tallest rabbit. There are at most n places to place it, so you can enumerate by a program. Suppose you place it at location t. Then there are $t-1$ rabbits on the left and $n-t-1$ on the right. There are $\binom{n}{t-1}$ indistinguishable ways to distribute the rabbits on the two sides. So for this placement of the tallest rabbits, there are \begin{align*} \binom{n}{t-1} T(t-1, x-1) \end{align*} ways to place the rabbits as required.

Now to compute $T(k, x)$ I'll give you a hint, if you place the tallest rabbit among the k rabbits at location r, then you reduce the problem to $T(r-1, x-1)$. This leads to an algorithm of complexity $O(kx)$

$\endgroup$
  • $\begingroup$ but wouldn't this calculate the configuration for only 1 side? What about the other? $\endgroup$ – Mayur Kulkarni Sep 2 '16 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.