31ος ΠΔΠ B' Φάση: Ισορροπημένες παρενθέσεις (cntbal) - Λύση

Συγγραφέας: Γιώργος Γιαπιτζάκης

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

Μας δίνεται μια συμβολοσειρά \(s\) η οποία αποτελείται απο \(N\) χαρακτήρες καθένας απο τους οποίους ειναι είτε ‘(‘ είτε ‘)’ και μας ζητείται να μετρήσουμε πόσες υποσυβολοσειρές της \(s\) είναι ισορροπημένες. Ισορροπημένη καλείται μια συμβολοσειρά στην οποία:

όλες οι παρενθέσεις που ανοίγουν κλείνουν, και
δεν κλείνουν παρενθέσεις που δεν έχουν προηγουμένως ανοίξει.

Ένα πιο απλό πρόβλημα

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

Το πρόβλημα: Μας δίνεται μια συβολοσειρά \(t\) και θέλουμε να ελέγξουμε αν είναι ισορροπημένη.

Λύση: Για τη λύση θα χρησιμοποιήσουμε τη δομή της στοίβας. Χρησιμοποιώντας τη στοίβα μπορούμε γρήγορα (σε σταθερό χρόνο) να προσθέτουμε ένα στοιχείο σε αυτή, να αφαιρούμε το στοιχείο που προστέθηκε τελευταίο καθώς και να ελέγχουμε αν αυτη είναι άδεια. Έτσι λοιπόν καταλήγουμε στον παρακάτω αλγόριθμο ο οποίος λύνει το πρόβλημα σε γραμμικό χρόνο (πολυπλοκότητα \(\mathcal{O}(N)\)) και μοιάζει πολύ με τον τρόπο που θα το λύναμε και εμείς οι ίδιοι:

Πρώτα, αρχικοποιούμε μια άδεια στοίβα. Στη συνέχεια, διατρέχουμε την συμβολοσειρά \(t\) από τα αριστερά προς τα δεξιά και αν συναντήσουμε τον χαρακτήρα ‘(‘ τον προσθέτουμε στη στοίβα. Αν τώρα συναντήσουμε το χαρακτήρα ‘)’ τότε διακρίνουμε τις περιπτώσεις:

Η στοίβα είναι άδεια. Αυτό σημαίνει πως δεν υπάρχει ανοιχτή παρένθεση η οποία δεν έχει κλείσει προηγουμένως και άρα η \(t\) δεν μπορεί να είναι ισορροπημένη
H στοίβα περιέχει τουλάχιστον ένα στοιχείο. Σε αυτή την περίπτωση μπορούμε απλα να κλείσουμε την τελευταία παρένθεση που βρίσκεται στη στοίβα με αυτή που συναντήσαμε μόλις και να προχωρήσουμε παρακάτω. Το κλείσιμο ισοδυναμεί με αφαίρεση του στοιχείου απο τη στοίβα.

Εύκολα παρατηρούμε ότι η \(t\) είναι ισορροπημένη αν και μόνο αν στο τέλος της παραπάνω διαδικασίας η στοίβα μας είναι άδεια.

Μια υλοποίηση του αλγορίθμου αυτού είναι η εξής:

bool isBalanced(string str){
   stack<char> st;
   for(char ch : str){ //το ch διατρέχει τους χαρακτήρες του str απο αριστερά προς τα δεξιά
                  //δουλεύει μόνο σε C++11 ή νεώτερη έκδοση
      if(ch == '(') st.push('(');
      else{
         if(st.empty()){
            return false;
         } else{
            st.pop();
         }
      }
   }
   return st.empty() //επιστρέφει true αν η στοίβα είναι άδεια
}

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

Αν για παράδειγμα \(t = (())()()\), εκτελώντας τον αλγόριθμο βρίσκουμε ότι η στοίβα αδειάζει στις θέσεις 4, 6 και 8 και έχουμε ότι οι αντίστοιχες υποσυμβολοσειρές \((())\), \((())()\) και \((())()()\) είναι ισορροπημένες.

