# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3669 |

3 | apiadu | 3397 |

4 | TLE | 3374 |

5 | Um_nik | 3358 |

6 | 300iq | 3317 |

7 | maroonrk | 3232 |

8 | Benq | 3230 |

9 | LHiC | 3229 |

10 | 1919810 | 3203 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 192 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 171 |

5 | pikmike | 169 |

6 | Radewoosh | 164 |

7 | ko_osaga | 162 |

8 | Um_nik | 161 |

9 | 300iq | 156 |

10 | rng_58 | 154 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2020 15:53:03 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve the 1000 point problem ...

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

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.