Hi Almighty CF Community,
First I googled a lot but didn't get any explanation.(However code is available)
I feel it difficult to solve problems of type "no of ways to arrange some elements of chess so that they are attacking/not attacking each other." I was solving CSES Two Knights problem and I am struggling to come up by a general formula.
I will request if any one can explain the idea behind such problems in general? or at least for this Two Knights problem.
$$$If \,you\, know \,some \,chess \,based \,problems, \,I \,will\, request\, you \,to \,please \,share \,it. \,Thanks.$$$
If two knight attack each other then they will be in 2*3 rectangle or 3*2 rectangle. So the number of ways of placing them is (n-1)*(n-2)+(n-2)*(n-1). Also in each rectangle no ways of placing the knight is 2. So total ways of placing knight so that they attack each other will be 2*2*(n-1)*(n-2). So the number of ways such that knight do not attack each other will be n*n*(n*n-1)/2 — 4*(n-1)*(n-2)
Thanks for the reply. One doubt total no of arrangement is $$$n^2(n^2-1)$$$ right? Because all the cells of chess are unique and this two knights are also different.
Two knights are same as it is not mentioned different explicitly in the question.
So interchanging the knights position will not going to create new ways.
There is no need to think. For each number of possible moves (2, 3, 4, 6 and 8) it is very easy to count the number of squares where you have this number of possible moves. For example, 2 moves are possible only from the corners, and there are 4 corners.
you can use Lagrange polynomial to find the expression, just take enough points( n, answer pairs) and brute force it.
Can you explain why it is a polynomial?
actually, sometime back I was solving a problem in which I used this and got the correct result. I don't have solid proof, but these were my thoughts that kinda convinced me and might convince you though I agree it's somewhat wage, let's increase the size of the chessboard by 1 unit,
f(n+1)-f(n)is a polynomial innbecause only polynomial more new places/orientation are created. (to be specific O($$$n^2$$$))(you can argue it might be a difference of some Taylor series expansion of some non-polynomial, but then again that function must be a mapping to infinite integer set, so that makes it difficult to not be polynomial according to my understanding, I am open to any suggestion on this.)
$$$f(n + 1) - f(n)$$$ is $$$O(n^2)$$$, but that doesn't make it a polynomial, it only means that it's bounded above by a polynomial. I don't know what the text in the brackets means.
do you agree f(n+1)-f(n) will be polynomial? Rest of this only make sense to me if you agree to it, I don't know, seeing the downvotes I think everybody knows/says it's not polynomial,then it's fine, I should be wrong, just igonre it, or give it downvotes.
In bracket, I meant that as some nonpolynomial can be written as polynomial as their Taylor series expansion, but I couldn't think of such a valid function, that have f(n+1)-f(n) O($$$n^2$$$) and an integer as output for every integer input.
It will, but only if we don't look at $$$n \le 5$$$ and not for the reasons you mentioned. I just did the math like dalex told.
There are many functions that have $$$f(n+1)-f(n) \in O(n^2)$$$ that are not polynomial. For example the minimum of two cubics. And a lot of functions that are the answer to some combinatorics problem.
You can watch this video : Editorial to 3 knights variation of the same problem. The audio is not that clear though, Still, you can understand the concept from this. Also, these sequences are generally available in OEIS, and hence googling the first few values works most of the time.