[Tutorial] SquareRoot Decomposition + Dynamic Programming in Competitive Programming

Hi guys! ✋

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain microsoft

You are going to learn how Square Root Decomposition and DP can be mixed to generate harder problems.

This is an awesome math problem on Matrices. It is based on DP + Data Structures(Fenwick Tree/SquareRoot Decomposition). Its a counting problem from CSAcademy Junior Challenge 2017.

Problem Link is here.   

You are given a matrix $M$ with $N,M( \le 2000)$ rows and columns, and you have to count the no of special square submatrices. A square matrix is special if it has all $1s$ on its borders and principal diagonal(top-left to bottom-right). The rest of the matrix can be filled with either $0s$ and $1s$.  

In beginning, the problem seems to be solvable using only DP, but the solution is simply mind-blowing, jaw-dropping and beautiful.  

The trick here is to iterate on diagonals which are $O(N+M)$ in number. Then for each diagonal, count the number of special square submatrices that lie on current diaognal i.e their principal diagonal lies on the current diagonal that we are iterating. 

Lets pick any two points on the diagonal that we are currently at. 

Using DP, we do some preprocessing. Then the question is transformed to given two arrays $L,R$, find the number of pairs $(i, j)$ such that following 3 conditions are met:   

1. $i\le j$ 

2. $L_j \le i$

3. $R_i \ge j$  

We iterate on $j$, and use square root decomposition to solve this problem :)

The video tutorial is divided into 2 parts: 

1. Part1: Approaching the problem and building our solution

2. Part2: The Square Root Decomposition part

Refer the Video Description to find the links to problem link and other relevant information.

If you liked my efforts, please hit the like button 👍, subscribe and share the videos among your college :D  

Have a good day! 😆