37ος ΠΔΠ Γ' Φάση: Αλυσίδες κριτικών (reviews) - Λύση

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

Μας δίνεται ένας συνδεδεμένος μη-κατευθυνόμενος γράφος ο οποίος έχει την μορφή ενός δέντρου με μία επιπλέον ακμή. Μας ζητείται για κάθε ακμή του γράφου να βρούμε το μήκος του μακρύτερου μονοπατιού μεταξύ δύο κορυφών του γράφου αν αυτή αφαιρεθεί από τον γράφο ή να επισημάνουμε ότι ο γράφος δεν είναι συνδεδεμένος.

Βασική παρατήρηση: Ο γράφος αποτελείται από έναν κύκλο και ένα ή περισσότερα δέντρα με ρίζες κόμβους του κύκλου.

Από αυτό προκύπτει ότι όταν αφαιρεθεί κάποια ακμή που δεν είναι στον κύκλο, τότε ο γράφος αποσυνδέεται και επομένως η απάντησή τους είναι $-1$. Οι υπόλοιπες ακμές (που ανήκουν στον κύκλο) δεν αποσυνδέουν τον γράφο.

Υποπρόβλημα 1

Σε αυτό το πρόβλημα όλοι οι κόμβοι ανήκουν στον κύκλο. Αν αφαιρέσουμε οποιαδήποτε ακμή μένει ένα μονοπάτι μήκους $N-1$. Επομένως μπορούμε να λύσουμε το πρόβλημα σε $\mathcal{O}(N)$ (δείτε τον κώδικα εδώ).

Υποπρόβλημα 2

Σε αυτό το υποπρόβλημα ο γράφος είναι πολύ μικρός και μπορούμε να αφαιρέσουμε κάθε ακμή και να βρούμε το μακρύτερο μονοπάτι στον υπολοιπόμενο γράφο, κάνοντας μία αναζήτηση κατά βάθος από κάθε κόμβο.

Ο αλγόριθμος αυτός χρειάζεται $\mathcal{O}(N^2)$ για κάθε ακμή, άρα $\mathcal{O}(N^3)$ συνολικά.

Αν αξιοποιήσουμε ότι ο υπολοιπόμενος γράφος είναι ένα δέντρο, τότε μπορούμε να βρούμε το μακρύτερο μονοπάτι σε $\mathcal{O}(N)$ χρόνο, κάνοντας δύο αναζητήσεις κατά βάθος:

Βρίσκουμε τον βαθύτερο κόμβο $u$ από τον κόμβο 1 (ή όποιον άλλον κόμβο)
Βρίσκουμε τον βαθύτερο κόμβο $x$ από τον κόμβο $u$. Η απόσταση μεταξύ των $u$ και $x$ είναι η μέγιστη απόσταση στο δέντρο (δείτε εδώ).

#include <cstdio>
#include <vector>

std::vector<std::vector<long>> adj;

/* Βοηθητική συνάρτηση που ελέγχει αν δύο ακμές είναι ίσες. */
bool are_same_edge(std::pair<long, long> p1, std::pair<long, long> p2) {
  return p1 == p2 || (std::make_pair(p1.second, p1.first) == p2);
}

/* Αναζήτηση κατά βάθος αποφεύγοντας την αφαιρεμένη ακμή. */
void dfs(long node, std::pair<long, long> forbidden_edge, std::vector<int>& visited) {
  visited[node] = true;
  for (auto neigh : adj[node]) {
    if (are_same_edge({node, neigh}, forbidden_edge)) continue;
    if (!visited[neigh]) dfs(neigh, forbidden_edge, visited);
  }
}

/* Έλεγχος αν ο γράφος είναι συνδεδεμένος. */
bool is_graph_connected(std::pair<long, long> forbidden_edge) {
  std::vector<int> visited(adj.size(), false);
  dfs(1, forbidden_edge, visited);
  for (long i = 1; i < adj.size(); ++i) {
    if (!visited[i]) return false;
  }
  return true;
}

