[Haskell-beginners] How to improve performace of a dfs program

xiong.hua ivoryxiong at gmail.com
Tue Jun 5 15:33:26 CEST 2012

```hi ,all :

I'm a learn haskell couple of days , and I want to solve some problem
[http://codeforces.com/contest/194/problem/D] with haskell , I know the
algorithm for the problem and implement it with haskell , but i jsut get TLE
on the test case . Here is my code , how i can implement it more Efficient ?

code :

import Data.Bits

import Data.Int

--import Debug.Trace

calc :: [Int64] -> [Int64] -> Int64

calc a b = sum \$ zipWith (*) a b

-- a p r

fun2op :: [Int64] -> [Int] -> Int64 -> [Int64]

--fun2op a x r |

--   trace ("fun2op " ++ show a ++ " " ++ show x ++ " " ++ show r ) False =
undefined

fun2op _ [] _ = []

fun2op a (x:xs) r = (( a !! (x-1)) + r) : (fun2op a xs r )

gor :: [Int64] -> [Int64] -> Int -> Int -> Int64 -> Int64

gor a k dep u ans

| (  ( u - dep ) .&.  1 :: Int) == 0 = max ans \$ calc a k

| otherwise = ans

-- a , b , p , k  , r , u , last , dep , ans

dfs :: [Int64] -> [Int64] -> [Int] -> [Int64] -> Int64 -> Int -> Int -> Int
-> Int64 -> Int64

dfs a b p k r u l dep ans

--    | trace ("dfs " ++ show a ++ " " ++ show l ++ " " ++  show dep ++ " "
++ show ans) False = undefined

| dep == u = max ans \$ calc a k

| l == 1  = df1

| otherwise  = max (df1) ( dfs (zipWith ( xor ) a b ) b p k r u 1
(dep+1) tmpans)

where

pa = fun2op a p r

tmpans = gor a k dep u ans

df1 = dfs pa b p k r u 2 (dep + 1) tmpans

rInt64 :: String -> Int64

rInt :: String -> Int

main = do

ss <- getLine

let tmp = words ss

let u = rInt (tmp !! 1)

let r = rInt64 ( tmp !! 2)

let x = map (rInt) \$ words ss

let x = map (rInt) \$ words ss

aa <- getLine

let a = map (rInt64) \$ words aa

bb <- getLine

let b = map (rInt64) \$ words bb

kk <- getLine

let k = map (rInt64) \$ words kk

pp <- getLine

let p = map (rInt) \$ words pp

print ( dfs a b p k r u 0 0 (rInt64 "-1000000000000000000"))

--------------

Best Regards

GTALK: ivoryxiong AT gmail.com

-------------- next part --------------
An HTML attachment was scrubbed...