Problem Link
Prerequisites
Divide and Conquer, two pointer
Problem Description
Given a rectangle N * M and a square free number K <= 10^4 , we need to find the number of sub rectangles, such that product of all the cells in it will yield K.
Explanation
The cells of the given rectangle will contain only 1 or any other prime factor of K. Let us see how many different prime factors of K are possible. Given that K is square free, prime-factorization of K will look like K = p_1 * p_2 *...* p_S. We need to see how much can the value of S can go.
Taking the minimal possible values of p_i, 2*3*5*7*11*13 > 10^4. Hence value of S will not exceed 6 for sure. Hence we have to count total number of rectangles, having all S primes, with each of them present exactly once.
Armed with above information, lets solve this problem using Divide and Conquer approach. Split the entire matrix/rectangle into two parts by drawing a horizontal line. Hence we will get two matrix X and Y each of size (N / 2) * M each. First, we’ll compute the number of sub-rectangles that contains a part from both X and Y. Then, we’ll solve this task for each of X and Y independently.
Now we’ll count sub-rectangles that overlaps both X and Y. First let us fix the horizontal width of the rectangle. Then we’ll iterate over possible rectangles with that fixed width. A picture speaks a thousand word:-
Let the green markers denotes one possible sub rectangle having all S divisors and orange one another such rectangle. Note that there will be at most S such (minimal sized) sub rectangles for a fixed width such that if you decrease their height, then they will not contain the all S primes. Increasing the height i.e distance between two greens / oranges might still keep it consistent as the added row in that sub rectangle might be all ones. Hence we can calculate those S rectangles by keeping a note of first occurrence of each prime for each column above and below the split line. Then, once we have a minimalist sub rectangle, we can see how far we can elongate it’s height in both directions (until which adding a row will add another prime, causing repetitions) and add the corresponding count to our answer. This can be done using 2-pointer approach on the list of first occurrence of prime array or binary search, although the latter one might time out in case of inefficient implementation.
Hence for each pair of fixed width lines, we have a processing of O(S). There will be O(N^2) such pairs (consider for case of N*N grid for simplicity of asymptotic calculation). Hence for each grid that we encounter, we’ll need to do work of O(N^2 S), and then further break down the recursion to two grids of half the size. Note that once you break the N*N grid into two parts, you will get two grids of (N/2)*N. When processing these grids, you should first rotate the grid by 90 degrees clock/anti-clock wise to reduce column width, since we iterate on column pairs and therefore we will reduce work done per grid by rotation.
Formally calculating the time complexity,
T(N) = O(N^2S) + 4*T(N/2)
Solving this recurrence, we get,
T(N) = O(N^2 * logN * S)
Note that the reason for a factor of 4 being there (instead of intuitive 2) is because it will take a grid to get splitted 2 times to actually make it’s column width half, that is being processed. In other word, the extra work that we will do for each grid we encounter recursively will remain same and change at an interval of 2. To get more clarity, try drawing some rectangles and break them down recursively.
There is a similar question which you can try: Empty Rectangles.