hey guys! can u explain why I can ignore the exact positions of the rooks in the initial configurations and that only the number of free rows and columns matter.

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

No items |

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

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

8 | orz | 146 |

10 | BledDest | 145 |

hey guys! can u explain why I can ignore the exact positions of the rooks in the initial configurations and that only the number of free rows and columns matter.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2024 22:01:12 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You simply can imagine it as a checkered square field and after you cut out a row or column you put the pieces back together and get the same, but just smaller square field. It perfectly shows why the order doesn't matter.

Look at it this way. A configuration is valid if no two rooks share the same column or row. So given that there are n rows and n columns, and a rook uses up one row and one column, it doesn't really matter which row and which columns it uses, since you will have left n-1 rows and n-1 columns. Notice that once you are actually solving the problem, the position actully matters while counting because you might count choosing [(3,1) then (2,4)] and [(2,4) then (1,3)] as diferent configurations, but that's the fun part of the problem.

In a more computational way, a configuration of rooks is a matching between the n rows and the m columns, so by adding an edge between row x and column y (putting a rook in (x,y)) you are left with a match between n-1 rows and n-1 columns and in the counting it doesn't really matter which are this columns/rows [again watch out for repetition, and in the case of this problem, how choosing one edge, the computer will choose another]