Lösung von 5SUM in O (n^3) mit strengen Speichergrenzen

Question

Ich brauche einen Weg, um das klassische 5SUM-Problem ohne Hashing oder mit einem speichereffizienten Weg des Hashing zu lösen.

Das Problem fragt, wie viele Teilfolgen in einer bestimmten Anordnung von Länge finden N die Summe gleich S haben

Ex:

Input 
6 5 
1 1 1 1 1 1 
Output 
6 

Die Einschränkungen sind:

N <= 1000 (size of the array) 
S <= 400000000 (the sum of the subsequence) 
Memory usage <= 5555 kbs 
Execution time 2.2s 

Ich bin mir ziemlich sicher, dass die freigesetzte Komplexität O (N^3) ist. Aufgrund der Speicherbeschränkungen bietet das Hashing keine tatsächliche O (1) Zeit.

Das Beste, was ich bekam, war 70 Punkte mit diesem Code. (Ich habe TLE auf 6 Tests)

#include <iostream> 
#include <fstream> 
#include <algorithm> 
#include <vector> 
#define MAX 1003 
#define MOD 10472 

using namespace std; 

ifstream in("take5.in"); 
ofstream out("take5.out"); 

vector<pair<int, int>> has[MOD]; 
int v[MAX]; 
int pnt; 
vector<pair<int, int>>::iterator it; 

inline void ins(int val) { 
    pnt = val%MOD; 
    it = lower_bound(has[pnt].begin(), has[pnt].end(), make_pair(val, -1)); 
    if(it == has[pnt].end() || it->first != val) { 
     has[pnt].push_back({val, 1}); 
     sort(has[pnt].begin(), has[pnt].end()); 
     return; 
    } 
    it->second++; 
} 

inline int get(int val) { 
    pnt = val%MOD; 
    it = lower_bound(has[pnt].begin(), has[pnt].end(), make_pair(val, -1)); 
    if(it == has[pnt].end() || it->first != val) 
     return 0; 
    return it->second; 
} 

int main() { 

    int n,S; 
    int ach = 0; 
    int am = 0; 
    int rez = 0; 
    in >> n >> S; 

    for(int i = 1; i <= n; i++) 
     in >> v[i]; 

    sort(v+1, v+n+1); 

    for(int i = n; i >= 1; i--) { 

     if(v[i] > S) 
      continue; 

     for(int j = i+1; j <= n; j++) { 
      if(v[i]+v[j] > S) 
       break; 
      ins(v[i]+v[j]); 
     } 

     int I = i-1; 

     if(S-v[I] < 0) 
      continue; 

     for(int j = 1; j <= I-1; j++) { 

      if(S-v[I]-v[j] < 0) 
       break; 

      for(int k = 1; k <= j-1; k++) { 

       if(S-v[I]-v[j]-v[k] < 0) 
        break; 

       ach = S-v[I]-v[j]-v[k]; 
       rez += get(ach); 

      } 
     } 
    } 

    out << rez << '\n'; 

    return 0; 
} 

Answer 1

Ich denke, dass es getan werden kann. Wir suchen nach allen Teilmengen von 5 Elementen im Array arr mit der richtigen SUM. Wir haben Array mit Indizes 0..N-1. Der dritte Punkt dieser fünf kann den Index i im Bereich 2..N-3 haben. Wir durchlaufen alle diese Indizes. Für jeden Index i erzeugen wir alle Kombinationen zweier Zahlen für den Index im Bereich 0..i-1 links vom Index i und alle Kombinationen von zwei Zahlen für den Index im Bereich i+1..N-1 rechts vom Index i. Für jeden Index i gibt es weniger als N*N Kombinationen auf der linken Seite und auf der rechten Seite. Wir würden nur die Summe für jede Kombination speichern, also wäre es nicht mehr als 1000 * 1000 * 4 = 4MB.

Jetzt haben wir zwei Folgen von Zahlen (die Summen) und Aufgabe ist dies: Nehmen Sie eine Nummer aus der ersten Sequenz und eine Nummer aus der zweiten Sequenz und erhalten Summe gleich Si = SUM - arr[i]. Wie viele Kombinationen gibt es? Um es effizient zu machen, müssen Sequenzen sortiert werden. Say First ist aufsteigend sortiert und hat die Nummern a, a, a, b, c ,.... Die Sekunde ist absteigend sortiert und hat die Nummern Z, Z, Y, X, W, .... Wenn a + Z > Si dann können wir Z wegwerfen, weil wir nicht kleinere Zahl haben, um zusammenzupassen. Wenn a + Z < Si wir a wegwerfen können, weil wir keine größere Zahl haben, um zusammenzupassen. Und wenn a + Z = Si wir haben 2 * 3 = 6 neue Kombinationen und loswerden sowohl a und Z. Wenn wir kostenlos sortieren, ist es ein schöner O (N^3) -Algorithmus.

