If you like number theory, combinatorics, and/or optimizing Haskell code, I challenge you to solve Infinite 2D Array using Haskell.

- Level 1: can you come up with a general formula to compute ?
- Level 2: In general, how can you efficiently compute ?
- Level 3: Now implement the above ideas in Haskell so your solution actually fits within the 1 second time limit.

I have solved it but it was definitely challenging. In a subsequent blog post I’ll talk about my solution and ask for other optimization ideas.

### Like this:

Like Loading...

*Related*

##
About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

I tried the obvious dynamic programming recurrence with a lazy array, but it’s still too slow (fails on test 2). I was surprised since I’ve had a lot of luck with the array-based approach for many challenges before. I think I need to find a shortcut that skips the intermediate calculations

You mean you made a lazy array to directly hold the F_x,y values? Notice that x and y can be up to 10^6, so that would be an array with a trillion elements. =)

Yep I forgot to square the 10^6 when estimating the space requirements, oops. I thought a million would be pretty quick

Level 1: I found this formula works for x>0, F_{x,y} = f_{x+2y} + \sum_{i=1}^y (f_i – f_{2i}) \binom{y-i+x-1}{y-i}, where f_i is the ith Fibonacci number.

Level 2: Binomial coefficients can be calculated in constant time from factorials and inverse factorials. Fibonacci numbers, factorials and inverse factorials can be calculated modulo 10^9+7 in linear time. The formula above also takes linear time.

Level 3: I used unboxed arrays for storage and it ran in 0.24s, comfortably within the time limit :)

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

infinite2darray.hs

hosted with ❤ by GitHub

infinite2darray_formula.md

hosted with ❤ by GitHub

Very nice! It seems you found a slightly nicer formula than I did; mine involves two sums of Fibonacci numbers times binomial coefficients instead of just one.

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

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