Hi guys! ✋
You are going to learn how Square Root Decomposition and DP can be mixed to generate harder problems.
The video tutorial is divided into 2 parts:
Refer the Video Description to find the links to problem link and other relevant information.
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 :)
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! 😆
