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 -> String
solveN 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