Αρχική > 31ος ΠΔΠ > lottery (εκφώνηση)

31ος ΠΔΠ Γ' Φάση: Τι πληρώνει το λαχείο (lottery) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

Ζητούμενο

Έστω ότι μας δίνονται δύο strings, το \(``stolismenos"\) και το \(``stolidi"\). Εν προκειμένω, το μέγιστο κοινό πρόθεμά τους (longest common prefix) είναι \(lcp(``stolismenos",``stolidi") = 5\), καθώς και τα δύο έχουν κοινό πρόθεμα το \(stoli\), αλλά το επόμενο γράμμα τους διαφέρει. Το πρόβλημα ορίζει ότι το κέρδος δύο κειμένων \(x\) και \(y\) είναι \(2^{lcp(x,y)}-1\).

Δίνονται \(N\) αριθμοί \(X_i\) με \(K\) ψηφία ο καθένας. Κατόπιν δίνονται \(Q\) ερωτήματα. Το κάθε ερώτημα \(q\) είναι ένας \(K\)-ψήφιος αριθμός. Η απάντηση στο κάθε ερώτημα \(q\) είναι ίση με το άθροισμα των κερδών του \(q\) έναντι των υπολοίπων \(N\) αριθμών. Πιο μαθηματικά, η απάντηση στο κάθε ερώτημα \(q\) είναι

\[\sum _{i=1}^{N} (2^{lcp(X_i,q)}-1)\]

Επειδή το αποτέλεσμα μπορεί να είναι πολύ μεγάλο, τυπώνουμε το υπόλοιπο της διαίρεσής του με το \(10^{9}+7\).

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

Λύσεις

Παρακάτω θα δούμε τις εξής λύσεις:

  1. Brute Force, πολυπλοκότητας \(\mathcal{O}(NQK)\), η οποία δεν απαιτεί καμμία άλλη γνώση.
  2. Σχεδόν βέλτιστη, πολυπλοκότητας \(\mathcal{O}((N+Q)K\log{N})\), χρειάζεται εξοικίωση με την binary search.
  3. Βέλτιστη, πολυπλοκότητας \(\mathcal{O}((N+Q)K)\), απαιτεί γνώση της δομής δεδομένων trie.

Brute Force, \(\mathcal{O}(QKN)\)

Για κάθε ένα από τα \(N\) κείμενα και για κάθε ένα από τα \(Q\) ερωτήματα, υπολογίζουμε το \(lcp\) των αντίστοιχων κειμένων. Από τη στιγμή που έχουμε το \(lcp\), υπολογίζουμε το \(2^{lcp}\) με την εντολή της \(C\):

long pow2(long lcp) {
  return (1<<lcp);
}

Η εντολή \(\ll\) πρόκειται για ένα bitwise shifting. Ο λόγος που υπολογίζει δυνάμεις του \(2\) είναι απλός. Σκεφτείτε ότι όταν πολλαπλασιάζετε οποιονδήποτε αριθμό \(x\) με τον αριθμό \(10\), απλώς προσθέτετε ένα μηδενικό στο τέλος της δεκαδικής αναπαράστασης του \(x\).

Το ίδιο ακριβώς πράγμα συμβαίνει αν γράψετε τον \(x\) σε δυαδικό και πολλαπλασιάσετε με \(2\). Όμως η διαδικασία του να προσθέσεις ένα μηδενικό στα δεξιά του \(x\) είναι ίδια με το να κυλήσεις τον \(x\) μία θέση αριστερά, δηλαδή \(x \ll 1\). Αφού \(x \ll 1 = x \cdot 2\), επαναλαμβάνουμε το ίδιο επιχείρημα κι έχουμε ότι \(x \ll y = x \cdot 2^{y}\), πράγμα που σημαίνει ότι \(1 \ll lcp = 1 \cdot 2^{lcp} = 2^{lcp}\).

Για να είμαστε πιο ακριβείς, υπάρχουν κάποια μικρά προβλήματα με τον παραπάνω κώδικα. Αρχικά προτιμούμε να δουλεύουμε με long long κι έτσι αντί για \(1\) πρέπει να γράψουμε 1LL. Επιπλέον δεν έχουμε πάρει το υπόλοιπο της διαίρεσης με το \(10^9+7\) όπως μας ζητάει η εκφώνηση. Τέλος, αν η απάντηση που μας ζητείται είναι πολύ μεγάλη (πχ \(2^{100}\)), τότε δε μας αρκούνε ούτε οι long long. Για το λόγο αυτό, αν \(lcp>60\), λέμε ότι \(2^{lcp} = 2^{60} * 2^{lcp-60}\), κι έτσι υπολογίζουμε τα δύο σκέλη ξεχωριστά, βρίσκουμε το υπόλοιπο τους με το \(10^9+7\) ώστε να μικρύνουν, και κατόπιν τα πολλαπλασιάζουμε (και ξαναβρίσκουμε το υπόλοιπο). Εδώ φαίνεται και ο λόγος που προτιμήσαμε τους long long αριθμούς, καθώς μπορεί να χρειαστεί να πολλαπλασιάσουμε δύο αριθμούς της τάξης του \(10^9\). Σημειώνουμε ότι το τελευταίο τρικ στηρίζεται στο γεγονός:

