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

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.

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

• Jason Hooper says:

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

2. Soumik Sarkar says:

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.

 {-# LANGUAGE BangPatterns, TypeApplications #-} import Data.Array.Unboxed import Data.List — Solution to Infinite 2D Array main :: IO () main = do [x, y] <- map read . words <$> getLine print$ solve x y solve :: Int -> Int -> Int solve 0 y | y > 0 = solve y 0 solve x y = foldl' plusmod (fib (x + 2 * y)) (map contrib [1..y]) where contrib i = (fib i minusmod fib (2 * i)) mulmod binom (y – i + x – 1) (y – i) mx :: Int mx = 3000000 fib :: Int -> Int fib = (fibs!) where fibs = listArray @UArray (0, mx) $unfoldr (\(!a, !b) -> Just (a, (b, plusmod a b))) (0, 1) binom :: Int -> Int -> Int binom = go where go n k | k < 0 || n < k = 0 go n k = fac!n mulmod ifac!k mulmod ifac!(n – k) fac = listArray @UArray (0, mx)$ unfoldr (\(!i, !x) -> Just (x, (i + 1, mulmod i x))) (1, 1) ifac = array @UArray (0, mx) \$ unfoldr (\(!i, !x) -> if i < 0 then Nothing else Just ((i, x), (i – 1, mulmod x i))) (mx, inv (fac!mx)) mm :: Int mm = 1000000007 infixl 6 plusmod infixl 6 minusmod infixl 7 mulmod plusmod, minusmod, mulmod :: Int -> Int -> Int plusmod a b = let c = a + b in if c >= mm then c – mm else c minusmod a b = let c = a – b in if c < 0 then c + mm else c mulmod a b = mod (a * b) mm inv :: Int -> Int inv x = go x (mm – 2) where go _ 0 = 1 go x y | even y = go (mulmod x x) (div y 2) | otherwise = mulmod x (go x (y – 1))

$$F_{x,y} = f_{x+2y} + \sum_{i=1}^y (f_i – f_{2i}) \binom{y-i+x-1}{y-i}$$

• Brent says:

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.

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