<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>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. <br>
</p>
<p>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.</p>
<p>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.<br>
</p>
<p>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.</p>
<p>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?</p>
<p>The number of places you can position a 3 x 3 board within an n x
n space is something like (n-3)^2 if I'm not mistaken?</p>
<p>So you can subtract that from the total number of boards to
arrive at a result.</p>
<p>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 ten-second-in-the-shower
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.<br>
</p>
<div class="moz-cite-prefix">On 2020-06-28 8:50 p.m., Julian Ong
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:1998786082.488717.1593391840318@mail.yahoo.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div class="yahoo-style-wrap" style="font-family:Helvetica Neue,
Helvetica, Arial, sans-serif;font-size:13px;">
<div dir="ltr" data-setdir="false">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.</div>
<div dir="ltr" data-setdir="false"><br>
</div>
<div dir="ltr" data-setdir="false">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.</div>
<div dir="ltr" data-setdir="false"><br>
</div>
<div dir="ltr" data-setdir="false">---</div>
<div dir="ltr" data-setdir="false"><br>
</div>
<div dir="ltr" data-setdir="false">
<div>
<div>-- CSES - Two Sets</div>
<div>-- 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</div>
<div><br>
</div>
<div>main :: IO ()</div>
<div>main = do</div>
<div> line <- getLine</div>
<div> let n = read line :: Integer</div>
<div> putStrLn $ solveN n</div>
<div> </div>
<div>-- 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</div>
<div>-- Then the algorithm starts adding numbers from n down
to 1 until the next number would make the sum exceed the
required set sum</div>
<div>-- 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.</div>
<div>solveN :: Integer -> String</div>
<div>solveN n</div>
<div> | (n * (n+1) `mod` 4 /= 0) = "NO"</div>
<div> | otherwise = "YES\n" ++ show set1_count ++ "\n" ++
(unwords $ map show set1_list) ++ "\n" ++ show set2_count
++ "\n" ++ (unwords $ map show set2_list)</div>
<div> where</div>
<div> set_sum = (n * (n+1)) `div` 4</div>
<div> set1_part1 = takeWhile (\x -> x*(n+1-x)
+ sum [0..(n-x)] < (n * (n+1)) `div` 4) [n, n-1..1]</div>
<div> set1_part2 = set_sum - sum set1_part1</div>
<div> set1_list = set1_part1 ++ [set1_part2]</div>
<div> set1_count = (toInteger . length) set1_list</div>
<div> set2_list = [x | x <- [1..n], not (x
`elem` set1_list)]</div>
<div> set2_count = (toInteger . length) set2_list</div>
</div>
----</div>
<div dir="ltr" data-setdir="false"><br>
</div>
<div dir="ltr" data-setdir="false">Julian</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
Beginners mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Beginners@haskell.org">Beginners@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a>
</pre>
</blockquote>
</body>
</html>