25ος ΠΔΠ B' Φάση: Οι μυστικοί αριθμοί (scidinner) - Λύση

Προαπαιτούμενες γνώσεις: αναπαράσταση δένδρων και αναζήτηση DFS.

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

Μας δίνονται \(M\) σχέσεις της μορφής \(x \to y\), που σημαίνει ότι ο αριθμός του \(x\) (ας τον ονομάζουμε \(n_x\)), διαιρεί τον αριθμό του \(y\), δηλαδή \(n_x \mid n_y\). Αυτές οι σχέσεις ορίζουν έναν κατευθυνόμενο γράφο. Παρακάτω θα δείξουμε ότι ο γράφος αυτός είναι μία συλλογή από δένδρα και ότι το πλήθος των ομάδων που χρειάζονται είναι ίσο με το μήκος του μεγαλύτερου μονοπατιού σε αυτά τα δένδρα.

Μαθηματική απόδειξη

Θα αποδείξουμε κάποιες ιδιότητες που έχει αυτός ο γράφος.

Παρατήρηση 1: Αν υπάρχει ένα μονοπάτι από το \(a_1 \to \ldots \to a_k\), τότε \(a_1 \mid a_k\).

Απόδειξη Η ύπαρξη του μονοπατιού μας δίνει ότι \(a_1 \mid a_2\), \(a_2 \mid a_3\), … , \(a_{k-1} \mid a_k\). Κάθε μία από αυτές τις σχέσεις σημαίνει ότι υπάρχει σταθερά \(c_i\) ώστε \(a_{i+1} = c_i a_{i}\). Συνεπώς,

Επομένως, το \(a_1 \mid a_k\).

Παρατήρηση 2: Ο γράφος δεν έχει κύκλο.

Απόδειξη Η εκφώνηση μας λέει ότι δεν υπάρχουν δύο επιστήμονες με τους ίδιους αριθμούς. Αν υπήρχε κύκλος, έστω \(a_1 \to \ldots \to a_k \to a_1\), τότε από την παραπάνω παρατήρηση \(a_1 \mid a_k\) και \(a_k \mid a_1\). Επομένως, \(a_1 = a_k\), άτοπο.

Συνεπώς, αυτό αποδεικνύει ότι έχουμε έναν γράφο που είναι κατευθυνόμενος και ακυκλικός. Επειδή μας δίνεται ότι δεν υπάρχουν \(x_1\) και \(x_2\) ώστε \(x_1 \to y\) και \(x_2 \to y\), αυτό σημαίνει ότι ο γράφος μας αποτελείται μόνο από δένδρα. Τώρα θα δείξουμε ότι το ελάχιστο πλήθος των δυνατών ομάδων είναι ίσο με το μέγεθος του μεγαλύτερου μονοπατιού σε κάποιο δένδρο, το οποίο ονομάζουμε \(\mathrm{max\_path}\).

Παρατήρηση 3: Δεν μπορούμε να φτιάξουμε λιγότερες από \(\mathrm{max\_path}\) ομάδες.

Ας υποθέσουμε ότι έχουμε λιγότερες από \(\mathrm{max\_path}\) ομάδες. Αν κοιτάξουμε τους \(\mathrm{max\_path}\) αριθμούς στο μεγαλύτερο μονοπάτι, τότε θα υπάρχουν δύο από αυτούς \(x\) και \(y\) στην ίδια ομάδα. Αλλά τότε \(x \mid y\) (ή \(y \mid x\)), που δεν επιτρέπεται. Άρα δεν μπορύμε να έχουμε λιγότερες από \(\mathrm{max\_path}\) ομάδες.

Παρατήρηση 4: Μπορούμε να χωρίσουμε τους επιστήμονες σε \(\mathrm{max\_path}\) ομάδες.

Απόδειξη Πρέπει να βρούμε αριθμούς ώστε να δείξουμε ότι για δύο επιστημόνες της ίδιας ομάδας, δεν γίνεται ο αριθμός του ενός να διαιρεί τον αριθμό του άλλου. Η ιδέα είναι να χωρίσουμε τους αριθμούς ανάλογα με το βάθος τους στο δένδρο. Για το παράδειγμα, τα βάθη δίνονται ως εξής:

και οι ομάδες που θέλουμε να τα χωρίσουμε είναι οι εξής:

Διαλέγουμε \(N\) διαφορετικούς πρώτους αριθμούς \(p_1, \ldots, p_N\). Ορίζουμε τον αριθμό \(n_v\) για κάθε επιστήμονα ως \(n_v = n_u \cdot p_v\) όπου \(n_u\) είναι ο αριθμός του πατέρα του στο δένδρο ή \(1\) αν δεν έχει πατέρα. Στο παράδειγμα αν \(p_1 = 2\), \(p_2 = 3\), \(p_3 = 5\), \(p_4 = 7\), \(p_5 = 11\), \(p_6 = 11\), \(p_7 = 13\), \(p_8 = 17\), \(p_9 = 19\), \(p_{10} = 23\), \(p_{11} = 29\), \(p_{12} = 31\), τότε τα \(n_v\) δίνονται στο παρακάτω διάγραμμα:

