25ος ΠΔΠ B' Φάση: Ανασύσταση της Βοιβηίδος λίμνης (karla) - Λύση

Επεξήγηση εκφώνησης

Μας δίνεται ένας πίνακας \(N\times N\) με ακέραιες τιμές και πρέπει να υπολογίσουμε πόσα συνδεδεμένα τμήματα θα μείνουν αν αφαιρέσουμε όλες τις τιμές μικρότερες ή ίσες με \(M\).

Δύο τιμές \(A, B\) είναι συνδεδεμένες (\(A\leftrightarrow B\)) αν:

H μία είναι μία από τις τέσσερις γειτονικές της άλλης.
Αν υπάρχει μία ακολουθία από γειτονικές τιμές \(k_1, \ldots, k_n\) ώστε \(Α \leftrightarrow k_1 \leftrightarrow \ldots \leftrightarrow k_n \leftrightarrow B\).

Αυτή η συνδεσιμότητα ορίζει έναν γράφο (δείτε την εικόνα για τον γράφο του παραδείγματος). Επομένως, πρέπει να μετρήσουμε τα συνεκτικά τμήματα του γράφου.

Στη συνέχεια θα δούμε δύο λύσεις που εντοπίζουν συνεκτικά τμήματα στο γράφο μας, η μία πρώτη λύση βασίζεται στην αναζήτηση κατά βάθος και η επόμενη στη δομή δεδομένων union-find. Και οι δύο περνάνε όλα τα testcases.

Αναζήτηση κατά βάθος

Ξεκινάμε από μία τιμή (\(> M\)) του πίνακα και βρίσκουμε όλες με τις οποίες συνδέεται. Το κάνουμε αυτό ξεκινώντας μία αναζήτηση-κατά-βάθος (DFS) στην τιμή. Κάθε τιμή που επισκεπτόμαστε την μαρκάρουμε, ώστε να μην την ξανα-επισκεφτούμε. Όταν δεν υπάρχουν άλλες τιμές που μπορούμε να επισκεφτούμε, συνεχίζουμε με την επόμενη τιμή μεγαλύτερη από \(M\) και αυξάνουμε τον μετρητή τμημάτων.

Αφού στο τέλος θα επισκεφτούμε κάθε τιμή μία φορά, ο αλγόριθμος τρέχει σε \(\mathcal{O}(N^2)\) και χρειάζεται μνήμη \(\mathcal{O}(N^2)\).

Υπάρχουν δύο κλασικοί τρόποι υλοποίησης της DFS: αναδρομικά ή γραμμικά. Ο γραμμικός τρόπος έχει το (μικρό) πλεονέκτημα ότι χρησιμοποιεί μικρότερη στοίβα κλήσεων. Παρακάτω δίνεται η αναδρομική υλοποίηση:

#include <stdio.h>

const size_t MAXN = 100;

int values[MAXN][MAXN];
bool visited[MAXN][MAXN];

int N, M;

bool isWithinBounds(int i, int j) {
   return i >= 0 && j >= 0 && i < N && j < N;
}

void visitAndMark(int i, int j) {
   visited[i][j] = true;
   if (isWithinBounds(i+1, j) && !visited[i+1][j] && values[i+1][j] > M) {
      visitAndMark(i+1, j);
   }
   if (isWithinBounds(i-1, j) && !visited[i-1][j] && values[i-1][j] > M) {
      visitAndMark(i-1, j);
   }
   if (isWithinBounds(i, j+1) && !visited[i][j+1] && values[i][j+1] > M) {
      visitAndMark(i, j+1);
   }
   if (isWithinBounds(i, j-1) && !visited[i][j-1] && values[i][j-1] > M) {
      visitAndMark(i, j-1);
   }
}

int main() {
   FILE *fi = fopen("karla.in", "r");
   fscanf(fi, "%d%d", &N, &M);
   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
         fscanf(fi, "%d", &values[i][j]);
      }
   }
   fclose(fi);
   
   int total = 0;
   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
         if (!visited[i][j] && values[i][j] > M) {
            visitAndMark(i, j);
            ++total;
         }
      }
   }
   
   FILE *fo = fopen("karla.out", "w");
   fprintf(fo, "%d\n", total);
   fclose(fo);
   
   return 0;
}
   

Η γραμμική υλοποίηση χρησιμοποιεί μία στοίβα:

