GodSpeed98's blog

An Interesting Combinatorics Problem.[Help Needed]
By GodSpeed98, history, 6 years ago, In English

Problem Link : Here

Problem Statement:

You are given a grid of size M x N, where each square is colored with some random color among K colors with each having equal probability.

A Good Rectangle is defined as one where all squares lying on the inner border are of the same color.

What is the expected number of Good Rectangles in the given grid.

Constraints 1 <= N <= 10^5 1 <= M <= 10^5 1 <= K <= 10^5

Most of the AC codes i saw was some direct Formula in form of AGP or some other reduction. So if any one can Give me brief logical reduction to the formula, that would be great!

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

»
6 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Expected number of good rectangles

Probability that rectangle R is good

(Probability that a rectangle of size i * j is good) * (Number of rectangles with size i * j)

)

→ Reply