PROBLEM LINK
Author: Jaymeet MehtaTester: Vatsal Parmar
Editorialist: Mann Mehta
DIFFICULTY
Easy
PREREQUISITES
Dynamic Programming
PROBLEM
Initially, We Are Given N × M Chessboard and R Black Rooks on that. We have to find Probability of placing one white rook safely such that no black rook attack’s, on the Chess-board in the form of P/Q where P and Q are Co-Prime Integers
QUICK EXPLAINATION
Consider a probability of an event of white rooks being safe as P(E)Where,
P(E) = Number of blocks on which Rook is safe ⁄ Total Number of Blocks
Total Number of blocks=N × M
We just need to find the total number of remaining blocks which are safe, and select any one block for white rook to be placed safely.
EXPLANATION
(I)Brute Force Approach:-Firstly we create a N × M Matrix let Mat[N][M]. For each query we have a block say (r,c)th for every Rth rook.
Now, as we know a rook at (r,c)th block will cover rth row and cth column for an attack, so we will eliminate all the (N+M) blocks for respective (r,c) block. Therefore for each query we keep on eliminate the unsafe blocks.
(II)DP Approach:-
Dynamic Programming Reference
Now,to implement this Make two Dynamic Tables for N rows and M columns
Initially this table will consisting True Values denoting safe row's and column's.
As the rook is placed on a (r,c)th block make rth row of Row Table and cth column of Column Table to False.
At last, there will be some rows say x and some columns say y which has True Value in Dynamic Table's or we can say safe row's and columns.
No of Safe Blocks = (No of safe rows) × (No of safe columns)
P(E) = Total number of safe blocks ⁄ Total number of blocks
Consider P = (x × y) and Q = (N×M)
P and Q are Co-Prime if and only if GCD(P,Q)=1
Now to make P and Q Co-Prime we should divide them by their GCD (Greatest Common Divisor)
P=P÷GCD(P,Q)
Q=Q÷GCD(P,Q)
P(E)=P⁄Q
TIME COMPLEXITY
Time Complexity is O(R) per test case.SOLUTIONS
Author's SolutionTester's Solution
Editorialist's Solution
