TouristFromOhio's blog

Problem C of the recent contest
By TouristFromOhio, history, 7 months 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.net/contest/1957/problem/C

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

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

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.

→ Reply
»
7 months ago, # |
  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
  • »
    »
    7 months ago, # ^ |
      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