\[(a \cdot b) \% MOD = ( (a \% MOD) \cdot (b \% MOD) ) \% MOD\]

Καταλήγουμε στον εξής τρόπο να υπολογίζουμε δυνάμεις του \(2\):

const long MOD = 1e9+7;

long long pow2(long k) {
  if (k<=60) return (1LL<<k)%MOD;
  return ( ((1LL<<60)%MOD) * ((1LL<<(k-60))%MOD) ) % MOD;
}

Ολοκληρωμένος ο κώδικας της λύσης παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
const long MOD = 1e9+7;
using namespace std;

long N, K, Q;
vector<string> X;
string strQ;

long long pow2(long k) {
  if (k<=60) return (1LL<<k)%MOD;
  return ( ((1LL<<60)%MOD) * ((1LL<<(k-60))%MOD) ) % MOD;
}

int main()
{
  string tmp;
  freopen("lottery.in","r",stdin);
  freopen("lottery.out","w",stdout);
  cin >> K >> N >> Q;
  X.push_back(" ");
  for(long i=1; i<=N; ++i) {
    cin >> tmp;
    reverse(tmp.begin(), tmp.end());
    X.push_back(tmp);
  }
  
  for(long i=1; i<=Q; ++i) {
    cin >> strQ;
    reverse(strQ.begin(), strQ.end());
    
    long long s = 0;
    long nwin = 0;
    for(long j=1; j<=N; ++j) {
      long k;
      for(k=0; k<K && strQ[k] == X[j][k]; ++k);
      if (k>0) {
	s = (s+pow2(k)-1) % MOD;
	++nwin;
      }
    }
    cout << nwin << ' ' << s << '\n';
  }
  return 0;
}

Σχεδόν βέλτιστη \(\mathcal{O}((N+Q)K\log{N})\)

Η παρακάτω λύση χρειάζεται μία καλή εξοικίωση με την binary search.

Αρχικά, παρατηρούμε ότι δεν υπάρχει λόγος να κρατήσουμε τα \(N\) κείμενα στη σειρά με την οποία δόθηκαν. Αντ’ αυτού, τα ταξινομούμε.

Κατόπιν, θα προσπαθήσουμε να υπολογίσουμε πόσα κείμενα έχουν \(lcp(X_i,q)\ge 1\) (έστω \(n_1\)), πόσα \(\ge 2\) (έστω \(n_2\)), κλπ. Αν βρούμε αυτές τις απαντήσεις, το πρόβλημα λύνεται εύκολα. Αφού υπάρχουν \(n_1\) κείμενα με \(lcp(X_i,q)\ge 1\), και \(n_2\) με \(\ge 2\), τότε υπάρχουν ακριβώς \(n_1-n_2\) με \(lcp(X_i,q)=1\). Προσέξτε ότι τα κείμενα που έχουν \(lcp(X_i,q) \ge j\), για οποιοδήποτε \(j\), είναι ακριβώς αυτά τα κείμενα που τα πρώτα τους \(j\) γράμματα είναι ίδια με του \(q\).

Θεωρώντας ότι γνωρίζουμε όλα τα \(n_i\) υπολογίζουμε την απάντηση ως:

\[\sum_{j=1}^{K} (n_{j} - n_{j+1}) \cdot (2^{j}-1)\]

Σημείωση: Χωρίς να είναι απαραίτητο, ισχύει επίσης ότι το παραπάνω είναι ίσο με \(\sum_{j=1}^{K} n_{j} \cdot (2^{j}-2^{j-1})\), το οποίο και χρησιμοποιούμε στον κώδικα. Αυτό προκύπτει απλώς αναδιατάσσοντας τους όρους του αθροίσματος.

Το μόνο που απομένει είναι να υπολογίσουμε τους όρους \(n_{j}\). Εφόσον τα κείμενα είναι ταξινομημένα, μπορούμε με μία binary search να βρούμε το μικρότερο από αυτά των οποίων τα πρώτα \(K\) γράμματα είναι ίδια με του \(q\), και με άλλη μία binary search το μεγαλύτερο από αυτά. Όλα τα ενδιάμεσα κείμενα (και μόνο αυτά) έχουν το ζητούμενο μέγιστο κοινό πρόθεμα.

