Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
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 <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of Primarily
Beginner-level Topics Related To Haskell <[email protected]>
Subject: [Haskell-beginners] CSES Two Sets problem at
https://cses.fi/problemset/task/1092/
Message-ID: <[email protected]>
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
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 144, Issue 8
*****************************************
