_badass_'s blog

By _badass_, history, 4 weeks ago, In English,

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

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

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it
Hint 1
Hint 2
Hint 3
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks a lot man :) Can you explain a bit about hint-3? Using an example would be better.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

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