37ος ΠΔΠ : Μονοπάτι μανιταριών (shroompath) - Λύση

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

Έχουμε όλους τους δυνατούς συνδυασμούς των γραμμάτων α και β σε συμβολοσειρές μήκους \(1,2,3,\dots\)
Για κάθε ξεχωριστό μήκος, οι συμβολοσειρές είναι ταξινομημένες αλφαβητικά. Όλες οι συμβολοσειρές που προκύπτουν, κολλάνε μεταξύ τους (χωρίς κενά ενδιάμεσα) παράγοντας μια ατέρμονη συμβολοσειρά.

Για κάθε γράμμα α ή β έχουμε ένα συγκεκριμένο βάρος (\(X\) και \(Y\) αντίστοιχα). Zητείται πότε θα έχουμε συγκεντρώσει συνολικό βάρος μεγέθους τουλάχιστον \(S\) ως άθροισμα συνεχόμενων ίδιων γραμμάτων α ή β.

Παρατήρηση 1: εφόσον θέλουμε το βάρος \(S\) να αποτελείται αποκλειστικά από ίδια γράμματα (έστω \(A\) γράμματα α ή \(B\) γράμματα β), αρκεί να διαιρέσουμε το βάρος \(S\) με το βάρος \(X\) ή \(Y\) στρογγυλοποιώντας προς τα πάνω, για να υπολογίσουμε τα \(A\) και \(B\). Στα μαθηματικά ο συμβολισμός για τη στρογγυλοποίηση προς τα πάνω είναι \(A = \lceil S/X \rceil, B = \lceil S/Y \rceil\).

Στη c++ γνωρίζουμε ότι η ακέραια διαίρεση αγνοεί τυχόν δεκαδικά ψηφία, οπότε για το \(A\), αρκεί να κάνουμε τον υπολογισμό \(A = (S+X-1)/X\) (δηλαδή αυξάνουμε τόσο το \(S\), ώστε να αυξήσει το πηλίκο αν και μόνο αν η διαίρεση του \(S\) με το \(X\) δεν είναι τέλεια)¹.

Υποπρόβλημα 1 (\(S\le 15\))

Στο υποπρόβλημα αυτό θα χρειαστεί να εξερευνήσουμε τις συμβολοσειρές με μήκος \(1,2,\dots ,S\), καθώς ο πρώτος συνδυασμός συμβολοσειρών μήκους \(S\) αποτελείται από \(S\) α και ο τελευταίος από \(S\) β. Μάλιστα αν τα \(X\) και \(Y\) είναι μεγαλύτερα από \(1\), θα καταφέρουμε να συγκεντρώσουμε βάρος \(S\) ακόμα πιο γρήγορα. Ακολουθούν δύο τρόποι για να υπολογίσουμε όλους τους συνδυασμούς, με αναδρομή και με επαναληπτικό βρόχο.

Αναδρομικά: Βρίσκουμε όλους τους συνδυασμούς για κάθε μήκος συμβολοσειράς και τους προσθέσουμε σε έναν πίνακα χαρακτήρων Z.

const char shrooms[] = "ab";//επιτρεπτοί χαρακτήρες
void add_length_w(vector<char>& str,int pos){
    //υπολόγισε όλους τους συνδυασμούς ξεκινώντας από τη θέση pos
    if(pos == str.size()){//καλύφθηκε το επιθυμητό μήκος
        Z.insert(Z.end(),str.begin(),str.end());
        return;
    }
    for(int i=0;shrooms[i]!=0;i++){
        str[pos] = shrooms[i];
        add_length_w(str,pos+1);
    }
}

Δείτε ολόκληρο τον κώδικα εδώ.

Κατόπιν με τη χρήση της συνάρτησης search της βιβλιοθήκης algorithm βρίσκουμε την πρώτη θέση που ξεκινούν τα \(A\) συνεχόμενα α ή τα \(B\) συνεχόμενα β που αναζητούμε.

    if(A>0){
        vector<char> f(A,'a');
        long pos = search(Z.begin(), Z.end(), f.begin(), f.end()) - Z.begin();
        ans = min(ans,pos+A);
    }
    if(B>0){
        vector<char> f(B,'b');
        long pos = search(Z.begin(), Z.end(), f.begin(), f.end()) - Z.begin();
        ans = min(ans,pos+B);
    }