Επιστρέφοντας στο αρχικό πρόβλημα, θα δούμε τρεις λύσεις:

Μία πολύ αργή, πολυπλοκότητας \(\mathcal{O}(N^3)\)
Μία λίγο πιο γρήγορη (αλλά και πάλι αργή), πολυπλοκότητας \(\mathcal{O}(N^2)\) και
Τη βέλτιστη, πολυπλοκότητας \(\mathcal{O}(N)\)

Σημείωση: Η C++ δεν επιτρέπει την αρίθμηση των συμβολοσειρών (strings) ξεκινώντας από το 1. Γι΄αυτό το λόγο θα χρησιμοποιούμε την παρακάτω συνάρτηση:

char get(string &str, int ind){
   return str[ind - 1];
}

την οποία θα καλούμε για να μας επιστρέφει τον χαρακτήρα στη θέση \(ind\) της συμβολοσειράς \(str\), ξεκινώντας την αρίθμιση απο το 1.

Πολύ αργή λύση - \(\mathcal{O}(N^3)\)

Θα χρησιμοποιήσουμε την προηγούμενη μέθοδο ως εξής: Για κάθε ζεύγος \((i, j)\) με \(1 \leq i < j \leq N\) θα εξετάσουμε αν η υποσυμβολοσειρά \(s[i\dots j]\) (η συμβολοσειρά με αρχή τον χαρακτήρα στη θέση i και τέλος τον χαρακτήρα στη θέση j) είναι ισορροπημένη. Το πλήθος των ζευγών για το οποίο αυτό συμβαίνει είναι και η απάντηση στο πρόβλημα.

Προσοχή: Η απάντηση ενδέχεται να μην χωράει σε ακέραιο 32-bit γι΄αυτό χρησιμοποιούμε ακεραίους 64-bit. Αυτό μπορούμε να το διαπιστώσουμε αν παρουμε ενα test της μορφης \(s=()()\dots ()\). Αν \(k\) είναι το πλήθος των \(()\) που ενώσαμε για να φτιάξουμε την \(s\) τότε η απάντηση είναι \(\frac{k(k+1)}{2}\) και για \(k=\frac{10^6}{2}\) (το μέγιστο δυνατό) η απάντηση δεν χωράει σε ακέραιο 32-bit.

Μία ενδεικτική υλοποίηση παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;

const long MAXN = 1000005;

char get(string &str, int ind){
   return str[ind - 1];
}

int main(){
   ios_base::sync_with_stdio(false); //Τα χρησιμοποιούμε πάντα οταν θέλουμε να 
   cin.tie(NULL), cout.tie(NULL);    //χρησιμοποιήσουμε cin/cout

   #ifdef CONTEST
   freopen("cntbal.in", "r", stdin);
   freopen("cntbal.out", "w", stdout);
   #endif
   

   long N; string s;
   cin >> N >> s;

   long long ans = 0;
   for(long i = 1; i <= N; i++){
      for(long j = i + 1; j <= N; j++){
         //Θα ελέγξουμε αν η s[i...j] είναι ισορροπημένη
         stack<char> st;
         bool isBalanced = true;
         for(long k = i; k <= j; k++){
            if(get(s, k) == '(') st.push('(');
            else{
               if(st.empty()){
                  isBalanced = false;
                  break;
               } else{
                  st.pop();
               }
            }
         }
         if(isBalanced && st.empty()) ans++;
      }
   }

   cout << ans << '\n';

   return 0;
}

Αργή λύση - \(\mathcal{O}(N^2)\)

