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!

I am stuck on this problem. https://www.codechef.com/problems/IOPC16K

Problem Statement:

Find out what will be the new shortest path if one of the edge on the original shortest path is removed.Find for all of the edges in shortest path path(Given Unique original shortest path).

Constraints:

no. of edges <= 1e5

no. of nodes <= 1e5

weights of edges <= 1e9

I Looked at some of the AC solutions but could not get the Idea. So if somebody can share the Idea to solve the problem it would be very Helpful! (I think its on some Algorithmic Paper).