Competitive programming in Haskell: Infinite 2D array, Level 1

In my previous post, I challenged you to solve Infinite 2D Array using Haskell. As a reminder, the problem specifies a two-parameter recurrence F_{x,y}, given by

  • F_{0,0} = 0
  • F_{0,1} = F_{1,0} = 1
  • F_{i,0} = F_{i-1,0} + F_{i-2,0} for i \geq 2
  • F_{0,i} = F_{0,i-1} + F_{0,i-2} for i \geq 2
  • F_{i,j} = F_{i-1,j} + F_{i,j-1} for i,j \geq 1.

We are given particular values of x and y, and asked to compute F_{x,y} \bmod (10^9 + 7). The problem is that x and y could be as large as 10^6, so simply computing the entire x \times y array is completely out of the question: it would take almost 4 terabytes of memory to store a 10^6 \times 10^6 array of 32-bit integer values. In this post, I’ll answer the Level 1 challenge: coming up with a general formula for F_{x,y}.

We need to be more clever about computing a given F_{x,y} without computing every entry in the entire 2D array, so we look for some patterns. It’s pretty obvious that the array has Fibonacci numbers along both the top two rows and the first two columns, though it’s sadly just as obvious that we don’t get Fibonacci numbers anywhere else. The last rule, the rule that determines the interior entries, says that each interior cell is the sum of the cell above it and the cell to the left. This looks a lot like the rule for generating Pascal’s triangle, i.e. binomial coefficients; in fact, if the first row and column were specified to be all 1’s instead of Fibonacci numbers, then we would get exactly binomial coefficients.

I knew that binomial coefficients can also be thought of as counting the number of paths from one point in a grid to another which can only take east or south steps, and this finally gave me the right insight. Each interior cell is a sum of other cells, which are themselves sums of other cells, and so on until we get to the edges, and so ultimately each interior cell can be thought of as a sum of a bunch of copies of numbers on the edges, i.e. Fibonacci numbers. How many copies? Well, the number of times each Fibonacci number on an edge contributes to a particular interior cell is equal to the number of paths from the Fibonacci number to the interior cell (with the restriction that the paths’ first step must immediately be into the interior of the grid, instead of taking a step along the first row or column). For example, consider F_{3,2} = 11. The two 1’s along the top row contribute 3 times and 1 time, respectively, whereas the 1’s and 2 along the first column contribute 3 times, 2 times, and once, respectively, for a total of 11:

The number of paths from F_{0,k} to F_{x,y} is the number of grid paths from (1,k) to (x,y), which is \binom{(x-1) + (y-k)}{y-k}. Likewise the number of paths from F_{k,0} to F_{x,y} is \binom{(x-k) + (y-1)}{x-k}. All together, this yields the formula

\displaystyle F_{x,y} = \left(\sum_{1 \leq k \leq x} F_k \binom{x-k+y-1}{x-k}\right) + \left(\sum_{1 \leq k \leq y} F_k \binom{y-k+x-1}{y-k}\right) \pmod{P}

Commenter Soumik Sarkar found a different formula,

\displaystyle F_{x,y} = F_{x+2y} + \sum_{1 \leq k \leq y} (F_k - F_{2k}) \binom{y-k+x-1}{y-k} \pmod{P}

which clearly has some similarity to mine, but I have not been able to figure out how to derive it, and Soumik did not explain how they found it. Any insights welcome!

In any case, both of these formulas involve a sum of only O(x+y) terms, instead of O(xy), although the individual terms are going to be much more work to compute. The question now becomes how to efficiently compute Fibonacci numbers and binomial coefficients modulo a prime. I’ll talk about that in the next post!

Advertisement

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in competitive programming, haskell and tagged , , . Bookmark the permalink.

1 Response to Competitive programming in Haskell: Infinite 2D array, Level 1

  1. Pingback: Competitive programming in Haskell: Infinite 2D array, Levels 2 and 3 | blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.