Καταρχάς, ας προσπαθήσουμε να αλλάξουμε τον τρόπο με τον οποίο μετράμε τις υποσυβολοσειρές. Ένας άλλος αρκετά φυσικός τρόπος είναι να μετρήσουμε για κάθε θέση \(i\) πόσες υποσυμβολοσειρές που ξεκινούν απο το \(i\) είναι ισορροπημένες. Για να απαντήσουμε στο πρόβλημα αρκεί να αθροίσουμε για κάθε \(i\) τις παραπάνω τιμές. Από την Παρατήρηση 1 όμως ξέρουμε έναν γραμμικό τρόπο για να το κάνουμε αυτο. Ξεκινάμε τον αλγόριθμο για να ελέχξουμε εάν η συμβολοσειρά \(s[i\dots N]\) είναι ισορροπημένη με τη μόνη διαφορά ότι μετράμε πόσες φορές αδειάζει η στοίβα. Το πλήθος των φορών είναι ακριβώς αυτο που θέλουμε να υπολογίσουμε. Αφού τρέχουμε \(N\) φορές έναν αλγόριθμο πολυπλοκότητας \(\mathcal{O}(N)\), η λύση τρέχει σε \(\mathcal{O}(N^2)\) χρόνο.

Μία ενδεικτική υλοποίηση παρουσιάζεται παρακάτω:

#include <bits/stdc++.h>
using namespace std;

const long MAXN = 1000005;

char get(string &str, int ind){
   return str[ind - 1];
}

int main(){
   ios_base::sync_with_stdio(false); //Τα χρησιμοποιούμε πάντα οταν θέλουμε να 
   cin.tie(NULL), cout.tie(NULL);    //χρησιμοποιήσουμε cin/cout

   #ifdef CONTEST
   freopen("cntbal.in", "r", stdin);
   freopen("cntbal.out", "w", stdout);
   #endif
   

   long N; string s;
   cin >> N >> s;

   long long ans = 0;
   for(long i = 1; i <= N; i++){
      stack<char> st;
      long long balanced_from_i = 0;
      for(long j = i; j <= N; j++){
         if(get(s, j) == '(') st.push('(');
         else{
            if(!st.empty()){
               st.pop();
               if(st.empty()) balanced_from_i++; //Η στοίβα άδειασε και άρα
                           //η s[i...j] είναι ισορροπημένη
            } else{
               break; //Παρένθεση κλείνει χωρίς να έχει ανοίξει
                  //άρα απο δώ και στο εξής δεν υπάρχουν ισορροπημένες 
                  //υποσυμβολοσειρές
            }
         }
      }
      ans += balanced_from_i;
   }

   cout << ans << '\n';

   return 0;
}

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

Ορισμός 1: Ορίζουμε ως άθροισμα δύο συμβολοσειρών \(s_1\), \(s_2\) την συμβολοσειρά \(s_3 = s_1 + s_2\) η οποία προκύπτει αν στο τέλος της \(s_1\) “κολλήσουμε” την \(s_2\).

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

Παρατήρηση 2: Το άθροισμα δύο ισορροπημένων συμβολοσειρών είναι ισορροπημένη συμβολοσειρά.

Παρατήρηση 3: Κάθε ισορροπημένη συμβολοσειρά είτε είναι απλή είτε γράφεται κατά μοναδικό τρόπο ως άθροισμα απλών συμβολοσειρών.

Παρατήρηση 4: Η συμβολοσειρά \(s[j\dots i]\) που προκύπτει απο τον αλγόριθμο ελέγχου ισορροπημένης συμβολοσειράς όταν κλείνουμε το στοιχείο ‘(‘ στη θέση \(j\) (οπου \(j\) η θέση του στοιχείου που προστέθηκε τελευταίο στη στοίβα) με το στοιχείο ‘)’ στη θέση \(i\) είναι απλή.

Ας ορίσουμε τώρα τον πίνακα \(\mathit{cnt}\) με:

\[\mathit{cnt[i]} = \text{το πλήθος των ισορροπημένων συμβολοσειρών που τελειώνουν στη θέση } i\]

