TouristFromOhio's blog

Problem C of the recent contest
By TouristFromOhio, history, 3 years ago, In English

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.

https://codeforces.me/contest/1957/problem/C

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

Comments Comments (2)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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]

    → Reply