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

31ος ΠΔΠ B' Φάση: Βουνό ή θάλασσα (mntsea) - Λύση

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

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

Μας δίνεται μία λέξη \(str\) με \(N\) χαρακτήρες \(str_1,str_2,\) …\(,str_N\), όπου ο κάθε χαρακτήρας είναι είτε ‘m’ είτε ‘s’. Μας ζητείται να βρούμε πόσες συνεχόμενες υπο-λέξεις έχουν ίδιο πλήθος ‘m’ και ‘s’.

Για παράδειγμα, έστω ότι μας δίνεται η λέξη

\[msmmss\]

Tότε οι ζητούμενες υπολέξεις είναι αυτές μεταξύ των θέσεων \(1-2\) (‘ms’), \(2-3\) (‘sm’), \(2-5\) (‘smms’), \(4-5\) (‘ms’), \(1-6\) (‘msmmss’) και \(3-6\)(‘mmss’). Συνεπώς το πλήθος τους είναι \(6\).

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

Παρακάτω θα εξετάσουμε:

  1. Μία πολύ απλή/πολύ αργή λύση, πολυπλοκότητας \(\mathcal{O}(N^3)\).
  2. Μία λίγο αργή βελτίωση της λύσης \(1\), πολυπλοκότητας \(\mathcal{O}(N^2)\).
  3. Μία λίγο αργή βελτίωση της λύσης \(1\), πολυπλοκότητας \(\mathcal{O}(N^2)\) ξανά. Εισάγει όμως καινούργιες ιδέες που θα χρειαστούν για να πετύχουμε την …
  4. Σχεδόν βέλτιστη λύση! Πολυπλοκότητας \(\mathcal{O}(NlogN)\).
  5. Βέλτιστη λύση, πολυπλοκότητας \(\mathcal{O}(N)\). Σε παρόμοια προβλήματα, συνήθως αρκεί η λύση \(4\) και δε χρειάζεται η τελική βελτίωση. Παρόλα αυτά, η αλλαγή που πρέπει να γίνει είναι πολύ μικρή, οπότε αξίζει να την εξετάσουμε. Όποιος κουράστηκε, δε χρειάζεται να τη διαβάσει. Όποιος μερακλής αντέχει, ορίστε!

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

Η λύση αυτή πρόκειται για μία απλή δοκιμή όλων των πιθανών υπολέξεων. Κατόπιν εξετάζουμε αυτό ακριβώς που μας υπαγορεύει η εκφώνηση, αν δηλαδή η κάθε υπολέξη περιέχει ίδιο πλήθος από ‘m’ και ‘s’.

Η πολυπλοκότητα είναι \(\mathcal{O}(N^3)\) διότι υπάρχουν \(\mathcal{O}(N^2)\) υπολέξεις, και κάθε μία χρειάζεται το πολύ \(\mathcal{O}(N)\) χρόνο για να μετρήσουμε πόσα ‘m’ και πόσα ‘s’ έχει.

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

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long ll;
long N;
char str[MAXN];

long validWithFixedRight(long right) {
	long ans=0;
	for(long left=1; left<=right; ++left) {
		long countM=0, countS=0;
		for(long i=left; i<=right; ++i) {
			if ( str[i] == 'm' ) ++countM;
			else ++countS;
		}
		
		if(countM==countS) ++ans;
	}

	return ans;
}

int main() {
	#ifdef CONTEST
	freopen("mntsea.in","r",stdin);
	freopen("mntsea.out","w",stdout);
	#endif

	scanf("%ld %s", &N, str+1);
	ll ans = 0;
	for(long right=1; right<=N; ++right)
		ans += validWithFixedRight(right);
	printf("%lld\n", ans);
	
	return 0;
}

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

Για να βελτιώσουμε τη λύση μας από \(\mathcal{O}(N^3)\) σε \(\mathcal{O}(N^2)\), αρκεί η παρακάτω παρατήρηση.

Έστω ότι, όπως και προηγουμένως, έχουμε τη λέξη

\['msmmss'\]

Έστω λοιπόν ότι ήδη ελέγξαμε την υπολέξη ‘mms’ (μεταξύ των θέσεων \(3-5\)), και εντοπίσαμε ότι έχει \(2\) ‘m’ και \(1\) ‘s’.

Αν κατόπιν προσθέσουμε ένα γράμμα προς τα αριστερά (‘smms’, μεταξύ των θέσεων \(2-5\)), υπάρχει λόγος να ξαναμετρήσουμε από την αρχή; Ή μπορούμε να εκμεταλλευτούμε την υπάρχουσα γνώση;

