Trgt_2021_explosion's blog

By Trgt_2021_explosion, history, 7 months ago, In English

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.$$$

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did u think like this! :O U just made my day!! its soo beautiful!!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Trgt_2021_explosion (previous revision, new revision, compare).

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My General Interpretation(after reading the comment by dolamanee6122)

Lets say $$$e1$$$ and $$$e2$$$ are two elements of chess. And we need to find "No of ways so that the attack each other/Not attack each other"

$$$Total\, no\, of\, ways$$$ to place these two are $$$n^2(n^2-1)/2 \,\,or\,\, n^2(n^2-1)$$$ if $$$e1$$$ and $$$e2$$$ are identical and non-identical respectively.

Now find $$$Minimum\,Region\,of\,attack$$$ and $$$Maximum \,Region \,of \,attack$$$ for $$$e1$$$ and $$$e2$$$.

$$$Minimum\,Region\,of\,attack$$$ — a rectangle of size $$$m_1*m_2 $$$ in which they can attack each other

Similarly $$$ Maximum\,Region\,of\,attack$$$ — a rectangle of size $$$M_1*M_2$$$

Now we can find no of rectangles of a given size in a grid easily. So our final result will be $$$ Total\, no\, of\, ways\, - \displaystyle \sum\limits_{i = m_1}^{M_1}\sum\limits_{j = m_2}^{M_2} (No\,of \,ways\, to \,choose\, rectangles \,of \,size\, (i*j )in\, given\, grid)*K_{ij}$$$

(where $$$K_{ij}$$$ is no of arrangement of $$$e1$$$ and $$$e2$$$ in the rectangle of size $$$(i*j)$$$ s.t. they are attacking each-other.)
Finding rectangle of size $$$i*j$$$ in a grid of size $$$m*n$$$ is straight. It's $$$(m-i+1)*(n-j+1)$$$ (for $$$i\leq m, j\leq n$$$)

Please point out if I am wrong.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is it that the total number of arrangments possible is n^2(n^2-1)/2. What is the mathematics involved in this?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 days ago, # |
  Vote: I like it -8 Vote: I do not like it

you can use Lagrange polynomial to find the expression, just take enough points( n, answer pairs) and brute force it.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Can you explain why it is a polynomial?

    • »
      »
      »
      10 days ago, # ^ |
      Rev. 2   Vote: I like it -12 Vote: I do not like it

      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 in n because 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.)

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 4   Vote: I like it +12 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              Interesting, I never encountered a non-polynomial combinatorial expression that isn't exponential and is Integer-valued.

              can you give some examples?

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.