Η ταξινόμηση των κειμένων κοστίζει \(\mathcal{O}(NK\log{N})\) καθώς η κάθε σύγκριση χρειάζεται χρόνο \(\mathcal{O}(K)\), που είναι το μέγεθος των κειμένων. Η κάθε μία από τις \(\mathcal{O}(Q)\) binary searches χρειάζεται χρόνο \(\mathcal{O}(K\log{N})\) (\(\mathcal{O}(\log{N})\) συγκρίσεις που η κάθε μία χρειάζεται \(\mathcal{O}(K)\) χρόνο). Συνεπώς η ολική πολυπλοκότητα είναι \(\mathcal{O}((N+Q)K\log{N})\).

Ολοκληρωμένος ο κώδικας της λύσης παρουσιάζεται παρακάτω.

Σημειώσεις: Ο βασικός λόγος που τονίστηκε ότι χρειαζόμαστε καλή εξοικίωση με τη binary search είναι κάποια λεπτά σημεία της που αν δε τα υλοποιήσουμε σωστά, θα πέσουμε σε ατέρμονα βρόγχο. Στο συγκεκριμένο πρόβλημα εμφανίζονται όλα αυτά. Για μια αναλυτική εξήγηση δείτε και εδώ.

Επειδή υπάρχει περίπτωση όλα τα κείμενα να είναι μικρότερα από αυτό που ψάχνουμε (ή όλα μεγαλύτερα), εφαρμόζουμε ένα κλασικό τρικ: Προσθέτουμε μία πολύ μικρή τιμή, και μία πολύ μεγάλη τιμή, στα δύο άκρα του πίνακα, ώστε να μη χρειάζεται να ελέγχουμε οριακές περιπτώσεις. Γιατί χρειάζεται αυτό; Σκεφτείτε ένα πολύ απλό παράδειγμα: Αν υπήρχε μόνο ένα κείμενο (\(N==1\)), τότε οποιαδήποτε binary search θα επέστρεφε τη θέση \(1\), και θα ήθελε έξτρα έλεγχο για να δούμε αν αυτό το κείμενο πληροί τις προδιαγραφές που θέλουμε ή όχι. Με το τρικ που προτείνουμε, αν το κείμενο δεν πληροί τις προδιαγραφές, η binary search θα επιστρέψει τη θέση \(0\) ή τη θέση \(N+1\) (ανάλογα με το αν είναι μικρότερο από αυτό που χρειαζόμασταν ή μεγαλύτερο), ενώ αν τις πληροί, θα επιστραφεί η ίδια η θέση του.

Επιπλέον προσέξτε ότι όταν διαλέγουμε την ενδιάμεση θέση, στην περίπτωση που απομένουν μόνο δύο στοιχεία, πρέπει να προσδιορίσουμε ποιο από τα δύο θέλουμε να θεωρηθεί ως ενδιάμεσο (διότι δεν υπάρχει καμμία ενδιάμεση θέση). Αυτό είναι απαραίτητο να γίνει με προσοχή, όπως στον παρακάτω κώδικα που στη μία συνάρτηση έχουμε:

mid = (low+high) / 2; //in case of 2 elements, this code picks mid=low

και στην άλλη:

mid = (low+high+1) / 2; //in case of 2 elements, this code picks mid=high

Η απόφαση βασίζετε στις επόμενες εντολές. Αν ακολουθεί low=mid+1 τότε θέλουμε να διαλέγουμε το \(low\), ενώ αν έχουμε high=mid-1 τότε θέλουμε το \(high\). Αλλιώς μπορεί να πέσουμε σε ατέρμονα βρόγχο.

Τα παραπάνω αποτελούν απλά έτοιμες συμβουλές που μπορείτε να ακολουθείτε. Όμως η ομορφιά κρύβεται στο γιατί πρέπει να τις ακολουθείτε. Προτείνουμε να δοκιμάσετε να φανταστείτε παραδείγματα με \(2\) μόνο στοιχεία, όπου η μία μέθοδος θα τερμάτιζε, κι η άλλη όχι. Μετά από πέντε λεπτά σκέψης, να διαβάσετε εδώ.

#include <bits/stdc++.h>
const long MOD = 1e9+7;
using namespace std;

long N, K, Q;
vector<string> X;
string strQ;

long long pow2(long k) {
  if (k<=60) return (1LL<<k)%MOD;
  return ( ((1LL<<60)%MOD) * ((1LL<<(k-60))%MOD) ) % MOD;
}

long FirstWithLCP(long k) {
  long low=0, high=N+1, mid, i;
  while(low<high) {
    mid = (low+high)/2;
    for(i=0; i<k && X[mid][i] == strQ[i]; ++i);
    if(i==k || X[mid][i] > strQ[i]) high = mid;
    else low=mid+1;
  }
  return low;
}