Η απάντηση είναι πολύ απλή. Αφού είχαμε \(2\) ‘m’ και \(1\) ‘s’, και προσθέσαμε ένα ‘s’, πλέον έχουμε \(2\) ‘m’ και \(2\) ‘s’.

Θα εκμεταλλευτούμε το παραπάνω για να σχεδιάσουμε μία ταχύτερη λύση. Αρχικά θα ελέγξουμε όλες τις υπολέξεις που τελειώνουν στη θέση \(1\) (μία είναι όλη κι όλη, χιχι), μετά όλες που τελειώνουν στη θέση \(2\), στη θέση \(3\), … στη θέση \(Ν\).

Τι κάνουμε όταν ελέγχουμε τις υπολέξεις που τελειώνουν στη θέση \(5\); Θα ξεκινήσουμε με αυτήν που αρχίζει στη θέση \(5\) (‘s’ στο παράδειγμά μας). Κατόπιν θα τη μεγαλώσουμε προς τα αριστερά (‘ms’ στο παράδειγμα). Μετά ‘mms’, μετά ‘smms’, μετά ‘msmms’.

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

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

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long ll;
long N;
char str[MAXN];

long validWithFixedRight(long right) {
	long ans=0, countM=0, countS=0;
	for(long left=right; left>0; --left) {
		if ( str[left] == 'm' ) ++countM;
		else ++countS;

		if(countM==countS) ++ans;
	}

	return ans;
}

int main() {
	#ifdef CONTEST
	freopen("mntsea.in","r",stdin);
	freopen("mntsea.out","w",stdout);
	#endif

	scanf("%ld %s", &N, str+1);
	ll ans = 0;
	for(long right=1; right<=N; ++right)
		ans += validWithFixedRight(right);
	printf("%lld\n", ans);
	
	return 0;
}

Αργή λύση - \(\mathcal{O}(N^2)\). Εισάγονται καινούργιες ιδέες που θα χρειαστούν για τη βέλτιστη λύση.

Παρακάτω θα δούμε μία ακόμα λύση πολυπλοκότητας \(\mathcal{O}(N^2)\). Τα εργαλεία που θα χρησιμοποιήσει θα μας είναι χρήσιμα για τη δημιουργία και της βέλτιστης λύσης.

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

Για λόγους ευκολίας στη συζήτηση, ας υποθέσουμε ότι δεν έχουμε τον αρχικό πίνακα \(str\), αλλά έναν πίνακα \(M\) ο οποίος περιέχει \(1\) σε όποια θέση ο \(str\) είχε ‘m’, και \(0\) σε όλες τις άλλες θέσεις. Βεβαίως ο πίνακας αυτός δεν είναι αναγκαίο να δημιουργηθεί και στον κώδικα, απλώς η συζήτηση γίνεται πιο εύκολη έτσι. Για παράδειγμα:

str   m s m m s s
M   1 0 1 1 0 0

Εύκολα βλέπει κανείς ότι η ερώτηση για το πόσα ‘m’ περιέχονται μεταξύ δύο θέσεων του \(str\) απαντιέται με το άθροισμα μεταξύ των ίδιων θέσεων στον πίνακα \(M\). Κι αυτό γιατί κάθε θέση που περιέχει ‘m’ στο \(str\), αυξάνει το άθροισμα κατά \(1\) στο \(M\).

Πώς όμως απαντάμε γρήγορα για αθροίσματα στο \(M\); Δημιουργούμε (πραγματικά, και στον κώδικα!) έναν πίνακα \(sumM\) που σε κάθε θέση \(i\) περιέχει το άθροισμα

\[sumM[i] = M[1]+M[2]+...+M[i]\]

Στη (βοηθητική) θέση \(0\) έχει την τιμή \(0\). Για παράδειγμα:

M     1 0 1 1 0 0
sumM   0 1 1 2 3 3 3

Βλέποντας το παραπάνω παράδειγμα, καταλαβαίνουμε ότι ισχύει

\[sumM[i]=sumM[i-1]+M[i]\]

Γιατί αυτό; Προσπαθήστε να το αποδείξετε, κι όποιος δε το καταφέρει ας μας στείλει μήνυμα :)