Παρατήρηση 2: Το πλήθος των συμβολοσειρών μήκους \(i\) από τα δύο γράμματα, είναι \(2^i\) (εφόσον κάθε θέση μπορεί να έχει \(2\) τιμές). Τα α και β μπορούν να θεωρηθούν ως οι αριθμοί \(0\) και \(1\) του δυαδικού συστήματος και η παραγόμενη συμβολοσειρά να είναι η αλληλουχία όλων των μη μηδενικών φυσικών αριθμών απεικονισμένων στο δυαδικό σύστημα.

Με επαναληπτικό βρόχο: Χρησιμοποιώντας την παρατήρηση 2, μπορούμε να κατασκευάσουμε τις συμβολοσειρές με έναν επαναληπτικό βρόχο ως εξής:

void add_length_w(int w){
    for(int i=0;i < (1<<w);i++)//1<<w == 2^w 
        for(int j=w-1;j>=0;j--)
            Z.push_back((i & (1<<j))?'b':'a');
}

Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ. Η λύση με αναδρομή ή επαναληπτικό βρόχο, χρειάζεται \(\mathcal{O}(S\cdot 2^S)\) χρόνο.

Υποπρόβλημα 2 (\(Χ\gt Y\))

Εφόσον οι χαρακτήρες τύπου α έχουν μεγαλύτερο βάρος, θα προλάβουμε να συγκεντρώσουμε το συνολικό βάρος \(S\) με αυτά. Οι χαρακτήρες β δεν θα μας χρησιμεύσουν.

Παρατήρηση 3: Για οποιοδήποτε μήκος \(w\) συμβολοσειρών με \(w\gt 1\), η πρώτη συμβολοσειρά αποτελείται από \(w\) α και η επόμενη από \(w-1\) α και ένα β. Σε καμία άλλη θέση δεν έχουμε τόσα α συγκεντρωμένα.

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

long calc_a(int A){
    ll pow2 = 1;//2^0
    ll prev=0;//άθροισμα μανιταριών που προσπεράσαμε στα προηγούμενα μήκη
    for(long i=1;;i++){
        pow2 = (pow2 * 2) % mod;//2^i
        if(A<=2*i-1) return (prev + A) % mod;
        prev = (prev + pow2*i) % mod;
    }
    return -1L;
}

Ο χρόνος που χρειάζεται αυτή η λύση είναι \(\mathcal{O}(S)\). Ολόκληρος ο κώδικας εδώ.

Υποπρόβλημα 3 (\(Χ=0\))

Στο υποπρόβλημα αυτό, τα α έχουν μηδενικό βάρος και δεν χρησιμεύουν. Παρατηρώντας την παρακάτω εικόνα είναι φανερό ότι η μέγιστη συγκέντρωση από β βρίσκεται στο μέσο σχεδόν των συμβολοσειρών μήκους \(B\). Πιο συγκεκριμένα, οι πρώτες μισές συμβολοσειρές έχουν α στην πρώτη θέση και οι επόμενες μισές έχουν β στην πρώτη θέση. Η τελευταία συμβολοσειρά με α πρώτο χαρακτήρα, έχει \(B-1\) χαρακτήρες β να ακολουθούν και αμέσως μετά ακολουθεί η πρώτη συμβολοσειρά με ένα β στην πρώτη θέση. Αυτή είναι και η θέση που καταφέρνουμε να συγκεντρώσουμε τα \(B\) β, δηλαδή μια θέση μετά τους μισούς χαρακτήρες των συνδυασμών μήκους \(B\).

long calc_b(int B){
    ll pow2 = 1;//2^0
    ll prev=0;//άθροισμα μανιταριών που προσπεράσαμε στα προηγούμενα μήκη
    for(long i=1;;i++){
        if(i==B) return (prev + pow2*i + 1) % mod;
        pow2 = (pow2 * 2) % mod;//2^i
        prev = (prev + pow2*i) % mod;
    }
    return -1L;
}

Ο χρόνος που χρειάζεται η λύση αυτή είναι \(\mathcal{O}(S)\). Ολόκληρος ο κώδικας εδώ.

Πλήρης λύση σε χρόνο \(\mathcal{O}(S)\)

Εφόσον γνωρίζουμε τις συγκεντρώσεις \(A\) ή \(B\) που χρειαζόμαστε για βάρος \(S\), πρέπει να βρούμε μετά από πόσους χαρακτήρες θα τις καταφέρουμε. Οι χαρακτήρες α και β όμως είναι τόσα πολλοί που ξεπερνούν τα όρια των ακεραίων τύπων που παρέχει η c++ και δεν μπορούμε να αποθηκεύσουμε τις θέσεις που τα βρήκαμε παρά μόνο αν αποθηκεύσουμε τα υπόλοιπα των θέσεων με κάποιον διαιρέτη όπως το \(10^9+7\) που μας δίνει η εκφώνηση. Η διάταξη των θέσεων έχει χαθεί από τη στιγμή που κρατάμε μόνο τα υπόλοιπα τους, οπότε υπολογίζουμε προοδευτικά τους συνδυασμούς α και β που συναντάμε και σταματάμε μόλις βρούμε την πρώτη λύση.

