First, here is the full challenge description:
Watson gives to Sherlock an array: \$A_1, A_2, ..., A_N\$. He also gives to Sherlock two other arrays: \$B_1, B_2, ..., B_M\$ and \$C_1, C_2, ..., C_M\$.
Then Watson asks Sherlock to perform the following program:
for i = 1 to M do for j = 1 to N do if j % B[i] == 0 then A[j] = A[j] * C[i] endif end do end do
Can you help Sherlock and tell him the resulting array
A
? You should print all the array elements modulo \$(10^9 + 7)\$.Input Format
The first line contains two integer numbers \$N\$ and \$M\$. The next line contains \$N\$ integers, the elements of array
A
. The next two lines contains \$M\$ integers each, the elements of arrayB
andC
.Output Format
Print \$N\$ integers, the elements of array
A
after performing the program modulo \$(10^9 + 7)\$.Constraints
\$1 ≤ N, M ≤ 10^5\$
\$1 ≤ B[i] ≤ N\$
\$1 ≤ A[i], C[i] ≤ 10^5\$Sample Input
4 3 1 2 3 4 1 2 3 13 29 71
Sample Output
13 754 2769 1508
And here is the code of my solution:
import Control.Applicative
import Control.Arrow
import Control.Monad.Primitive
import Control.Monad.ST
import Data.Int
import Data.List.Split
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.Map as M
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as Vmu
type Vec = V.Vector Int64
(|>) :: a -> (a -> b) -> b
(|>) x y = y x
infixl 0 |>
main :: IO ()
main = do
[n, m] <- (splitOn " " >>> map read) <$> getLine
inputLines <- B.split '\n' <$> B.getContents
let [a, b, c] = map readInts inputLines
solve n m a b c |> V.toList >>> map show >>> unwords |> putStrLn
-- http://stackoverflow.com/questions/25913481/read-numbers-from-stdin-into-a-data-vector-unboxed-vector-int64
readInts :: B.ByteString -> Vec
readInts = B.split ' ' >>> mapMaybe (B.readInt >>> liftA fst) >>>
map fromIntegral >>> V.fromList
limit :: Integral a => a -> a
limit = (`mod` 1000000007)
solve :: Int -> Int -> Vec -> Vec -> Vec -> Vec
solve n m a b c = applyChanges changes a
where
changes = [(i, \x -> limit $ x * fact ) | (i, fact) <- idxsAndFactors]
idxsAndFactors = [let ii = fromIntegral i
in zip [ii-1, ii+ii-1 .. (n-1)] (repeat factor) |
(i, factor) <- M.assocs factors] |> concat
factors = buildFactors m b c
-- http://stackoverflow.com/questions/25872149/apply-a-list-of-changes-to-elements-of-a-mutable-vector
applyChanges :: [(Int, Int64 -> Int64)] -> Vec -> Vec
applyChanges changes v = runST $ do
mV <- V.thaw v
mapM_ (applyChange mV) changes
V.freeze mV
applyChange :: (Control.Monad.Primitive.PrimMonad m, Vmu.Unbox t) =>
Vmu.MVector (Control.Monad.Primitive.PrimState m) t
-> (Int, t -> t) -> m ()
applyChange mvec (idx, f) = do
val <- Vmu.read mvec idx
Vmu.write mvec idx $ f val
buildFactors :: Int -> Vec -> Vec -> M.Map Int64 Int64
buildFactors m b c = M.empty |> comp inserts
|> M.map fromIntegral >>> M.mapKeys fromIntegral
where
inserts = [M.insertWith multAndLimit (b V.! i) (c V.! i) |
i <- [0 .. m-1]]
where multAndLimit x y = x * y |> limit
-- http://stackoverflow.com/questions/19777555/most-idiomatic-implementation-of-a-a-a-a
comp :: [b -> b] -> b -> b
comp = foldr (.) id
It passes all tests, but the code looks way too complicated to me, especially when I compare it to my Python solution:
import collections
import sys
def main():
lines = [[int(x) for x in line.split()] for line in sys.stdin]
[n, m], a, b, c = lines
def one():
return 1
# http://codereview.stackexchange.com/questions/62956/performance-in-hackerrank-challenge-sherlock-and-queries
factors = collections.defaultdict(one)
for i in range(0, m):
factors[b[i]] = factors[b[i]] * c[i] % 1000000007
for i, factor in factors.iteritems():
for idx in xrange(i-1, n, i):
a[idx] = a[idx] * factor % 1000000007
print ' '.join(map(str, a))
if __name__ == "__main__":
main()
Here is a large test case (#15):
On my system, the Python version takes about 0.5s and the Haskell version 0.7s.
Usually my Haskell code is shorter, but not in this case. Also, the Haskell solution runs a bit slower than the Python version. This also should be the other way around, I guess.
How could my Haskell code be improved, i.e. made more readable etc. without losing performance?