void dfsIteratively(int begin_i, int begin_j) {
   std::stack<std::pair<int, int>> st;
   st.push(std::make_pair(begin_i, begin_j));
   
   while (!st.empty()) {
      int i = st.top().first;
      int j = st.top().second;
      st.pop();
      
      if (isWithinBounds(i+1, j) && !visited[i+1][j] && values[i+1][j] > M) {
         visited[i+1][j] = true;
         st.push(std::make_pair(i+1, j));
      }
      if (isWithinBounds(i-1, j) && !visited[i-1][j] && values[i-1][j] > M) {
         visited[i-1][j] = true;
         st.push(std::make_pair(i-1, j));
      }
      if (isWithinBounds(i, j+1) && !visited[i][j+1] && values[i][j+1] > M) {
         visited[i][j+1] = true;
         st.push(std::make_pair(i, j+1));
      }
      if (isWithinBounds(i, j-1) && !visited[i][j-1] && values[i][j-1] > M) {
         visited[i][j-1] = true;
         st.push(std::make_pair(i, j-1));
      }
   }
}

Μπορούμε να απλοποίησουμε τον έλεγχο των γειτονικών κελιών κρατώντας τις τέσσερις πιθανές διευθύνσεις σε έναν πίνακα:

std::vector<std::pair<int, int>> deltas({ {1, 0}, {-1, 0}, {0, 1}, {0, -1} });

void visitAndMark(int i, int j) {
   visited[i][j] = true;
   for (const auto& delta : deltas) {
      int ii = i + delta.first;
      int jj = j + delta.second;
      if (isWithinBounds(ii, jj) && !visited[ii][jj] && values[ii][jj] > M) {
         visitAndMark(ii, jj);
      }
   }
}

Συνένωση τμημάτων σε ομάδες (sets)

Γνώσεις που θα χρειαστούμε: union-find disjoint-sets

Θα εξερευνήσουμε με τη σειρά ένα ένα όλα τα κελιά, από αριστερά προς τα δεξιά και από πάνω προς τα κάτω. Θα εντάξουμε όλα τα μη πλημμυρισμένα κελιά σε μια νέα ή σε μια υπάρχουσα ομάδα.

Εργαζόμαστε ως εξής: αν το κελί που εξετάζουμε δεν είναι πλημμυρισμένο, το ενώνουμε με τα αμέσως γειτονικά του προς τα αριστερά και προς τα επάνω, εφόσον δεν είναι πλημμυρισμένα. Το αριστερό και το επάνω κελί τα έχουμε επεξεργαστεί πριν φτάσουμε στο τρέχον κελί. Επομένως, χρειάζεται να διατρέξουμε μία φορά τον πίνακα, άρα χρειάζονται \(\mathcal{O}(N^2)\) βήματα.

Στο τέλος μετράμε πόσες διαφορετικές ομάδες έχουν δημιουργηθεί στη union-find. Αυτό το κάνουμε μετρώντας τους διαφορετικούς εκπροσώπους που υπάρχουν. Το τελευταίο αυτό στάδιο θέλει άλλα \(\mathcal{O}(N^2)\) βήματα για την καταμέτρηση.

#include <cstdio>
//using namespace std;

const int MAXN = 101;
int N,M;
bool Z[MAXN][MAXN];//κελιά (true αν μη πλημμυρισμένο)
int dj[MAXN*MAXN];//disjoint set.
bool leader[MAXN*MAXN];//για την καταμέτηση των ομάδων

inline int xy(int x,int y){//μετέτρεψε τις δυο διαστάσεις σε μία
    return y*N + x;
}

int dj_find(int xy){//βρες τον εκπρόσωπο του x,y
    //xy είναι η μονοδιάσταση συντεταγμένη του κάθε κελιού
    if(dj[xy] == xy)
        return xy;
    return dj[xy] = dj_find(dj[xy]);
}

void dj_union(int a,int b){//ένωσε τις δυο ομάδες
    a = dj_find(a), b = dj_find(b);
    if(a!=b)//δεν έχουν τον ίδιο εκπρόσωπο
        dj[b] = a;//κάνε τον a, εκπρόσωπο του b
}

int dj_count(){
    int ans = 0;
    for(int i=0,k=N*N;i<k;i++){
        if(dj[i]>=0){
            int leader1 = dj_find(i);
            if(!leader[leader1]){
                leader[leader1]=true;
                ans++;
            }
        }
    }
    return ans;
}