Während die Sortierung nicht kostenlos ist, ist es O (N * N^2 * log (N^2)) = O (N^3 * log (N)). Wir müssen in linearer Zeit sortieren, was nicht möglich ist. Oder ist es? Im Index i+1 können wir Sequenzen aus dem Index i wiederverwenden. Es gibt nur wenige neue Kombinationen für i+1 - nur solche, die die Nummer arr[i] zusammen mit einer Nummer aus dem Index 0..i-1 enthalten. Wenn wir sie sortieren (und wir können, weil es nicht N*N von ihnen gibt, aber höchstens N), müssen wir nur zwei sortierte Sequenzen zusammenführen. Und das kann in linearer Zeit geschehen. Wir können es sogar vermeiden, komplett zu sortieren, wenn wir am Anfang sortieren. Wir verschmelzen einfach.

Für die zweite Sequenz beinhaltet das Zusammenführen nicht hinzufügen, sondern entfernen, aber es ist sehr ähnlich.

Die Umsetzung scheint zu funktionieren, aber ich erwarte, dass es durch einen Fehler irgendwo ;-)

#include <iostream> 
#include <fstream> 
#include <algorithm> 
#include <vector> 

using namespace std; 


int Generate(int arr[], int i, int sums[], int N, int NN) 
{ 
    int p1 = 0; 
    for (int i1 = 0; i1 < i - 1; ++i1) 
    { 
     int ai = arr[i1]; 
     for (int i2 = i1 + 1; i2 < i; ++i2) 
     { 
      sums[p1++] = ai + arr[i2]; 
     } 
    } 
    sort(sums, sums + p1); 
    return p1; 
} 

int Combinations(int n, int sums[], int p1, int p2, int NN) 
{ 
    int cnt = 0; 
    int a = 0; 
    int b = NN - p2; 

    do 
    { 
     int state = sums[a] + sums[b] - n; 

     if (state > 0) { ++b; } 
     else if (state < 0) { ++a; } 
     else 
     { 
      int cnta = 0; 
      int lastA = sums[a]; 
      while (a < p1 && sums[a] == lastA) { a++; cnta++; } 

      int cntb = 0; 
      int lastB = sums[b]; 
      while (b < NN && sums[b] == lastB) { b++; cntb++; } 

      cnt += cnta * cntb; 
     } 
    } while (b < NN && a < p1); 

    return cnt; 
} 

int Add(int arr[], int i, int sums[], int p2, int N, int NN) 
{ 
    int ii = N - 1; 
    int n = arr[i]; 
    int nn = n + arr[ii--]; 
    int ip = NN - p2; 
    int newP2 = p2 + N - i - 1; 

    for (int p = NN - newP2; p < NN; ++p) 
    { 
     if (ip < NN && (ii < i || sums[ip] > nn)) 
     { 
      sums[p] = sums[ip++]; 
     } 
     else 
     { 
      sums[p] = nn; 
      nn = n + arr[ii--]; 
     } 
    } 
    return newP2; 
} 

int Remove(int arr[], int i, int sums[], int p1) 
{ 
    int ii = 0; 
    int n = arr[i]; 
    int nn = n + arr[ii++]; 
    int pp = 0; 
    int p = 0; 
    for (; p < p1 - i; ++p) 
    { 
     while (ii <= i && sums[pp] == nn) 
     { 
      ++pp; 
      nn = n + arr[ii++]; 
     } 
     sums[p] = sums[pp++]; 
    } 
    return p; 
} 

int main() { 
    ifstream in("take5.in"); 
    ofstream out("take5.out"); 

    int N, SUM; 
    in >> N >> SUM; 

    int* arr = new int[N]; 

    for (int i = 0; i < N; i++) 
     in >> arr[i]; 

    sort(arr, arr + N); 

    int NN = (N - 3) * (N - 4)/2 + 1; 
    int* sums = new int[NN]; 
    int combinations = 0; 
    int p1 = 0; 
    int p2 = 1; 

    for (int i = N - 3; i >= 2; --i) 
    { 
     if (p1 == 0) 
     { 
      p1 = Generate(arr, i, sums, N, NN); 
      sums[NN - 1] = arr[N - 1] + arr[N - 2]; 
     } 
     else 
     { 
      p1 = Remove(arr, i, sums, p1); 
      p2 = Add(arr, i + 1, sums, p2, N, NN); 
     } 

     combinations += Combinations(SUM - arr[i], sums, p1, p2, NN); 
    } 

    out << combinations << '\n'; 

    return 0; 
}