long LastWithLCP(long k) {
  long low=0, high=N+1, mid, i;
  while(low<high) {
    mid = (low+high+1)/2;
    for(i=0; i<k && X[mid][i] == strQ[i]; ++i);
    if(i==k || X[mid][i] < strQ[i]) low = mid;
    else high=mid-1;
  }
  return low;
}

int main()
{
  string tmp;
  freopen("lottery.in","r",stdin);
  freopen("lottery.out","w",stdout);
  cin >> K >> N >> Q;
  X.push_back(" ");
  X[0][0] = '0'-1; //smaller than everything
  for(long i=1; i<=N; ++i) {
    cin >> tmp;
    reverse(tmp.begin(), tmp.end());
    X.push_back(tmp);
  }
  sort(X.begin()+1, X.begin()+N+1);
  X.push_back(" ");
  X[N+1][0] = '9'+1; //bigger than everything
  
  for(long i=1; i<=Q; ++i) {
    cin >> strQ;
    reverse(strQ.begin(), strQ.end());
    
    long long s = 0;
    long nwin = 0;
    for(long k=1; k<=K; ++k) {
      long x = FirstWithLCP(k);
      long y = LastWithLCP(k);
      if (k==1) nwin = (y-x+1);
      s = (s + (y-x+1)*(pow2(k)-pow2(k-1))) % MOD;
      if (s<0) s+= MOD;
    }
    cout << nwin << ' ' << s << '\n';
  }
  return 0;
}

Βέλτιστη λύση \(\mathcal{O}((N+Q)K)\)

Η λύση αυτή απαιτεί γνώση της δομής δεδομένων trie.

Πατώντας πάνω στην προηγούμενη λύση, αρκεί να υπολογίσουμε όλες τις τιμές \(n_j\), δηλαδή για κάθε \(j\), το πλήθος των κειμένων \(X_i\) που έχουν τα πρώτα τους \(j\) γράμματα ίδια με του ερωτήματος \(q\).

Για το λόγο αυτό, οργανώνουμε και τα \(N\) κείμενα \(X_i\) σε ένα trie, σε γραμμικό ως προς το μέγεθός τους χρόνο \(\mathcal{O}(NK)\). Σε κάθε κόμβο του trie, κρατάμε πόσες φορές έχει εμφανιστεί κάποια λέξη που διέρχεται από τον κόμβο αυτό. Με άλλα λόγια, κρατάμε το πλήθος των κειμένων που έχουν πρόθεμα αυτό που αντιστοιχεί στο μονοπάτι από τη ρίζα ως τον κόμβο.

Κατόπιν προσπαθούμε να εντοπίσουμε τη λέξη \(q\) μέσα στο trie. Οι κόμβοι από τους οποίους περνάμε σε αυτή την αναζήτηση κρατάνε ακριβώς την πληροφορία που ζητάμε. Ο πρώτος κόμβος κρατάει το \(n_1\), ο δεύτερος το \(n_2\), κι ούτω καθεξής.

Οι \(Q\) διασχίσεις του trie κοστίζουν \(\mathcal{O}(K)\) χρόνο η κάθε μία, κι έτσι η ολική πολυπλοκότητα είναι \(\mathcal{O}((N+Q)K)\).

#include <bits/stdc++.h>
const long MOD = 1e9+7;
const long MAXC = 1e6;
using namespace std;

long N, K, Q, newValue, cnt[MAXC+5];
long neib[MAXC+5][10];

long long pow2(long k) {
  if (k<=60) return (1LL<<k)%MOD;
  return ( ((1LL<<60)%MOD) * ((1LL<<(k-60))%MOD) ) % MOD;
}

int main()
{
  string tmp;
  long curr;
  freopen("lottery.in","r",stdin);
  freopen("lottery.out","w",stdout);
  cin >> K >> N >> Q;
  for(long i=1; i<=N; ++i) {
    curr = 0;
    cin >> tmp;
    reverse(tmp.begin(), tmp.end());

    //Inserting tmp into the trie
    for(long k=0; k<K; ++k) {
      if ( !neib[curr][ tmp[k]-'0' ] )
	neib[curr][ tmp[k]-'0' ] = ++newValue;
      curr = neib[curr][ tmp[k]-'0' ];
      ++cnt[curr];
    }
  }
  
  for(long i=1; i<=Q; ++i) {
    cin >> tmp;
    reverse(tmp.begin(), tmp.end());
    
    long long s = 0;
    long nwin = 0;
    curr = 0;

    //Traversing the trie, trying to match tmp
    for(long k=0; k<K; ++k) {
      if ( !neib[curr][ tmp[k]-'0' ] )
	break;
      curr = neib[curr][ tmp[k]-'0' ];
      if (k==0) nwin = cnt[curr];
      s = (s + cnt[curr]*(pow2(k+1)-pow2(k))) % MOD;
      if (s<0) s+= MOD;
    }
    cout << nwin << ' ' << s << '\n';
  }
  return 0;
}