/* Βρίσκει τον βαθύτερο κόμβο σε ένα δέντρο. */
std::pair<long /* max_distance */, long /* node */> find_furthest_node_in_tree(
    long node, 
    long par, 
    long depth, 
    std::pair<long, long> forbidden_edge) {
  long max_depth = depth;
  long max_depth_node = node;
  
  for (auto neigh : adj[node]) {
    if (neigh == par) continue;
    if (are_same_edge({node, neigh}, forbidden_edge)) continue;
    auto [cur_depth, cur_depth_node] = find_furthest_node_in_tree(neigh, node, depth + 1, forbidden_edge);
    if (cur_depth > max_depth) {
      max_depth = cur_depth;
      max_depth_node = cur_depth_node;
    }
  }
  return {max_depth, max_depth_node};
}

int main() {
  FILE *fi = fopen("reviews.in", "r");
  long T, N;
  fscanf(fi, "%ld%ld", &T, &N);
  adj.resize(N+1);
  std::vector<std::pair<long, long>> edges(N+1);
  for (long i = 1; i <= N; ++i) {
    long tmp;
    fscanf(fi, "%ld", &tmp);
    edges[i] = {i, tmp};
    adj[i].push_back(tmp);
    adj[tmp].push_back(i);
  }
  fclose(fi);
  
  FILE *fo = fopen("reviews.out", "w");
  for (long i = 1; i <= N; ++i) {
    if (!is_graph_connected(edges[i])) {
      fprintf(fo, "-1\n");
    } else {
      auto [x, furthest_node_from_1] = find_furthest_node_in_tree(1, -1, 0, edges[i]);
      auto [dist, y] = find_furthest_node_in_tree(furthest_node_from_1, -1, 0, edges[i]);
      fprintf(fo, "%ld\n", dist+1);
    }
  }
  fclose(fo);
  return 0;
}

Υποπρόβλημα 3

Σε αυτό το υποπρόβλημα υπάρχουν μόνο τρεις κόμβοι στον κύκλο, άρα μπορούμε απλά να τους αφαιρέσουμε και να βρούμε το μακρύτερο μονοπάτι στο υπολοιπόμενο δέντρο σε συνολικό χρόνο $\mathcal{O}(N)$ (δείτε τον κώδικα εδώ).

Υποπρόβλημα 4

Σε αυτό το υποπρόβλημα υπάρχει ένα σχετικά μικρό πλήθος κόμβων στον κύκλο. Όταν αφαιρούμε μία ακμή από τον κύκλο υπάρχουν τα εξής πιθανά σενάρια:

Η μεγαλύτερη απόσταση είναι μεταξύ δύο κόμβων στο ίδιο δέντρο (πράσινο).
Η μεγαλύτερη απόσταση ξεκινάει από ένα δέντρο συνεχίζει στον κύκλο και έπειτα συνεχίζει σε ένα άλλο δέντρο (κόκκινο).

Την πρώτη περίπτωση μπορούμε να την αντιμετωπίσουμε όπως στο Υποπρόβλημα 2 με τις δύο αναζητήσεις κατά βάθος.

Για την δεύτερη περίπτωση, αφαιρούμε την ακμή από τον κύκλο και το μονοπάτι που μένει το αντιμετωπίζουμε σαν έναν πίνακα. Βρίσκουμε $w[i]$ το βάθος του δέντρου με ρίζα τον κόμβο $i$ και έπειτα ψάχνουμε να βρούμε τους δύο κόμβους στον πίνακα με το μέγιστο $w[i] + w[j] + \lvert i - j\rvert$.

Μπορούμε εύκολα να βρούμε αυτή την μέγιστη τιμή δοκιμάζοντας όλα τα δυνατά ζευγάρια:

  for (long i = 1; i <= N; ++i) {
    if (index_in_cycle[i] == -1 || index_in_cycle[edges[i].second] == -1) {
      // Αν κάποια από τις δύο κορυφές δεν είναι στον κύκλο, τότε
      // ο γράφος δεν είναι συνδεδεμένος.
      fprintf(fo, "-1\n");
    } else {
      long u = i, v = edges[i].second;
      if (index_in_cycle[v] == (index_in_cycle[u] + 1) % cycle.size()) u = v;
      // Δοκιμάζουμε όλα τα δυνατά ζεύγη από κόμβους στον κύκλο:
      // Το μονοπάτι ξεκινάει στον j-οστό κόμβο στον κύκλο και καταλήγει στον jj-οστό.
      // Στους δύο ακριανούς κόμβους επιλέγουμε το μακρύτερο μονοπάτι. 
      long mx = 0;
      for (long j = 0; j < cycle.size(); ++j) {
        long idx_j = (index_in_cycle[u] + j) % cycle.size();
        for (long jj = j + 1; jj < cycle.size(); ++jj) {
          long idx_jj = (index_in_cycle[u] + jj) % cycle.size();
          long candidate = (jj - j) + w[cycle[idx_j]] + w[cycle[idx_jj]] + 1;
          mx = std::max(mx, candidate);
        }
      }
      // Η απάντηση είναι η μέγιστη από το mx και την μεγαλύτερη απόσταση δύο κόμβων, 
      // που περιέχεται πλήρως σε κάποιο από τα υποδέντρα.
      fprintf(fo, "%ld\n", std::max(mx, mx_internal_dist));
    }
  }
  fclose(fo);

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