int main(){
   freopen("karla.in", "r",stdin);
   freopen("karla.out", "w",stdout);

    scanf("%d%d",&N,&M);
    for(int y=0;y<N;y++){
        for(int a,x=0;x<N;x++){
            scanf("%d",&a);
            Z[x][y] = a>M;
        }
    }

    for(int y=0;y<N;y++){
        for(int x=0;x<N;x++){
            if(!Z[x][y]){ //πλημμυρισμένο κελί,
                dj[xy(x,y)] = -1;//να μην έχει εκπρόσωπο
                continue;
            }
            dj[xy(x,y)] = xy(x,y);//κάνε το εκπρόσωπο του εαυτού του

            if(x>0 && Z[x-1][y])
                dj_union(xy(x,y),xy(x-1,y));
            if(y>0 && Z[x][y-1])
                dj_union(xy(x,y),xy(x,y-1));
        }
    }

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

Μπορούμε να εξαλείψουμε την καταμέτρηση στο τέλος της παραπάνω λύσης. Θα χρησιμοποιήσουμε τη μεταβλητή \(\mathit{ans}\) στην οποία θα διατηρούμε τον αριθμό των ομάδων που έχουμε δημιουργήσει.

Κάθε μη πλημμυρισμένο κελί \(x,y\) που εξερευνούμε, το εντάσσουμε σε μία νέα ομάδα με εκπρόσωπο τον εαυτό του, αυξάνοντας την \(\mathit{ans}\).

Ελέγχουμε τα αμέσως γειτονικά του προς τα αριστερά και προς τα επάνω και αν δεν είναι πλημμυρισμένα και ανήκουν σε διαφορετική ομάδα, τα ενώνουμε με την ομάδα του τρέχοντος κελιού, μειώνοντας την μεταβλητή \(\mathit{ans}\).

Παρατηρήστε στον γράφο της ακόλουθης εικόνας πως θα ανακαλύψουμε αρχικά την πράσινη ομάδα, οπότε το \(\mathit{ans}\) γίνεται \(1\) και παραμένει \(1\) μέχρι και το τέλος της δεύτερης γραμμής. Εξερευνώντας την τρίτη γραμμή, συναντάμε κελιά της ροζ ομάδας, άρα το \(\mathit{ans}\) γίνεται \(2\), μέχρι που φτάνουμε στο μωβ κελί στο οποίο ανακαλύπτουμε ότι η πράσινη και η ροζ ομάδα ταυτίζονται και τις ενώνουμε (άρα το \(\mathit{ans}\) μειώνεται σε \(1\)). Όταν εξερευνήσουμε το δεξί άκρο της τέταρτης γραμμής, θα ανακαλύψουμε και την τρίτη ομάδα του γράφου μας.

Η αναζήτηση εκπροσώπου και η συνένωση ομάδων, γίνεται amortized σχεδόν σε σταθερό χρόνο¹ και δεν αλλάζει την ασυμπτωτική πολυπλοκότητα της λύσης.

#include <cstdio>
//using namespace std;

const int MAXN = 101;
int N, M, ans;
bool Z[MAXN][MAXN];//κελιά (true αν μη πλημμυρισμένο)
int dj[MAXN*MAXN];//disjoint set.

inline int xy(int x,int y){//μετέτρεψε τις δυο διαστάσεις σε μία
    return y*N + x;
}

int dj_find(int xy){//βρες τον εκπρόσωπο του xy
    if(dj[xy] == xy)
        return xy;
    return dj[xy] = dj_find(dj[xy]);
}

bool dj_union(int a,int b){//ένωσε τα δυο set
    a = dj_find(a), b = dj_find(b);
    if(a!=b){//δεν έχουν τον ίδιο εκπρόσωπο
        dj[b] = a;//κάνε τον a, εκπρόσωπο του b
        return true;//έγινε συνέωση
    }
    return false;//ανήκουν στο ίδιο set
}

inline void dj_create(int xy){//δημιουργήθηκε ένα νέο set με το κελί αυτό
    dj[xy] = xy;
}

int main(){
   freopen("karla.in", "r",stdin);
   freopen("karla.out", "w",stdout);

   scanf("%d%d",&N,&M);
    for(int y=0;y<N;y++){
        for(int a,x=0;x<N;x++){
            scanf("%d",&a);
            Z[x][y] = a>M;
        }
    }

    for(int y=0;y<N;y++){
        for(int x=0;x<N;x++){
            if(!Z[x][y]) //πλημμυρισμένο κελί, αγνόησε το
                continue;
            
            dj_create(xy(x,y));
            ans++;
            
            if(x>0 && Z[x-1][y] && dj_union(xy(x,y),xy(x-1,y)))
                ans--;
            
            if(y>0 && Z[x][y-1] && dj_union(xy(x,y),xy(x,y-1)))
                ans--;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Οι λειτουργίες union και find της union-find που χρησιμοποιούν συμπύκνωση μονοπατιών, χρειάζονται χρόνο \(\mathcal{O}(\alpha(N^2))\) ανα κλήση σε ένα δάσος \(N^2\) κόμβων σαν αυτό της άσκησης. Με \(\alpha(n)\) συμβολίζουμε την εξαιρετικά μικρής αύξησης ως προς το \(n\), αντίστροφη συνάρτηση Ackermann. Ενδεικτικά του ρυθμού αύξησης, το \(\alpha(9876 !)=5\). Στην πράξη, ο χρόνος στις συναρτήσεις union και find είναι σχεδόν γραμμικός λόγω του ότι το \(\alpha(n)\le 3\) για οποιοδήποτε \(n\) μπορεί να προκύψει στην πράξη ανφ.R.Tarjan. ↩