SPOJ SUMFOUR ..... TLE на тестовом примере 9

Question

я пытаюсь решить SPOJ Проблема SUMFOUR .... Я адресность TLE на тестовом примере 9 http://www.spoj.com/problems/SUMFOUR/

Итак, какая часть моего кода должен быть ? отредактирован и как здесь N = 4000 <

#include <iostream> 
#include<string> 
#include<algorithm> 
#include<cstdio> 
#include<cmath> 
#include<map> 
#include<vector> 

using namespace std; 


int main() 
{ 
int a[4005][5],n; 
cin>>n; 
for(int i=1;i<=n;i++) 
    for(int j=1;j<=4;j++) 
     scanf("%d",&a[i][j]); 
int k=0; 
for(int i=1;i<=n;i++) 
{ int p=a[i][1]; 
    for(int j=1;j<=n;j++) 
    { b.push_back(p+a[j][2]); 
     k++; 
    } 
} 
k=0; 
for(int i=1;i<=n;i++) 
{ int p=a[i][3]; 
    for(int j=1;j<=n;j++) 
    { c.push_back(p+a[j][4]); 
     k++; 
    } 
} 
sort(b.begin(),b.end()); 
int cnt=0; 
for(int j=0;j<k;j++) 
    if(find(b.begin(),b.end(),-c[j])!=b.end()) 
     cnt=cnt+count(b.begin(),b.end(),-c[j]) ; 


printf("%d\n",cnt); 
return 0; 
} 

Answer 1

проблема здесь:

for(int j=0;j<k;j++) 
     if(find(b.begin(),b.end(),-c[j])!=b.end()) 
      cnt=cnt+count(b.begin(),b.end(),-c[j]) ; 

при п = 4000, так что есть 4000^2 элементов в Ь и с. Таким образом, временная сложность этого цикла составляет 4000^4, так как find и count сложность времени - O (n), что, конечно же, приведет к превышению лимита времени.

Итак, как вы можете сократить время? Вы можете использовать двоичный поиск , чтобы ускорить процесс подсчета, что уменьшает временную сложность вышеуказанного цикла до O (n^2 log n), так как я заметил, что вы уже сортируете b.

Или вы можете использовать map для подсчета и сохранения частоты каждого элемента в b и c.

map<long long, int> b; 
map<long long, int> c; 

for(int i=1;i<=n;i++) 
{ long long p=a[i][1]; 
    for(int j=1;j<=n;j++) 
    { 
     long long tmp =p + a[j][2]; 
     b[tmp] = b[tmp] + 1; 
    } 
} 
// Similar for c 
map <long long, int>::iterator it; 
long long result; 
for (it = c.begin(); it != c.end(); ++it) 
     result += c[it->first]*b[-(it->first)]; 

Для вашего нового обновления, пожалуйста, изменить:

for(int j=1;j<=n;j++) 
    { if(b.count(a[i][1]+a[j][2])) 
     { b[a[i][1]+a[j][2]]+=1; 
      c[a[i][3]+a[j][4]]+=1; 
     } 
     else 
     { b[a[i][1]+a[j][2]]=1; 
      c[a[i][3]+a[j][4]]=1; 
     } 
    } 

в этом:

for(int j=1;j<=n;j++) 
    { 
      b[a[i][1]+a[j][2]]+=1; 
      c[a[i][3]+a[j][4]]+=1;    
    } 

условие проверки if(b.count(a[i][1]+a[j][2])) является только b, и использовать его для c, который Сделайте c некорректным.

Обновление: После попытки принять в SPOJ, оказывается, что карта не достаточно быстро, поэтому я вношу изменения в двоичный поиск и принимаю.

Мои accepted code

Answer 2

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

SO Вместо этого вы можете просто использовать два отсортированных массива и для каждого элемента, как в

первого массива, Двоичный поиск своего -ve агента во второй накопительном массиве.

Просто измените метод поиска в последних строках на двоичный поиск (c.begin(), c.end(), key) и найдите repititons до конца с этим индексом, поскольку он дает индекс lower_bound.

Это Общая сумма дает ответ и ожидаемый Сложность

О (п^2log (п)).