Competitive programming in Haskell: Infinite 2D array

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

	{-# 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))

view raw

infinite2darray.hs

hosted with ❤ by GitHub

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

view raw

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.

About Brent

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

Leave a Reply Cancel reply

Pages

Categories

Archives

Top Posts

Blogroll

Fun

Personal

Meta