[Haskell-beginners] CSES Two Sets problem at https://cses.fi/problemset/task/1092/
Julian Ong
julian_ong at yahoo.com
Mon Jun 29 00:50:40 UTC 2020
After the Two Knights problem, I went on this next problem which requires that you separate 1..n into two sets with the same sum if possible. Again my algorithm in Haskell works but is apparently too slow. It fails for CSES test inputs >= 26560 where a solution exists.
I'm starting to wonder if Haskell is fundamentally too slow compared to other languages. From what I've read that shouldn't be the case though. For this problem it looks like it's doable in Python (I haven't tried that). Most of the fastest solutions for these problems seem to be written in C++. If there's anyone who's trying to solve these problems in Haskell (they're really fun by the way if you've never checked them out) and has solved this one (or Two Knights) and passed all the tests, I'd love to hear how you did it. Thanks.
---
-- CSES - Two Sets-- Given 1..n, separate into two sets of equal sums and if possible list the elements of each set of a possible solution or output NO if not possible
main :: IO ()main = do line <- getLine let n = read line :: Integer putStrLn $ solveN n -- Observe that sum [1..n] = n*(n+1)/2 so each set sum must be n*(n+1)/4 and so the set sum must be divisible by 4 for the separation to be possible-- Then the algorithm starts adding numbers from n down to 1 until the next number would make the sum exceed the required set sum-- At this point you add one more number, which will be the lowest number, to fill in the gap to complete set1. Set2 is then the other numbers.solveN :: Integer -> StringsolveN n | (n * (n+1) `mod` 4 /= 0) = "NO" | otherwise = "YES\n" ++ show set1_count ++ "\n" ++ (unwords $ map show set1_list) ++ "\n" ++ show set2_count ++ "\n" ++ (unwords $ map show set2_list) where set_sum = (n * (n+1)) `div` 4 set1_part1 = takeWhile (\x -> x*(n+1-x) + sum [0..(n-x)] < (n * (n+1)) `div` 4) [n, n-1..1] set1_part2 = set_sum - sum set1_part1 set1_list = set1_part1 ++ [set1_part2] set1_count = (toInteger . length) set1_list set2_list = [x | x <- [1..n], not (x `elem` set1_list)] set2_count = (toInteger . length) set2_list----
Julian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20200629/f9550590/attachment.html>
More information about the Beginners
mailing list