CSES Two Sets problem at https://cses.fi/problemset/tas


CSES Two Sets problem at https://cses.fi/problemset/tas

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+1x) + sum [0..(nx)] < (n * (n+1)) `div` 4) [n, n1..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 _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Without having attempted to code this in any particular language,
but just thinking about the problem, I believe the CSES knights
problem is not a test of language speed or programming acumen but
a test of choosing an efficient choice of algorithm that doesn't
generate more information than the question asks for. In short, they're asking for the NUMBER of boards, not the actual boards. Most of the solutions people are proposing in Haskell simulate the problem instead of calculating it  in short, they generate the actual boards, then count them, whereas the solution only requires you to count them. The solutions for n = 1 and n = 2 can be calculated by hand and
put in as constants. n = 3 you can calculate or simulate as is
your preference. Knights have a maximum interaction range of three linear squares. Knights placed more than three squares apart in any one direction cannot hinder each other. So the number of illegal placements of knights can be confined to a 3x3 board. After that, all illegal boards of size n x n are simply one of those 3 x 3 boards shifted to a new position. The total number of n x n boards with two knights placed on them is given by (n^2) choose 2, which I'm not going to look up because it's been over 20 years since I took statistics and I'm happy about that. Still, it's a calculation. Not a super simple one from a computing perspective, since it involved factorials, but I'm assuming someone has figured out how to do factorials quickly in Haskell? The number of places you can position a 3 x 3 board within an n x n space is something like (n3)^2 if I'm not mistaken? So you can subtract that from the total number of boards to arrive at a result. NOTE: This likely requires SOME tweaking for edge cases (For
example, Is the board where k1 is in position x and k2 is in
position y considered the same as the board where their positions
reversed, or not? Does the choosing calculation factor for that
properly?) because it's literally a tensecondintheshower
concept, but it seems like this could come up with a result.
Whether it does it in time is mostly down to whether Haskell can
do factorials fast enough at that point. On 20200628 8:50 p.m., Julian Ong
wrote:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgibin/mailman/listinfo/beginners 
Free forum by Nabble  Edit this page 