найти эффективный алгоритм для ответа на запросы в подматрицы заданной квадратной матрицы

Question

Я пытаюсь решить “Rectangular Queries” problem from the December 2013 CodeChef contest:

Учитывая квадратная матрица N х N, заполненный целыми числами от {1, .. 10} , Нам даны Q (10^5) запросы следующим образом: , если x1, y1, x2, y2 найти количество уникальных элементов в данной подматрице.

Пределы: N < = 300 Q (10^5) x1 < < = х2 = N у1 = у2 < < = N ограничения по времени 1 сек.

Я пробовал подход, используя std :: set для уникальности, но получаю TLE ... МОЙ подход наивен ... цикл из верхнего левого угла вправо справа для запроса и добавления элементов для установки. Затем печать std: : set.size().

Answer 1

Есть два возможных подхода: -

1. решить проблему самостоятельно и получить кровно заработанные очки.

2. Ждите окончания конкурса и рассмотрите решения в редакционных статьях.

Удачи.

Answer 2

Вот простое решение, которое будет делать это в срок: -

#include<stdio.h> 
#define max 300 
int count[max][10][max]; 
int matrix[max][max]; 
int N; 

void gen_counts() { 
int i,j,k,number,index; 

for(i=0;i<N;i++) { 

    for(j=0;j<10;j++) 
     count[i][j][0] = 0; 
} 

for(i=0;i<N;i++) { 

    for(j=0;j<10;j++) { 

    for(k=0;k<N;k++) { 
     if(k>0) 
      count[i][j][k] = count[i][j][k-1]; 

     if(matrix[i][k]==j+1) { 
      count[i][j][k]++; 
     } 

    } 

    } 

} 


} 

int get_distinct(int r1,int c1,int r2,int c2) { 
    int i,j,present[10],ret=0; 
    for(i=0;i<10;i++) 
     present[i] = 0; 
    for(i=r1;i<=r2;i++) { 

    for(j=0;j<10;j++) { 
     if(c1>0) 
     present[j]=present[j]||(count[i][j][c1-1]<count[i][j][c2]); 
     else present[j] = present[j] || (count[i][j][c1]>0||count[i][j][c2]>0); 
    } 

    } 
    for(i=0;i<10;i++) 
    ret = ret + present[i]; 

    return(ret); 
} 



int main() { 

int Q,i,j,r1,r2,c1,c2; 

scanf("%d",&N); 

for(i=0;i<N;i++) { 

for(j=0;j<N;j++) 
    scanf("%d",&matrix[i][j]); 
} 

gen_counts(); 

scanf("%d",&Q); 

for(i=0;i<Q;i++) { 

scanf("%d%d%d%d",&r1,&c1,&r2,&c2); 
printf("%d\n",get_distinct(r1-1,c1-1,r2-1,c2-1)); 

} 


return(0); 

} 

Answer 3

я нашел оптимальный алгоритм для этой проблемы ... я думаю, что его сложность также меньше, чем O (N * N) , я думаю, что это будет полезно

#include <stdio.h> 

int main(void) { 
int n,i,j; 
//read matrix dimensions 
scanf("%d",&n); 

int mat[n][n]; 
int t,x1,x2,y1,y2; 
int counter[10],flag; 
//read matrix 
for(i=0;i<n;i++){ 
    for(j=0;j<n;j++){ 
     scanf("%d",&mat[i][j]); 
    } 
} 

scanf("%d",&t); 
//for each test case do this 
while(t--){ 
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 

    //make all counters zero 
    for(i = 0;i<10;i++){ 
     counter[i]=0; 
    } 

    flag = 0; 

    for(i=x1-1;i<=x2-1;i++){ 
     for(j=y1-1;j<=y2-1;j++){ 
      //counter == 0 means we are visiting the element for the first time 
      counter[mat[i][j]-1]++; 
     } 

    } 



    for(i =0;i<10 ;i++){ 
     if(counter[i]!=0){ 
      flag++; 
     } 
    } 

    printf("%d\n",flag); 

} 
return 0; 
}