Some error occured while loading page for you. Please try again.
Sort 6 Discussions, By:
Please Login in order to post a comment
My implementation in Scala fails time constraint on case 9. I can use mutable structures (e.g. Java collections, that Scala supports as is) to achieve much better performance but IMHO this is not what functional programming is used for. Maybe I'm wrong here, though...
In my opinion, some test case data are not following common sense rule. How many hands have inmate? Rather not more than 2. So how many pairs can inmate create - in my opinion also 2. But in TC3 data points that inmate 22 is cuffed with 5 other inmates! Cuffing directly one person to 5 other is rather impossible.
If I am correct description should be rephrased or some test cases changed.
So I have this, which compiles and runs fine locally:
groupSizes :: Graph -> [Int]
groupSizes g = map (\x -> length x) (components g)
cost :: Int -> Int
cost x = head [c | c <- [1..], c * c >= x]
group :: [String] -> [(Int, Int)]
group input = map (\x -> (read (head x), read (last x))) (map words input)
main = do
n <- getLine
m <- getLine
pairs <- replicateM (read m) getLine
let groups = group pairs
prisoners = buildG (1, read n) groups
tcost = map cost (groupSizes prisoners)
putStrLn $ show $ sum tcost
However I get error: Couldn't match type ‘Tree Vertex’ with ‘[a0]’ when i run it in the buffer. I'm a Haskell beginner and not sure what to make of this. Can I not import Data.Graph or what?
Is anyone else having trouble getting the last test to pass in-time w/ Haskell. All the other tests pass very quickly and then the last one always times-out by a large margin, and I've tried using many differnet datatypes and setups and it's always the same.
I'm using Scala but I had a similar problem, until I've implemented the ranked union-find data structure - surprisingly enough, you don't even need the path compression to make it work fast enough - I'm assuming Haskell will give you similar results, as I've only used pure immutable structures. Read the Wikipedia article about disjoint sets - it has everything you need - it's simpler than it looks at first.
me too. Im using Data.Set datatype
Where can I find a good Union-Find library for Haskell?
Hi, you can write it yourself :)
Just implement what you find in Wikipedia about ranked union find - you don't even need the path compression part, which seems to be counter-productive in pure functional implementations.
Where it says "Only one group of inmates can be transported per bus": for the purposes of this rule are single inmates considered to be groups of 1 or are we allowed to put all the single inmates on the same bus?
They are group of 1.
No more comments