Ας δούμε τώρα πώς αυτός ο πίνακας μας βοηθάει να απαντήσουμε ερωτήματα. Έστω ότι ζητάμε το άθροισμα, στον πίνακα \(M\), μεταξύ των θέσεων \(5\) και \(1005\). Θέλουμε δηλαδή το:

                     M[5]+M[6]+...+M[1005]

Γνωρίζουμε ότι έχουμε κάτι αρκετά κοντινό, δηλαδή το \(sumM[1005]\) που είναι ίσο με:

 M[1]+M[2]+M[3]+M[4]+M[5]+M[6]+...+M[1005]

Ποια είναι η διαφορά αυτών των δύο; Απλώς οι τιμές:

M[1]+M[2]+M[3]+M[4]

Όμως και αυτές είναι αποθηκευμένες, στο \(sumM[4]\). Ισχύει δηλαδή

\[SUM(5,1005)=sumM[1005]-sumM[4]\]

και γενικά:

\[SUM(i,j) = sumM[j] - sumM[i-1]\]

Προσοχή! Όχι \(sumM[j]-sumM[i]\) γιατί αυτό θα μας έβγαζε και το \(M[i]\) από το άθροισμα, ενώ εμείς το θέλουμε!

Η τεχνική αυτή είναι πολύ γνωστή, με το όνομα Cumulative Sums ή Prefix Sums.

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

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long ll;
long N, sumM[MAXN], sumS[MAXN];
char str[MAXN];

long Sum(long left, long right, long sum[]) {
	return sum[right]-sum[left-1];
}

long validWithFixedRight(long right) {
	long ans=0;
	for(long left=1; left<=right; ++left)
		if(Sum(left,right,sumM)==Sum(left,right,sumS)) ++ans;

	return ans;
}

int main() {
	#ifdef CONTEST
	freopen("mntsea.in","r",stdin);
	freopen("mntsea.out","w",stdout);
	#endif

	scanf("%ld %s", &N, str+1);
	for (long i=1; i<=N; ++i) {
		if(str[i]=='m') {
			sumM[i]=sumM[i-1]+1;
			sumS[i]=sumS[i-1];
		} else {
			sumM[i]=sumM[i-1];
			sumS[i]=sumS[i-1]+1;
		}
	}
				
	ll ans = 0;
	for(long right=1; right<=N; ++right)
		ans += validWithFixedRight(right);
	printf("%lld\n", ans);
	
	return 0;
}

Σχεδόν βέλτιστη λύση!

Tώρα που μάθαμε τα Cumulative Sums, είμαστε έτοιμοι να τα αξιοποιήσουμε. Θα δώσουμε δύο διαφορετικές επεξηγήσεις. Η πρώτη πιο μαθηματική, η δεύτερη πιο φιλολογική. Διαβάζετε όποια προτιμάτε!

Μαθηματικά: Ας προσέξουμε πότε εντοπίζαμε μία υπολέξη μεταξύ των θέσεων \(i\) και \(j\) στην προηγούμενη λύση (λύση \(3\)). Έπρεπε να ισχύει:

\[sum\_of\_M(i,j) = sum\_of\_S(i,j)\]

Όμως με χρήση Cumulative Sums αυτό αναλύεται σε

\[sumM[j]-sumM[i-1] = sumS[j] - sumS[i-1]\]

Σε τέτοιες περιπτώσεις πάντα δοκιμάζουμε να ξεχωρίσουμε τις μεταβλητές. Το ένα μέλος να μιλάει μόνο για \(i\) και το άλλο μόνο για \(j\). Παίρνουμε λοιπόν:

\[sumM[j]-sumS[j] = sumM[i-1] - sumS[i-1]\]

Τα δύο μέλη μοιάζουν πολύ! Για να μιλάμε πιο εύκολα, ας δημιουργήσουμε ένα καινούργιο πίνακα \(\mathit{Diff}\) με \(N\) θέσεις, που στην \(x\)-οστή θέση του να έχει την παραπάνω ποσότητα, \(Diff[x]=sumM[x]-sumS[x]\).

Καταλήγουμε ότι μία ζητούμενη υπολέξη εμφανίζεται όποτε υπάρχουν \(i\) και \(j\) τέτοια ώστε \(Diff[i-1] = Diff[j]\).

