You are not logged in. Please login at www.codechef.com to post your questions!

×

RECTQUER - Editorial

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Gerald Agapov
Editorialist: Jingbo Shang

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:

for d = 1 to 10:
    Is there any d in the sub matrix?

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:

S[i][j] = S[i-1][j] + S[i][j-1] – S[i-1][j-1] + Matrix[i][j]

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,

# of number d in (x1,y1)-(x2,y2) = S[x2][y2]–S[x2][y1-1]–S[x1-1][y2]+S[x1-1][y1-1]

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).

alt text

Then we can have

S[x2][y2] = R + B + G + Y
S[x2][y1-1] = G + B
S[x1-1][y2] = G + Y;
S[x1-1][y1-1] = G
Our goal is R.

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.
Tester's solution can be found here.

This question is marked "community wiki".

asked 16 Dec '13, 18:51

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446173
accept rate: 0%

edited 17 Dec '13, 17:40

rsaha77's gravatar image

4★rsaha77
9653815


I used 2-D BIT, i would like to know any faster methods

link

answered 16 Dec '13, 19:28

yashkumar18's gravatar image

6★yashkumar18
82661224
accept rate: 18%

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) sudharkj3★

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) yashkumar186★

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) sudharkj3★

my segment tree works well.

(17 Dec '13, 14:55) muttakyn3★

I used 3D matrix and DP strategy :)

As it is given that only 10 different colours are used , we can use hashing here

#include<vector>
#include<algorithm>
#include<iostream> 
using namespace std;


int main(){

int buff;
int a[301][301];
int dp[301][301][10];
for(int i = 0 ; i <= 300 ; i++){
    for(int j = 0 ; j <= 300 ; j++){
        for(int k = 1 ; k <= 10 ; k++){
            dp[i][j][k] = 0;
        }}}
int n,q;
cin>>n;
for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= n ; j++){
        cin>>a[i][j];
        dp[i][j][a[i][j]] = 1;
}}

for(int i = 1 ; i <= n ; i++){
    int hash[11] = {0};
    for(int j = 1 ; j <= n ; j++){
        hash[a[i][j]]++;
        for(int k = 1 ; k <= 10 ; k++){
            dp[i][j][k] = hash[k];
}}}
cin>>q;
int x1,x2,y1,y2;
while(q--){
cin>>x1>>y1>>x2>>y2;
if( x1 == x2 && y1 == y2) cout<<1<<endl;
else{
int hash[11] = {0};
int count = 0;
for(int i = x1 ; i <= x2 && count<10; i++){
    for(int j = 1 ; j <= 10 ; j++){
        if(dp[i][y2][j] - dp[i][y1-1][j] > 0 && hash[j] == 0) {
            hash[j] = 1;
            count++ ;
}
}}
cout<<count<<endl;
}
}
return 0;
}
link

answered 16 Dec '13, 20:34

infinitum's gravatar image

2★infinitum
1.2k21116
accept rate: 10%

2

This is basically same with the method in editorial :)

(16 Dec '13, 20:47) shangjingbo ♦♦3★

What is the complexity of above code?

(16 Dec '13, 20:51) vikrant14333★

I think it is O(N^2 D) + O(Q N D). It stores 1-D prefix sum for each number and row. For each query, it needs to enumerate all different numbers and rows.

(16 Dec '13, 20:59) shangjingbo ♦♦3★

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.

link

answered 16 Dec '13, 20:49

vikrant1433's gravatar image

3★vikrant1433
227369
accept rate: 0%

1

The idea is to maintain 10 different 2-D prefix sum.

(16 Dec '13, 20:59) shangjingbo ♦♦3★

I used 2-d segment tree for each element 1-10.

link

answered 17 Dec '13, 08:33

sg1993's gravatar image

2★sg1993
46124
accept rate: 0%

I solved it using binary search. but it took a bit time, 0.82

link

answered 17 Dec '13, 13:01

imranraad's gravatar image

4★imranraad
1614
accept rate: 0%

how to solve it with binary search?

(17 Dec '13, 16:12) muttakyn3★

^^ please tell how to solve with binary search?

(20 Dec '13, 14:12) sskashish4★

Do the prefix sum for the binary matrix:

What does this mean?

link

answered 17 Dec '13, 21:44

yash_15's gravatar image

5★yash_15
5081716
accept rate: 2%

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!!!!!!!!!!

link

answered 18 Dec '13, 15:40

rsawankumar's gravatar image

2★rsawankumar
1
accept rate: 0%

I am having problem in understanding the editorial solution. For the matrix given in the question i.e. {{1, 2, 3}, {3, 2, 1}, {5, 6, 3}} the prefix sum matrix would be {{1, 3, 6}, {4, 8, 12}, {9, 19, 26}}?? If my prefix sum matrix is correct then the answer to the query (2,2) - (3,3) would be s[3][3] - s[3][1] -s[1][3] + s[1][1] = 26-9-6+1 => 12. How come it is 12? when the answer should be 4. Please tell me where I am wrong?

link

answered 28 Dec '13, 19:42

pawan68's gravatar image

2★pawan68
111
accept rate: 0%

Nope, here S[][], is a prefix matrix of binary matrix for a given number.d. Please read the editorial step by step. We first divide the original problem into D parts (D is the number of different numbers in the original matrix, at most 10).

(08 Jan '14, 19:43) shangjingbo ♦♦3★

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.

http://www.codechef.com/DEC13/status/RECTQUER,yoyosonu

link

answered 29 Dec '13, 14:06

yoyosonu's gravatar image

3★yoyosonu
31114
accept rate: 0%

edited 29 Dec '13, 14:06

of number d in (x1,y1)-(x2,y2) = S[x2][y2]–S[x2][y1-1]–S[x1-1][y2]+S[x1-1][y1-1]

can someone explain this??

link

answered 07 Jan '14, 20:33

vipulk10's gravatar image

3★vipulk10
1
accept rate: 0%

You may look at the figure. It is based on inclusion-exclusion principle actually. But it is straightforward in the picture.

(08 Jan '14, 19:42) shangjingbo ♦♦3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×13,381
×2,891
×69
×16

question asked: 16 Dec '13, 18:51

question was seen: 4,946 times

last updated: 08 Jan '14, 19:43