### npsecmigl's blog

By npsecmigl, history, 7 months ago, ,

I am trying to solve the problem for a long time but still didn't get any idea how to solve it. It would be great if you help me to solve it. Problem Link : https://vjudge.net/contest/332542#problem/A

Since the contest is ended that's why I share the vjudge link because I think everyone has not a light oj id and this problem is from light online judge(loj). Thanks in advance :) sorry for my poor english. :)

• +7

 » 7 months ago, # |   +9 Hint 1Firstly, note that if $k \gt n$, then by Pigeon Hole Principle, atleast two Rooks will be attacking, thus $ans = 0$. Hint 2Break down the problem into choosing $k$ distinct rows and $k$ distinct columns. Then you have rows — $r_{1}, r_{2}, ....., r_{k}$ and columns — $c_{1}, c_{2}, ...., c_{k}$.Then, you say that, first Rook is at $(r_{1}, c_{1})$, second Rook is at $(r_{2},c_{2})$, .... and so on. In general, $i^{th}$ Rook is at $(r_{i}, c_{i})$, for each $i \in [1,k]$. Hint 3Total ways of selecting k distinct rows is $C(n,k)$. And total ways of selecting k distinct columns is $C(n,k)$. Also, finally, we have not counted permuting the selected rows and columns. So we must multiply another $k!$.NOTE: Not $(k!)^2$ because, permuting both rows and columns means overcounting.
•  » » 7 months ago, # ^ |   +8 Thanks a lot man :) Can you explain a bit about hint-3? Using an example would be better.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +1 Let's work through an example. Consider $n = 10$, $k = 3$.Then, first choose three rows, let's call them $r_1, r_2, r_3$. Ofcourse, we have $1 \le r_1, r_2, r_3 \le 10$. Similiarly, choose three columns, say $c_1, c_2, c_3$. Again, $1 \le c_1, c_2, c_3 \le 10$. So far, number of ways are — $C(10,3)$ ( for choosing $3$ rows ) AND $C(10,3)$ ( for choosing $3$ columns ). So, for now, $ans = C(10,3)*C(10,3)$. But we see that, we have $6$ configurations ( notice $6 = 3!$ ) for placing Rooks, when we have these $x$ and $y$ co-ordinates.These configurations are:1) $(r_1,c_1)$,$(r_2,c_2)$,$(r_3,c_3)$.2) $(r_1,c_1)$,$(r_2,c_3)$,$(r_3,c_2)$.3) $(r_1,c_2)$,$(r_2,c_1)$,$(r_3,c_3)$.4) $(r_1,c_2)$,$(r_2,c_3)$,$(r_3,c_1)$.5) $(r_1,c_3)$,$(r_2,c_1)$,$(r_3,c_2)$.6) $(r_1,c_3)$,$(r_2,c_2)$,$(r_3,c_1)$.So, final answer should be $C(10,3)*C(10,3)*3!$.In, general, we have $C(n,k)*C(n,k)*k!$.
•  » » » » 7 months ago, # ^ |   0 Thanks a ton man :) understood.