36ος ΠΔΠ Γ' Φάση: Bits με υπογραφή (bitsign) - Λύση

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

Μας δίνεται μία ακολουθία \(\texttt{c}\) με χαρακτήρες ‘0’, ‘1’ και ‘.’, και μία ακολουθία \(\texttt{s}\) με ακέραιους αριθμούς. Μας ζητείται να βρούμε με πόσους τρόπους μπορούμε να αντικαταστήσουμε τους χαρακτήρες ‘.’ με ψηφία ‘0’ ή ‘1’ στην \(\texttt{c}\) ώστε η ακολουθία του πλήθους των διαδοχικών ‘1’ να είναι η \(\texttt{s}\).

Για παράδειγμα, για τις ακολουθίες \(\texttt{c} = \texttt{0..00..000.110}\) και \(\texttt{s} = \texttt{1 1 3}\), δύο πιθανές απαντήσεις είναι οι εξής:

Εξαντλητική λύση

Μία λύση είναι να δοκιμάσουμε όλες τις δυνατές τιμές \(0\) και \(1\) για κάθε θέση της \(\texttt{c}\) που έχει ‘.’. Στην χειρότερη περίπτωση χρειάζεται να ελέγξουμε \(\Theta(2^N)\) δυνατές ακολουθίες, επομένως ο αλγόριθμος χρειάζεται \(\mathcal{O}(2^N)\) χρόνο.

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

/* Δοκιμάζουμε τις δυνατές τιμές για το c[c_idx], δεδομένου ότι έχουμε συμπληρώσει 
   τις τιμές για τα c[0..c_idx-1], ότι έχουμε φτιάξει τα διαστήματα s[0..s_idx-1] και 
   ότι το μήκος της τωρινής ακολουθίας από άσους είναι len_of_ones. */
void solve(int c_idx, int len_of_ones, int s_idx) {
   if (c_idx == N + 1) {
      // Συμπληρώσαμε όλη την ακολουθία. Ελέγχουμε ότι δεν μας περίσσεψε κάτι.
      if (s_idx == s.size() && len_of_ones == 0) total = (total + 1) % MOD;
      return;
   }
   // Δοκιμάζουμε να βάλουμε έναν άσο. Επεκτείνεται η τωρινή ακολουθία κατά ένα.
   if (c[c_idx] == '1' || c[c_idx] == '.') solve(c_idx + 1, len_of_ones + 1, s_idx);
   // Δοκιμάζουμε να βάλουμε ένα μηδενικό. Αν υπάρχει τωρινή ακολουθία από άσσους
   // με μήκος s[s_idx], την ολοκληρώνουμε.
   if (c[c_idx] == '0' || c[c_idx] == '.') {
      if (s_idx < s.size() && len_of_ones == s[s_idx]) solve(c_idx + 1, 0, s_idx + 1);
      else if (len_of_ones == 0) solve(c_idx + 1, 0, s_idx);
   }
}

και η αρχική κλήση είναι η εξής:

      total = 0;
      solve(0, 0, 0);

Μπορείτε να βρείτε ολόκληρο των κώδικα εδώ.

Λύση με δυναμικό προγραμματισμό σε \(\mathcal{O}(N^2 M)\) χρόνο

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

Ορίζουμε ως dp[j][i] το πλήθος των δυνατών τρόπων να αντισταταστήσουμε τα ‘.’ στις θέσεις c[1..i] ώστε να έχουμε συμπληρώσει ακολουθίες διαδοχικών άσων με μήκη s[1..j]. Για χάριν ευκολίας, λέμε ότι συμπληρώνεται μία ακολουθία από διαδοχικούς άσους αφού προσθέσουμε το μηδέν μετά τον τελευταίο άσο. Επιπλέον, προσθέτουμε ένα μηδενικό στο τέλος του c (το οποίο δεν αλλάζει την απάντηση), ώστε να ολοκληρωθεί η τελευταία ακολουθία από άσους. Άρα σε κάθε θέση c[i] = ‘1’ έχουμε εξ ορισμού ότι dp[j][i] = 0.

Αν το στοιχείο c[i] = ‘0' ή c[i] = ‘.', έχουμε δύο τρόπους να επεκτείνουμε τις υπάρχουσες ακολουθίες:

