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.

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.

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

  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 :)


    {-# LANGUAGE BangPatterns, TypeApplications #-}
    import Data.Array.Unboxed
    import Data.List
    Solution to Infinite 2D Array
    https://open.kattis.com/problems/infinite2darray
    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.

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

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