Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to beginners-requ...@haskell.org
You can reach the person managing the list at beginners-ow...@haskell.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. CSES Two Sets problem at https://cses.fi/problemset/task/1092/ (Julian Ong) ---------------------------------------------------------------------- Message: 1 Date: Mon, 29 Jun 2020 00:50:40 +0000 (UTC) From: Julian Ong <julian_...@yahoo.com> To: The Haskell-Beginners Mailing List - Discussion of Primarily Beginner-level Topics Related To Haskell <beginners@haskell.org> Subject: [Haskell-beginners] CSES Two Sets problem at https://cses.fi/problemset/task/1092/ Message-ID: <1998786082.488717.1593391840...@mail.yahoo.com> Content-Type: text/plain; charset="utf-8" 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-0001.html> ------------------------------ Subject: Digest Footer _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners ------------------------------ End of Beginners Digest, Vol 144, Issue 8 *****************************************