Φιλολογικά: Έστω ότι μία ζητούμενη λέξη αρχίζει στη θέση \(901\) και τελειώνει στη θέση \(1000\). Εξετάζουμε πόσο άλλαξαν τα Cumulative Sums (\(sumM\) και \(sumS\)) πριν την αρχή της υπολέξης (θέση \(900\)) και στο τέλος αυτής (θέση \(1000\)). Παρατηρούμε ότι το πλήθος των ‘m’ αυξήθηκε, καθώς η λέξη μας περιέχει κάποιο πλήθος από ‘m’. Το πλήθος των ‘s’ αυξήθηκε επίσης, και μάλιστα κατά την ίδια ακριβώς ποσότητα με τα ‘m’! Γιατί; Διότι αυτό ακριβώς μας ζητούσε η εκφώνηση, η υπολέξη να περιέχει ίδιο πλήθος ‘m’ και ‘s’.

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

\[sumM[900]-sumS[900]=sumM[1000]-sumS[1000]\]

ή αλλιώς, αν ορίσουμε έναν πίνακα \(\mathit{Diff}\) τέτοιο ώστε σε κάθε θέση \(x\) να ισχύει \(Diff[x]=sumM[x]-sumS[x]\), έχουμε ότι:

\[Diff[900] = Diff[1000]\]

Βλέπουμε ότι κάθε ζητούμενη λέξη αντιστοιχεί σε ένα ζευγάρι θέσεων με τον ίδιο αριθμό, στον πίνακα \(\mathit{Diff}\).

Νέο πρόβλημα: Πλέον το πρόβλημά μας μπορεί να διατυπωθεί ως εξής: Δίνεται ένας πίνακας \(\mathit{Diff}\) και θέλουμε να βρούμε πόσα ζευγάρια θέσεων περιέχουν τον ίδιο αριθμό! Αυτό βεβαίως είναι πολύ ευκολότερο!

Αλγόριθμος: Έστω ότι τελειώσαμε με όλα τα ζευγάρια θέσεων που περιέχουν τον ίδιο αριθμό στον πίνακα \(\mathit{Diff}\), μέχρι τη θέση \(999\). Θέλουμε κατόπιν, γρήγορα, να εντοπίσουμε πόσες θέσεις αριστερά της \(1000\) έχουν τον ίδιο αριθμό \(Diff[1000]\). Προφανώς δε θα τις εξετάσουμε πάλι μία μία.

Αρκεί να έχουμε διατηρήσει ένα map, τέτοιο ώστε στη θέση \(i\) να έχουμε κρατημένες πόσες (μέχρι στιγμής) θέσεις \(x\) έχουν \(Diff[x-1]=i\). Μπορούμε έτσι, απευθείας, να αποσπάσουμε την ζητούμενη πληροφορία.

Τελειώνοντας, πρέπει να ανανεώσουμε το map μας. Αφού μόλις είδαμε και τη θέση \(1000\), πρέπει να ενημερώσουμε το map για αυτήν. Αρκεί να κάνουμε

\[myMap[ Diff[1000] ]++\]

καθώς αυτή ήταν όλη κι όλη η αλλάγη: Είδαμε μία ακόμα θέση (την \(1000\)) με διαφορά ίση με \(Diff[1000]\).

Πολυπλοκότητα: Πλέον, κάθε φορά που βλέπουμε μία καινούργια θέση, δε χρειάζεται να εξετάζουμε όλες τις πιθανές αρχές υπολέξεων που τελειώνουν σε αυτή τη θέση. Αρκεί να ρωτήσουμε το map πόσες αρχές υπολέξεων έχουν διαφορά ίση με αυτή της θέσης μας. Για κάθε μία από τις \(N\) θέσεις κάνουμε \(2\) operations σε map, που κοστίζουν \(\mathcal{O}(logN)\), και συνεπώς η πολυπλοκότητά μας είναι \(\mathcal{O}(NlogN)\).

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

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long ll;
long N, sumM[MAXN], sumS[MAXN];
char str[MAXN];
map<long, long> howManyWithDiff;

long validWithFixedRight(long right) {
	long diff = sumM[right]-sumS[right];
	long ans = howManyWithDiff[diff];
	++howManyWithDiff[diff];
	return ans;
}

int main() {
	#ifdef CONTEST
	freopen("mntsea.in","r",stdin);
	freopen("mntsea.out","w",stdout);
	#endif

	scanf("%ld %s", &N, str+1);
	for (long i=1; i<=N; ++i) {
		if(str[i]=='m') {
			sumM[i]=sumM[i-1]+1;
			sumS[i]=sumS[i-1];
		} else {
			sumM[i]=sumM[i-1];
			sumS[i]=sumS[i-1]+1;
		}
	}
	howManyWithDiff[0] = 1;
				
	ll ans = 0;
	for(long right=1; right<=N; ++right)
		ans += validWithFixedRight(right);
	printf("%lld\n", ans);
	
	return 0;
}

