HolyInq's blog

By HolyInq, 7 years ago, translation, In English,

If you intend advancing to Round 2 and didn't done it already.
Registation at 14:00 UTC, main event at 17:10.
600 participants will advance.

Good luck & have fun!

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

7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

How to solve the 1000 point problem ...

  • »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I'd like to know too...

    It's easy to calculate the expectancy of attacked cells if you only place only one knight. If I'm not mistaken, it's (8*N^2 — sigma(1,8) f(i)) / N^2, where f(i) is the amount of cells from which the knight cannot make move i (the knight can move in 8 different ways). For each of the 8 types of movement, you define the rectangular region from which the knight cannot make that move (it's always rectangular, covers either the whole horizontal range or the whole vertical range, and starts from one corner of the board, depending on the type of move), then f(i) is the area of that rectangle.

    But when the second knight comes into the game, it changes completely and I don't know how to solve it...

  • »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    First, let's solve problem "what is probability of cell (i; j) to be under attack? (call it p_i_j)". Calculate number of different cells (x, y), that if there is a knight on cell (x, y), cell (i, j) is under attack. Let it be A. Than p_i_j = (total — (n^2 — A) * (n^2 — A — 1) / 2) / total, where total = n^2 * (n^2 — 1) / 2 — number of different arrangements of knights.

    Now, we just need to calculate sum of p_i_j over all n^2 cells. We know that p_i_j depends only on A (number of different...). So let's divide all cells in groups with same value of A. Let's call value i interesting if exist such j that A[i][j] != A[i-1][j]. We can find that only {0, a, b, n — a, n — b, n} (may be +-1 in some of them) can be interesting. So if we divide our board into count_interesting^2 parts, for every part we could calculate p_i_j in some cell and multiply it by number of cells in part.