# PROBLEM LINK

**Author:**Jaymeet Mehta

**Tester:**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.

**Time Complexity: O ( N^3 )**

**(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