SPBRD - Editorial

PROBLEM LINK

Practice

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 Solution
Tester's Solution
Editorialist's Solution
1 Like

Will you please tell me why is this giving RE?
https://www.codechef.com/viewsolution/33101448

@notsoloud Hey, I checked it out, your logic is perfect the issue is with the initialization of row[] and col[] arrays. Instead row[1005] you need to do like row[10005] because the constraints for n and m are 10^4 not 10^3.
This is the simple case of accessing indexes of an array which is out of bounds, that’s why you receive RE.

And I suggest if the initialization is not global then instead initializing arrays with constant you can initialize array with variable too. like row[m] and col[n].

1 Like

Thanks a lot! It got accepted :slight_smile:

1 Like