/* Βρίσκουμε ποιοι κόμβοι ανήκουν στον κύκλο. 
   Το κάνουμε αυτό κρατώντας μία στοίβα με τους κόμβους που είναι στο μονοπάτι 
   της DFS. Όταν βρούμε δύο φορές τον ίδιο κόμβο, το μονοπάτι έγινε κύκλος. */
void find_cycle() {
  std::stack<std::tuple<long, long, long>> st;
  std::vector<long> is_on_stack(adj.size(), false);
  st.push({ 1, -1, 0 });
  while (!st.empty()) {
    auto [node, par, neigh_idx] = st.top();
    st.pop();
    if (neigh_idx == 0 && is_on_stack[node]) {
      // Βρήκαμε τον κύκλο. 
      long prev, idx = 0;
      do {
        prev = std::get<0>(st.top());
        index_in_cycle[prev] = cycle.size();
        cycle.push_back(prev);
        st.pop();
      } while (prev != node);
      return;
    }
    is_on_stack[node] = true;
    if (adj[node].size() > neigh_idx && adj[node][neigh_idx] == par) ++neigh_idx;
    if (adj[node].size() > neigh_idx) {
      st.push({ node, par, neigh_idx + 1 });
      st.push({ adj[node][neigh_idx], node, 0 });
    } else {
      is_on_stack[node] = false;
    }
  }
}

Η εύρεση του κύκλου χρειάζεται $\mathcal{O}(N)$ χρόνο και κάθε ερώτημα απαντάται σε $\mathcal{O}(C^2)$ χρόνο, όπου $C$ είναι το μήκος του κύκλου. Συνεπώς, συνολικά ο αλγόριθμος χρειάζεται $\mathcal{O}(NC^2)$ χρόνο, που είναι αρκετό για να περάσει το υποπρόβλημα.

Υποπρόβλημα 5

Σε αυτό το υποπρόβλημα το μήκος του κύκλου είναι λίγο πιο μεγάλο και θα προσπαθήσουμε να απαντήσουμε το κάθε ερώτημα σε $\mathcal{O}(C)$ χρόνο. Η βασική παρατήρηση που κάνουμε είναι η εξής:

Παρατήρηση: Έστω ότι έχουμε δύο κόμβους $i$ και $j$ με $w[i] - i > w[j] - j$. Για κάθε κόμβο $k$ με $k > i$ και $k > j$, έχουμε ότι συμφέρει να ταιριάξουμε τον $k$ με τον $i$ (αντί για τον $j$).

Αυτό προκύπτει γιατί $w[i] + w[k] + (k - i) > w[j] + w[k] + (k - j)$.