Βέλτιστη λύση.

Η παραπάνω λύση δεν είναι γραμμική, επειδή προτιμήσαμε map αντί για κλασικό πίνακα. Γιατί όμως το κάναμε αυτό;

Ας προσέξουμε ότι η διαφορά μπορεί να είναι αρνητικός αριθμός. Ένα map δεν έχει κανένα πρόβλημα με το να ζητήσουμε τη θέση \(myMap[-1]\), ενώ ένας πίνακας θα δημιουργούσε error.

Αυτό όμως είναι πολύ εύκολο να λυθεί. Αφού στη χειρότερη περίπτωση όλα τα γράμματα είναι ‘s’ (κι άρα η διαφορά είναι \(-N\)), αρκεί στον πίνακά μας, αντί να ζητάμε τη θέση \(Diff[j]\), να ζητάμε τη θέση \(N+Diff[j]\). Με αυτό τον τρόπο, πάντα ζητάμε μη-αρνητικές θέσεις του πίνακα.

Για παράδειγμα, το πλήθος θέσεων με διαφορά \(2\) θα είναι αποθηκευμένο στη θέση \(N+2\), το πλήθος θέσεων με διαφορά \(-N\) θα βρίσκεται στη θέση \(N-N=0\), κλπ.

Εναλλακτικά μπορούμε να έχουμε δύο διαφορετικούς πίνακες, έναν για τις θετικές και έναν για τις αρνητικές τιμές.

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

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
typedef long long ll;
long N, sumM[MAXN], sumS[MAXN], howManyWithDiff[2*MAXN];
char str[MAXN];

long validWithFixedRight(long right) {
	long diff = sumM[right]-sumS[right];
	long ans = howManyWithDiff[diff+N];
	++howManyWithDiff[diff+N];
	return ans;
}

int main() {
	#ifdef CONTEST
	freopen("mntsea.in","r",stdin);
	freopen("mntsea.out","w",stdout);
	#endif

	scanf("%ld %s", &N, str+1);
	for (long i=1; i<=N; ++i) {
		if(str[i]=='m') {
			sumM[i]=sumM[i-1]+1;
			sumS[i]=sumS[i-1];
		} else {
			sumM[i]=sumM[i-1];
			sumS[i]=sumS[i-1]+1;
		}
	}
	howManyWithDiff[0+N] = 1;
				
	ll ans = 0;
	for(long right=1; right<=N; ++right)
		ans += validWithFixedRight(right);
	printf("%lld\n", ans);
	
	return 0;
}

Τελική σημείωση!

Υπάρχουν πάρα πολλοί (και καλοί) λόγοι τα \(N\) στοιχεία ενός πίνακα να τα βάζετε στις θέσεις \(1...Ν\) κι όχι στις \(0...N-1\).

Το μόνο πλεονέκτημα της \(0...N-1\) μεθόδου, είναι ότι εξοικονομούμε μία θέση στον πίνακα (συνταρακτικό!).

Από την άλλη πλευρά, η μέθοδο, \(1...N\) είναι αυτή με την οποία από νήπια μάθαμε να μετράμε. Πιστέψτε μας ότι αυτός ο λόγος θα πρέπει να σας είναι αρκετός!

Επειδή όμως πιθανώς να θέλετε και κάτι πιο χειροπιαστό, δείτε ότι στην τεχνική Cumulative Sums, η θέση 0 χρησιμοποιείται αν ζητήσουμε το άθροισμα όλων των στοιχείων, αφού

\[SUM(1,N) = sumM[N] - sumM[0]\]

Αν η αναπαράστασή ήταν \(0...N-1\), τότε θα είχαμε:

\[SUM(0,N-1) = sumM[N-1] - sumM[-1]\]

κι έτσι θα ζητούσαμε τη θέση \(-1\), πράγμα που θα οδηγούσε σε σφάλμα. Προφανώς το πρόβλημα θα διορθωνόταν με μία if, αλλά αν αυτό είναι επιχείρημα για να υποστηρίξει την μέθοδο \(0...N-1\), τότε μπορεί να υποστηρίξει και τη μέθοδο \(3...N+2\) που μόλις εφηύρα.