1. Επεκτείνουμε όλες τις λύσεις στο dp[j][i-1] προσθέτοντας ένα μηδενικό στο τέλος τους.
2. Αν μπορούμε να βάλουμε s[j] άσους στις θέσεις c[(i - s[j] - 1)..(i-1)], δηλαδή αυτές οι θέσεις έχουν μόνο χαρακτήρες ‘1’ ή ‘.’, τότε έχουμε dp[j - 1][i - s[j] - 1] επιπλέον τρόπους.

Ο παρακάτω κώδικας συμπληρώνει τον πίνακα dp και η απάντηση βρίσκεται στην θέση dp[M][N+1].

      for (int i = 0; i <= N+1 && c[i] != '1'; ++i) dp[0][i] = 1;
      
      for (int j = 1; j <= M; ++j) {
         for (int i = 1; i <= N + 1; ++i) {
            if (c[i] == '1') continue;
            dp[j][i] = dp[j][i-1]; // Μπορούμε απλά να προσθέσουμε ένα 0.
            int first_zero_to_left = i - 1;
            while (c[first_zero_to_left] != '0') --first_zero_to_left;
            if (i - first_zero_to_left - 1 >= s[j-1]) { // Υπάρχουν αρκετά ‘1' ή ‘.'?
               dp[j][i] = (dp[j][i] + dp[j - 1][i - s[j-1] - 1]) % MOD;
            }
         }
      }

Ο έλεγχος για τα στοιχεία c[(i-s[j]-1)..(i-1)] χρειάζεται \(\mathcal{O}(N)\) χρόνο, άρα αφού υπάρχουν \(\mathcal{O}(NM)\) θέσεις στον πίνακα dp, συνολικά ο αλγόριθμος χρειάζεται \(\mathcal{O}(N^2M)\) χρόνο και \(\mathcal{O}(NM)\) μνήμη.

Μπορείτε να βρείτε ολόκληρο των κώδικα εδώ.

Λύση με δυναμικό προγραμματισμό (σε \(\mathcal{O}(N M)\) χρόνο)

Μπορούμε να επιταγχύνουμε την προηγούμενη λύση προϋπολογίζοντας τις τιμές first_zero_to_left για κάθε θέση i σε χρόνο \(\mathcal{O}(N)\) (ακόμα και \(\mathcal{O}(N^2)\) θα ήταν αρκετό), ως εξής:

      // Προϋπολογίζουμε το πρώτο μηδενικό στα δεξιά του κάθε στοιχείου.
      std::vector<int> first_zero_to_left(N + 2);
      for (int i = N + 1; i >= 0; --i) {
         if (c[i] == '0') {
            first_zero_to_left[i] = i;
            continue;
         }
         first_zero_to_left[i] = std::min(first_zero_to_left[i+1], i);
         while (c[first_zero_to_left[i]] != '0') --first_zero_to_left[i];
      }

Ο κυρίως κώδικας αλλάζει ως εξής:

      for (int i = 0; i <= N+1 && c[i] != '1'; ++i) dp[0][i] = 1;
      
      for (int j = 1; j <= M; ++j) {
         for (int i = 1; i <= N + 1; ++i) {
            if (c[i] == '1') continue;
            dp[j][i] = dp[j][i-1]; // Μπορούμε απλά να προσθέσουμε ένα 0.
            if (i - first_zero_to_left[i - 1] - 1 >= s[j-1]) // Υπάρχουν αρκετά ‘1' ή ‘.'?
               dp[j][i] = (dp[j][i] + dp[j - 1][i - s[j-1] - 1]) % MOD;
         }
      }

Έτσι χρειάζομαστε \(\mathcal{O}(1)\) χρόνο για τον υπολογισμό της κάθε τιμής του πίνακα \(\texttt{dp}\), συνεπώς ο αλγόριθμος τρέχει σε \(\mathcal{O}(NM)\) χρόνο. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Επιπλέον αν παρατηρήσετε ότι για τον υπολογισμό των τιμών \(\texttt{dp}[j][\cdot]\) χρησιμοποιούμε μόνο τις τιμές \(\texttt{dp}[j-1][\cdot]\), μπορούμε να κρατάμε μόνο δύο γραμμές στον πίνακα dp, μειώνοντας τον συνολικό χώρο σε \(\mathcal{O}(N)\). Δείτε εδώ.