## Competitive programming in Haskell: Infinite 2D array

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 $F_{x,y}$?
• Level 2: In general, how can you efficiently compute $F_{x,y} \pmod {10^9 + 7}$?
• 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.

Assistant 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.

### 2 Responses to Competitive programming in Haskell: Infinite 2D array

1. Jason Hooper says:

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

• Brent says:

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. =)

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