Opis glavnog rešenja

Označimo relaciju mogućeg ugneždavanja sa \(\rightarrow\), tj. neka \(B_i \rightarrow B_j\) označava da se kutija \(B_i\) može ugnjezditi u \(B_j\).

Pokažimo da je relacija \(\rightarrow\) tranzitivna. Neka su date \(d\)-dimenzione kutije \(B_x = (x_1, x_2, \ldots, x_d)\), \(B_y = (y_1, y_2, \ldots, y_d)\) i \(B_z = (z_1, z_2, \ldots, z_d)\). Pretpostavimo da važi \(B_x \rightarrow B_y\) i \(B_y \rightarrow B_z\), tj. postoje permutacije \(\pi\) i \(\sigma\) tako da veži \(x_{\pi(1)} < y_1, x_{\pi(2)} < y_2, \ldots, x_{\pi(d)} < y_d\) i \(y_{\sigma(1)} < z_1, y_{\sigma(2)} < z_2, \ldots, y_{\sigma(d)} < z_d\). Tada važi \(x_{\pi(\sigma(1))} < z_1, x_{\pi(\sigma(2))} < z_2, \ldots, y_{\pi(\sigma(d))} < z_d\), te je \(B_x \rightarrow B_z\).

Lako možemo zaključiti da važi \(B_x \rightarrow B_y\) akko su rastuće dimenzije kutije \(B_x\) po dimenzijama manje od rastućih dimenzija kutije \(B_y\). Zbog toga provera da li važi \(B_x \rightarrow B_y\) zahteva dva sortiranja dimenzija kutija složenosti \(O(d \log d)\) i jedno upoređivanje po dimenzijama složenosti \(O(d)\). Tada je ukupna složenost ove provere \(O(d \log d)\).

Dalje kreiramo graf \(G = (V, E)\). Za svaku kutiju \(B_i\), postoji čvor \(i \in V\). Za svaki par kutija \(B_i\) i \(B_j\) za koji važi \(B_i \rightarrow B_j\), postoji usmerena granu \((i, j) \in E\). Kako za svake dve kutije ispitujemo da li se jedna može ugnjezditi u drugu složenost konstrukcije ovog grafa je \(O(n^2 d \log d)\). Zbog tranzitivnosti, dobijeni graf je aciklički te je moguće odrediti najduži podniz pomoću topološkog sortiranja u složenosti \(O(n + m)\), gde je \(m\) broj parova kutija \(B_i\) i \(B_j\) za koje važi \(B_i \rightarrow B_j\). Broj \(m\) je u najgorem slučaju \(O(n^2)\). Tada je ukupna složenost ove konstrukcije \(O(n^2 d \log d)\).

Za efikasnije rešenje, nakon sortiranja dimenzija svake od kutija u vremenu \(O(n d \log d)\) možemo sortirati kutije u leksikografskom poretku po dimenzijama u vremenu \(O(d n \log n)\). Neka je leksikografski poredak kutija \(B_{i_1}, B_{i_2}, \ldots, B_{i_n}\). Primetimo da će ovaj leksikografski poredak kutija odgovarati topološkom poretku. Sada, za svaki par kutija \(B_{i_k}\) i \(B_{i_l}\) (\(k < l\)), ispitujemo da li \(B_{i_k} \rightarrow B_{i_l}\), u vremenskoj složenosti \(O(n^2 d)\). Shodno tome, konstruišemo odgovarajući graf \(G\). Po konstrukciji dobijeni graf je aciklički. Pored toga, čvorovi grafa su uređeni u topološkom poretku. Ukupna složenost ove konstrukcije je \(O(n d (n + \log d))\).

Složenost određivanja najdužeg puta u usmerenom acikličkom grafu je \(O(n + m)\). Broj \(m\) je u najgorem slučaju \(O(n^2)\), te ukupna složenost algoritma ostaje \(O(n d (n + \log d))\).

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

using namespace std;

typedef vector<int> Box;

bool nests(const Box &b1, const Box &b2)
{
    const int d = b1.size();

    for (int i = 0; i < d; i++) {
        if (b1[i] >= b2[i]) {
            return false;
        }
    }

    return true;
}

int longest_nested_sequence(vector<Box> &boxes)
{
    const int n = boxes.size();
    const int d = boxes[0].size();

    // O(nd log d)
    for (int i = 0; i < n; i++) {
        sort(boxes[i].begin(), boxes[i].end());
    }

    // O(dn log n)
    for (int i = d - 1; i >= 0; i--) {
        sort(boxes.begin(), boxes.end(), 
                [i](auto b1, auto b2) {
                    return b1[i] < b2[i];
                }
            );
    }

    vector<vector<int>> adj(n);

    // O(n^2 d)
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nests(boxes[i], boxes[j])) {
                adj[i].push_back(j);
            }
        }
    }

    // O(n^2)
    vector<int> dist(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j : adj[i]) {
            if (dist[j] < dist[i] + 1) {
                dist[j] = dist[i] + 1;
            }
        }
    }

    // O(n)
    return *max_element(dist.begin(), dist.end());
}

int main() 
{
    int d, n; cin >> d >> n;

    vector<Box> boxes(n, Box(d));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> boxes[i][j];
        }
    }

    cout << longest_nested_sequence(boxes) << endl;

    return 0;
}