2
\$\begingroup\$

I am trying to solve the RIVALS problem on SPOJ: Starting from (0, 0), how many paths are there to reach point (X, Y), only taking one-unit steps moving to the right or up? Constraints: 0 ≤ X ≤ 106, 0 ≤ Y ≤ 106, answer is to be given modulo (109 + 7).

I am facing a performance issue with accessing elements of a list. I am also facing a runtime error if I am trying to access the list element.

In order to get the nth element I am using [1,1,1,2]!!n, but I have been told that this runs in O(n) which is very slow. Is there any other data structure in Haskell which gives O(1) access time for nth element?

About my algorithm: the number of way to move form (0,0) to (x,y) in 2D plain and answer is:

$$\frac{(x+y)!}{x!\ y!}$$

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Data.List
import Data.Bits
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Char8 as C

seqI :: Integer -> Integer
seqI x = seq x x

seqB :: Bool -> Bool
seqB x = seq x x



modExp' :: Integer -> Integer -> Integer -> Integer -> Integer
modExp' r b p m = let nextR = seqI $ (seqI $ r*b)`rem` m
                      nextB = seqI $ (seqI $ b*b)`rem` m
                      nextP = seqI $ shiftR  p 1
                      incl  = seqB $ testBit p 0
                      cont  = seqB $ nextP  /= 0
                  in  if incl
                         then if cont
                                 then modExp' nextR nextB nextP m
                                 else nextR
                         else if cont
                                 then modExp' r     nextB nextP m
                                 else r

modExp :: Integer -> Integer -> Integer -> Integer
modExp b p m = modExp' 1 b p m

readInts :: IO [Int]
readInts = fmap (map read.words) getLine

read2Ints :: IO [Int]
read2Ints = do
     ints <- readInts
     if length ints == 2 then return ints else do
         putStrLn ("sorry, could you give me exactly two integers, "
                  ++ "separated by spaces?")
         read2Ints

p = 1000000007::Integer
ip = 1000000005::Integer
mtimes a b =  (a * b)`rem`p
facts = scanl mtimes 1 [1..2000001]

anstable ::[Integer]
anstable  =  facts

solve ::Int->Int-> Integer
solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007


main :: IO ()
main = do
    n <- readLn
    forM_ [1..n::Int] (\i -> do
       xs <- read2Ints
       print $(solve (head xs) (last xs)))
\$\endgroup\$
2
\$\begingroup\$

Code organization

The definitions of readInts and read2Ints disrupt the mathematical code. The I/O routines belong further down, just before main.

import Data.Maybe and import qualified Data.ByteString.Char8 as C appear to be superfluous.

Abstraction

It is not immediately obvious from reading

solve x y = anstable!!(x+y)*(modExp (anstable!!x) ip p)*(modExp (anstable!!y) ip p)`rem`1000000007

that it is calculating

$$ \left(\begin{array}{c} x+y \\ y \end{array}\right) = \frac{(x + y)!}{x!\ y!}\mod p $$

I would expect to see

solve x y = modCombination (x + y) y p

modCombination n r p =
  (factorial n) * (modInvFactorial r) * (modFactorial (n - r)) `rem` p'
  where …

In some ways, you come close, but anstable obscures your intention. Why not ansTable, with the customary capitalization so that it doesn't look like an stable? Why did you rename it from fact in the first place, making it more confusing? Why is 1000000007 hard-coded at the end, when you could have used p?

What is ip? 1000000005 is a magic number that appears nowhere in the stated challenge. What about 2000001? Where did that limit come from?

\$\endgroup\$
  • \$\begingroup\$ Thanks for your reply.I am very new to Haskell so please forgive me for poor coding style. I have already solved this problem on spoj.I am learning Haskell and trying to code some easy problems in Haskell.P is mod and ip I am using while finding mod inverse of factorial x using Fermat theorem. Now come to the limit max value of x & y in this problem can be 10^6 and on finding nCr we need factorial (x+y) that's why factorial limit is 200001. About import libraries Initially I was using different method to read the data because of some issue I changed the input reading method. \$\endgroup\$ – Lakshman Jan 13 '15 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.