Συνεπώς, καθώς διατρέχουμε τον πίνακα κρατάμε τη μεγαλύτερη τιμή του $w[i] - i$ και την ταιριάζουμε με την τιμή του δείκτη $k$.

    if (index_in_cycle[i] == -1 || index_in_cycle[edges[i].second] == -1) {
      // Αν κάποια από τις δύο κορυφές δεν είναι στον κύκλο, τότε
      // ο γράφος δεν είναι συνδεδεμένος.
      fprintf(fo, "-1\n");
    } else {
      long u = i, v = edges[i].second;
      if (index_in_cycle[v] == (index_in_cycle[u] + 1) % cycle.size()) u = v;
      // Δοκιμάζουμε όλα τα δυνατά ζεύγη από κόμβους στον κύκλο:
      // Το μονοπάτι ξεκινάει στον j-οστό κόμβο στον κύκλο και καταλήγει στον jj-οστό.
      // Στους δύο ακριανούς κόμβους επιλέγουμε το μακρύτερο μονοπάτι. 
      long mx = 0;
      long best_score = w[u]; // Μέγιστο w[cycle[idx_j]] - j
      for (long k = 1; k < cycle.size(); ++k) {
        long idx_k = (index_in_cycle[u] + k) % cycle.size();
        long candidate = k + best_score + w[cycle[idx_k]] + 1;
        mx = std::max(mx, candidate);
        best_score = std::max(w[cycle[idx_k]] - k, best_score);
      }
      // Η απάντηση είναι η μέγιστη από το mx και την μεγαλύτερη απόσταση δύο κόμβων, 
      // που περιέχεται πλήρως σε κάποιο από τα υποδέντρα.
      fprintf(fo, "%ld\n", std::max(mx, mx_internal_dist));
    }
  }

Κάθε ερώτημα χρειάζεται $\mathcal{O}(C)$ χρόνο και συνολικά $\mathcal{O}(NC)$, που είναι αρκετό για να περάσει το υποπρόβλημα. Ολόκληρος ο κώδικας εδώ.

Πλήρης λύση

Για την πλήρη λύση θα απαντήσουμε όλα τα ερωτήματα στον κύκλο με ένα πέρασμα στον πίνακα. Η ιδέα είναι να βάλουμε δύο αντίγραφα του πίνακα το ένα δίπλα στο άλλο και για κάθε παράθυρο μεγέθους $C$ να βρούμε το μέγιστο άθροισμα $w[i] + w[j] + (i - j)$.

Για να το κάνουμε αυτό αποδοτικά κρατάμε ένα set με τα στοιχεία { w[i] + i, i } και ένα με τα στοιχεία { w[j] - j, j }. Σε κάθε βήμα, αφαιρούμε τα στοιχεία που είναι παλιά (δηλαδή έχουν $i$ με $i \leq k - C$) και θέλουμε να βρούμε το μέγιστο άθροισμα αυτών των δύο. Υπάρχουν οι εξής δύο περιπτώσεις:

Είναι το άθροισμα από τα δύο μέγιστα (αν οι δύο δείκτες είναι διαφορετικοί)
Είναι το άθροισμα από το ένα μέγιστο και το δεύτερο μέγιστο από το άλλο σύνολο.

Το set μας επιτρέπει να κάνουμε αυτές τις πράξεις σε $\mathcal{O}(\log C)$ χρόνο.

  for (long j = 0; j < 2 * cycle.size(); ++j) {
    long idx_j = j % cycle.size();
    long node_j = cycle[idx_j];
    pos.insert({ -(w[node_j] + j), j});
    neg.insert({ -(w[node_j] - j), j});
    if (j >= cycle.size()) {
      // Διορθώνουμε τα μικρότερα στοιχεία. 
      while (pos.begin()->second <= (j - cycle.size())) pos.erase(pos.begin());
      while (neg.begin()->second <= (j - cycle.size())) neg.erase(neg.begin());
      // Διορθώνουμε τα δεύτερα μικρότερα στοιχεία.
      while (second_best(pos)->second <= (j - cycle.size())) pos.erase(second_best(pos));
      while (second_best(neg)->second <= (j - cycle.size())) neg.erase(second_best(neg));
      
      long next_j = cycle[(idx_j + 1) % cycle.size()];
      long i = edges[node_j].second == next_j ? node_j : next_j;
      if (pos.begin()->second != neg.begin()->second) { // 1η περίπτωση
        ans[i] = 1 + -(pos.begin()->first + neg.begin()->first);  
      } else { // 2η περίπτωση
        ans[i] = 1 + -std::min(
          pos.begin()->first + second_best(neg)->first,
          neg.begin()->first + second_best(pos)->first);
      }
      ans[i] = std::max(ans[i], mx_internal_dist);
    }
  }
  

Συνολικά ο αλγόριθμος χρειάζεται $\mathcal{O}(N \log N)$ χρόνο και είναι αρκετό για να περάσει όλα τα testcases. Ολόκληρος ο κώδικας εδώ.