PROBLEM LINK:Author: Roman Rubanenko DIFFICULTY:Easy PREREQUISITES:Prefix sum PROBLEM:Given a N*N matrix of at most 10 different numbers, answer Q queries about how many distinct numbers are there in a given sub matrix. EXPLANATION:It is worth noting that there are at most 10 different numbers. Assume they are 1, 2, 3, ... , 10. To answer the number of distinct numbers, we can divide this problem to 10 separate problems:
Let’s focus on a given number d. Then the matrix can be treated as binary, i.e. whether the entry equals d. Do the prefix sum for the binary matrix:
With this O(N^2) preprocess, we can answer the problem “Is there any d in the sub matrix?” in O(1) time. That is,
Also, you can see the following figure for visualization. Denote the sum of red region as R, similar to Y(ellow), G(ray), B(lue). Then we can have
Using this technique, it is easy to solve this problem in O(N^2 + Q * D). D is the different numbers in the matrix. AUTHOR'S AND TESTER'S SOLUTIONS:Solutions to be uploaded soon. Author's solution can be found here.
This question is marked "community wiki".
asked 16 Dec '13, 18:51

I used 2D BIT, i would like to know any faster methods answered 16 Dec '13, 19:28
1
@yashkumar18 i thought of implementing using segment trees and it actually worked for larger inputs also, http://www.codechef.com/viewsolution/3069222 (tle). so i thought of another method and came up with an algo similar to the above editorial, http://www.codechef.com/viewplaintext/3095118. Method mentioned in the above editorial is better as you can see here, http://www.codechef.com/DEC13/status/RECTQUER,sudharkj. I thought of implementing using bit also. But, i was not able to code. @shangjingbo and @yashkumar18 could any one tell why segment tree method gave tle, but not for bit? Thanks.
(16 Dec '13, 20:50)
i think segment tree should give a faster solution but i prefer BIT, its much simpler, but i am not sure why segment tree would give tle
(16 Dec '13, 21:31)
may be wrong implementation of segment trees because someone else sg1993 was able to do it. Anyhow i liked the method in this editorial.
(17 Dec '13, 10:21)
my segment tree works well.
(17 Dec '13, 14:55)

Complexity of my solution is: PreProcessing O(N^2) + Q*Nlog(N). I didn't understand this editorial and would like to know some better algorithms for this kind of problems. answered 16 Dec '13, 20:49

I used 2d segment tree for each element 110. answered 17 Dec '13, 08:33

Hi could anyone please help me to find error in my solution for this problem RECTQUER. link to solution: http://www.codechef.com/viewsolution/3066953 Algorithm: Instead of 2D array, I have taken n * n one dimensional array. now one 2D temp array[n*n][10] (it will store cumulative count of all numbers till ith position). now to get the number of distinct element from (x1,y1) to (x2,y2) , I am converting these index for one dimensional array so l=x1 * n+y1 and r=x2 * n+y2. then take the difference array[r][10]array[i][10]. I have also taken care of boundary conditions and everything. please run this program in C++11 for given sample input or user generated input and point out why it is failing...please Help!!!!!!!!!! answered 18 Dec '13, 15:40

Someone please help me find why all my solution to this problem throw verdict "SIGSEGV" :'( I used the same logic as mentioned in the editorial. answered 29 Dec '13, 14:06