Όμοια με την παραπάνω λύση η απάντηση του προβλήματος είναι το άθροισμα των τιμών \(\mathit{cnt[i]}\) για κάθε \(i \in \{1, 2, \dots N\}\).
Παρατηρήστε ότι αν \(s[i\dots j]\) είναι μια απλή υποσυμβολοσειρά τότε (Παρατήρηση 2, Παρατήρηση 3) \(\mathit{cnt[j]} = 1 + \mathit{cnt[i - 1]}\). Αυτό προκύπτει αφού μπορούμε να έχουμε είτε την υποσυμβολοσειρά \(s[i\dots j]\) ή σε κάθε μια απο τις \(cnt[i - 1]\) ισορροπημένες υποσυμβολοσειρές που τελειώνουν στη θέση \(i-1\) να προσθέσουμε την \(s[i\dots j]\). Συνθέτοντας τα παραπάνω με την Παρατήρηση 4 καταλήγουμε στον παρακάτω αλγόριθμο:

Ξεκινάμε τον αλγόριθμο ελέγχου ισορροπημένης συμβολοσειράς για την \(s\) με τη διαφοροποίηση ότι στη στοίβα κρατάμε και τη θέση του στοιχείου που προσθέτουμε στην αρχική συμβολοσειρά. Επιπλέον, οταν βρούμε ένα στοιχείο ‘)’ στη θέση \(i\), αν η στοίβα δεν είναι κενή θέτουμε \(\mathit{cnt[i]} = 1 + \mathit{cnt[j - 1]}\) όπου \(j\) η θέση του στοιχείου που αφαιρούμε από τη στοίβα (η θέση του ‘(‘ το οποίο κλείνουμε).

Μια εύλογη ερώτηση είναι η εξής: μήπως χάνουμε κάτι στο μέτρημα ή μετράμε κάτι δύο φορές; Η απάντηση είναι όχι και στα δύο. Αυτό μπρορεί να το δεί κανείς διαισθητικά ή να το αποδείξει χρησιμοποιώντας τις παρατηρήσεις.

Μία ενδεικτική υλοποίηση είναι η εξής:

#include <bits/stdc++.h>
using namespace std;

const long MAXN = 1000005;
long long cnt[MAXN];

char get(string &str, int ind){
   return str[ind - 1];
}

int main(){
   ios_base::sync_with_stdio(false); //Τα χρησιμοποιούμε πάντα οταν θέλουμε να 
   cin.tie(NULL), cout.tie(NULL);    //χρησιμοποιήσουμε cin/cout

   #ifdef CONTEST
   freopen("cntbal.in", "r", stdin);
   freopen("cntbal.out", "w", stdout);
   #endif
   

   long N; string s;
   cin >> N >> s;
   
   cnt[0] = 0; //Βοηθητική θέση σε περίπτωση που η s[1...i] είναι απλή
          //συμβολοσειρά. Τότε cnt[i] = 1 + cnt[0] = 1
   stack<long> st;

   for(long i = 1; i <= N; i++){
      if(get(s, i) == '(') st.push(i);
      else{
         if(!st.empty()){
            long j = st.top();
            cnt[i] = 1 + cnt[j - 1]; //Η συμβολοσειρά s[j...i] είναι απλή
            st.pop();
         }
      }
   }

   long long ans = 0;
   for(long i = 1; i <= N; i++){
      ans += cnt[i]; 
   }
   cout << ans << '\n';

   return 0;
}

Σημείωση: Για να εξοικονομήσουμε μνήμη, στη στοίβα κρατάμε μόνο τις θέσεις των ‘(‘ και όχι τους ίδιους τους χαρακτήρες μιας και γνωρίζουμε πως όλοι οι χαρακτήρες που προσθέτουμε στη στοίβα είναι ‘(‘. Σε παραλλαγές του προβλήματος όπου επιτρέπεται και η χρήση και άλλων χαρακτήρων (όπως π.χ ‘{‘, ‘}’, ‘[’, ‘]’) θα ήταν απαραίτητο να κρατάμε και τον ίδιο τον χαρακτήρα.