Τώρα πρέπει να ελέγξουμε ότι για δύο μέλη της ίδιας ομάδας, πχ το \(k\) και \(\ell\), τότε \(v_k \nmid v_{\ell}\). O μοναδικός τρόπος ώστε \(v_k \mid v_{\ell}\), είναι αν \(p_k \mid v_{\ell}\). Αφού το \(p_k\) είναι μοναδικός πρώτος, για να διαιρεί το \(v_{\ell}\) σημαίνει ότι υπάρχει ένα μονοπάτι από το \(k\) στο \(\ell\), που δεν μπορεί να ισχύει, αφού το \(k\) και \(\ell\) είναι στο ίδιο βάθος του δένδρου.

Αν ο γράφος, δεν είναι συνεκτικός μπορούμε να ενώσουμε τις ομάδες από μη-συνδεδεμένα υπογραφήματα, αφού οι επιστήμονες αυτών δεν αλληλεπιδρούν.

Υλοποίηση

Επομένως, το πρόβλημα ανάγεται στο να βρούμε το μέγιστο μονοπάτι σε μερικά δένδρα. Αυτό μπορούμε να το κάνουμε με χρήση DFS, είτε αναδρομικά είτε γραμμικά. Ο γραμμικός τρόπος έχει το πλεονέκτημα ότι χρησιμοποιεί μικρότερη στοίβα κλήσεων (διαφορά τεσσάρων testcases στον διαγωνισμό). Μπορούμε να βρούμε την ρίζα ενός δένδρου ως τον κόμβο που δεν έχει καμία εισερχόμενη ακμή και επομένως να ξεκινήσουμε την DFS από εκεί.

Σε κάθε περίπτωση θεωρούμε ότι έχουμε βρει το μήκος \(m\) του μονοπατιού έως τον κόμβο \(u\) και μετά το μήκος του μονοπατιού για κάθε παιδί \(v\) του \(u\), είναι \(m + 1\). Βρίσκουμε το μεγαλύτερο μήκος και αυτό είναι η απάντηση. Είτε το υλοποίησουμε αναδρομικά είτε γραμμικά, ο χρόνος εύρεσης του μεγαλύτερου μονοπατιού θέλει \(\mathcal{O}(N + (N-1)) = \mathcal{O}(N)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.

Αναδρομική υλοποίηση

#include <cstdio>
#include <vector>

const size_t MAXN = 1'000'000;

std::vector<long> v[MAXN+1];
bool has_parent[MAXN + 1];
long max_path_len;

void dfs(long u, long path_len) {
   if (path_len > max_path_len) 
       max_path_len = path_len;
   for (const auto neigh : v[u])
      dfs(neigh, path_len + 1);
}

int main() {
   long N, M;
   FILE *fi = fopen("scidinner.in", "r");
   fscanf(fi, "%ld%ld", &N, &M);
   for (long i = 0; i < M; ++i) {
      long a, b;
      fscanf(fi, "%ld%ld", &a, &b);
      v[a].push_back(b);
      has_parent[b] = true;
   }
   fclose(fi);
   
   for (long i = 1; i <= N; ++i)
      if (!has_parent[i])
         dfs(i, 1);
   
   FILE *fo = fopen("scidinner.out", "w");
   fprintf(fo, "%ld\n", max_path_len);
   fclose(fo);
   
   return 0;
}

Γραμμική υλοποίηση

Η γραμμική υλοποίηση χρησιμοποιεί την δομή δεδομένων stack και με αυτό τον τρόπο αποφεύγει να δημιουργηθεί μία μεγαλή στοίβα κλήσεων όπως γίνεται με την dfs().

void dfsIterative(long begin) {
   std::stack<std::pair<long /* node */, long /* path length */>> s;
   s.push({ begin, 1 });
   while(!s.empty()) {
      auto [node, path_len] = s.top();
      s.pop();
      if (path_len > max_path_len)
         max_path_len = path_len;
      for (const auto neigh : v[node])
         s.push({ neigh, path_len + 1 });
   }
}

Σημείωση: Μπορείτε να δείτε μία πιο δύσκολη παραλλαγή του προβλήματος εδώ, στην οποία δεν ισχύει η συνθήκη ότι δεν υπάρχουν δύο \(x_1\) και \(x_2\) ώστε \(x_1 \to y\) και \(x_2 \to y\).