long calc(int A, int B){
    ll pow2 = 1;
    ll prev=0;//σύνολο μανιταριων που προσπερασαμε
    for(int i=1;;i++){//για όλα τα πλάτη απο 1 έως ...
        if(A<=2*i-1) return (prev + A) % mod;
        if(i == B) return (prev + pow2*i + 1) % mod; 
        pow2 = (pow2 * 2) % mod;
        prev = (prev + pow2*i) % mod;
    }
    return -1L;
}

Ολόκληρος ο κώδικας εδώ.

Αν όμως αξιοποιήσουμε την πληροφορία ότι τους \(B\) χαρακτήρες β τους συναντάμε στις συμβολοσειρές μήκους \(B\), είναι φανερό ότι μέχρι και \(2\cdot B-1\) χαρακτήρες α, τους βρίσκουμε νωρίτερα από τους \(B\) β.

Ενώνοντας τις λύσεις των δύο προηγούμενων υποπροβλημάτων, έχουμε:

long calc(int s,int x,int y){
    long A = x ? ((s+x-1)/x) : mod;
    long B = y ? ((s+y-1)/y) : mod;
    if(B*2-1>=A)
        return calc_a(A);
    else 
        return calc_b(B);
}

Ολόκληρος ο κώδικας εδώ. Οι παραπάνω λύσεις χρειάζονται χρόνο \(\mathcal{O}(S)\).

Πλήρης λύση σε χρόνο \(\mathcal{O}(\log_2{S})\)

Ο αριθμός των χαρακτήρων από όλους τους συνδυασμούς ενός μόνο πλάτους \(k\), δίνεται από τη συνάρτηση
\(f(k) = 2^k \cdot k\). Ο υπολογισμός του συνόλου των χαρακτήρων μέχρι και το πλάτος \(k\), δίνεται από τη συνάρτηση \(p(k) = f(1)+f(2)+\dots+f(k)=\sum_{i=1}^{k}f(i) = \sum_{i=1}^{k} {i\cdot 2^i}\).

Η συνάρτηση αυτή μπορεί να υπολογισθεί με \(p(k) = 2^{k+1}\cdot (k-1)+2\)

Απόδειξη: Θα χρησιμοποιήσουμε επαγωγή. Για \(k=1\), έχουμε \(p(1) = 2^{1+1}\cdot (1-1) +2 = 2\) το οποίο ισχύει (έχουμε \(2\) χαρακτήρες, ένα α και ένα β στους συνδυασμούς με μήκος \(1\)).
Έστω ότι ισχύει για κάποιο \(k\), δηλαδή \(p(k) = 2^{k+1}\cdot (k-1)+2\), θα αποδείξουμε ότι ισχύει και για το \(k+1\), δηλαδή:

Γνωρίζουμε ότι

άρα καταλήγουμε ότι ισχύει η \(p(k+1)\), άρα η σχέση μας ισχύει για όλα τα \(k\ge1\).

Ο υπολογισμός της δύναμης με τη συνάρτηση pow2 στην παραπάνω λύση, χρειάζεται λογαριθμικό χρόνο ως προς τον εκθέτη (μέγιστος εκθέτης ο \(S\)), οπότε ο χρόνος που χρειάζεται συνολικά η λύση είναι \(\mathcal{O}(\log_2{S})\). Ο σχετικός κώδικας ακολουθεί:

ll f(long w){ return (pow2(w)*w)%mod; }

ll p(long w){ return (pow2(w+1)*(w-1)+2) % mod; }

long calc(int s,int x,int y){
    long A = x ? ((s+x-1)/x) : mod;
    long B = y ? ((s+y-1)/y) : mod;
    if(B*2-1>=A){
        return (p(A/2) + A)%mod;
    }else{
        ll w = f(B);
        //το w πρέπει να είναι άρτιος ώστε να μπορεί να διαιρεθεί με το 2
        if(w & 1)w+=mod;//αν w περιττός, μετέτρεψε το σε ισοδύναμο (ως προς mod) άρτιο
        return (p(B-1) + w/2+1)%mod;
    }
}

Ολόκληρος ο κώδικας εδώ