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

28ος ΠΔΠ B' Φάση: Μονοδιάστατο scrabble (scrabble1d) - Λύση

Συγγραφέας: Γιώργος Βενιζέλος

Επεξήγηση προβλήματος

Το πρόβλημα ζητάει να τοποθετήσουμε 2 λέξεις μήκους \(K\) σε έναν πίνακα \(N\) θέσεων (θα τα αριθμίσουμε από το \(1\) ως το \(N\)). Οι λέξεις δεν πρέπει να επικαλύπτονται και σκοπός μας είναι να μεγιστοποιήσουμε το άθροισμα των πόντων των κελιών στα οποία έχουμε τοποθετήσει τις λέξεις. Με πιο απλά λόγια, το πρόβλημα ζητάει να βρόυμε 2 διαστήματα μήκους \(K\), που να μην αλληλοεπικαλύπτονται, και το άθροισμα των κελιών τους να είναι το μέγιστο δυνατό.

Λύση πολυπλοκότητας \(\mathcal{O}(N^2 K)\)

Η πιο απλή λύση που μπορούμε να σκεφτούμε, είναι να δοκιμάσουμε όλους τους πιθανούς συνδυασμούς τοποθέτησης των λέξεων. Έστω ότι η πρώτη λέξη ξεκινάει από το κελί \(s_1\) και τελειώνει στο κελί \(s_1+K-1\), και η δεύτερη λέξη ξεκινάει από το \(s_2\) και φτάνει ως το \(s_2+K-1\). Για να είναι ολόκληρο το διάστημα των λέξεων μέσα στον πίνακα και να μην επικαλύπτονται, θα πρέπει \(1 \le s_1 \le N - 2K + 1\), \(K + 1 \le s_2 \le N - K + 1\) και \(s_1 + K \le s_2\). Τότε μπορούμε να έχουμε μια επανάληψη για κάθε πιθανή θέση του \(s_1\) και \(s_2\), στην οποία υπολογίζουμε το άθροισμα για τις λέξεις και ελέγχουμε εάν αυτό είναι το μέχρι στιγμής μέγιστο. Ο κώδικας είναι ο εξής:

#include <cstdio>

using namespace std;

const size_t MAXN = 2000000;
const size_t MAXK = 1000000;

long N, K;
long P[MAXN]; // Οι πόντοι του ταμπλό

int main () {
	// Άνοιγμα αρχείων για διαβασμα και γράψιμο
	freopen("scrabble1d.in", "r", stdin);
	freopen("scrabble1d.out", "w", stdout);
	
	// Διάβσμα αρχείου εισόδου
	scanf("%ld %ld", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%ld", P + i);
	}

	// Αρχικοποιούμε το μέγιστο άθροισμα με 0
	long maxSum = 0;
	for (int s1 = 1; s1 <= N - 2 * K + 1; s1++) {
		// Εύρεση των πόντων που παίρνει η λέξη αν ξεκινάει από το s1
		long sum1 = 0;
		for (int e1 = 0; e1 < K; e1++) {
			sum1 += P[s1 + e1];
		}
		
		// Αρκεί να βρούμε το μέγιστο άθροισμα για τη δεύτερη λέξη πρώτα
		// και μετα να το προσθέσουμε στο sum1, αφού το sum1 παραμένει σταθερό
		// όσο αλλάζει το sum2

		// Αρχικοποιούμε το μέγιστο άθροισμα για την
		// δεύτερη λέξη
		long maxSum2 = 0;
		// Η επανάληψη για το s2 ξεκινάει τουλάχιστον Κ στοιχεία
		// μετά το s1 για να μην επικαλύπτονται τα διαστήματα
		for (int s2 = s1 + K; s2 <= N - K + 1; s2++) {
			// Βρίσκουμε τους πόντους που παίρνει η λέξη αν ξεκινάει από το s2
			long sum2 = 0;
			for (int e2 = 0; e2 < K; e2++) {
				sum2 += P[s2 + e2];
			}
			if (sum2 > maxSum2) { maxSum2 = sum2; }
		}
		// Αν το άθροισμα των πόντων των δύο λέξεων είναι καλύτερο
		// από αυτό που έχουμε ως τώρα, ανανεώνουμε το maxSum
		if (sum1 + maxSum2 > maxSum) {
			maxSum = sum1 + maxSum2;
		}
	}
	printf("%ld\n", maxSum);
	return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(N^2)\)

Παρατηρούμε ότι στον παραπάνω κώδικα υπολογίζουμε πολλές φορές από την αρχή τα αθροίσματα των λέξεων, ενώ αυτά δεν αλλάζουν και εξαρτώνται μόνο από το αρχικό κελί \(s\) της λέξης. Επομένως, μπορούμε να υπολογίσουμε τα αθροίσματα αυτά στην αρχή του κώδικα και να αποφύγουμε επιπλέον επαναλήψεις στον κώδικα. Ο χώρος που θα χρειαστεί για να αποθηκεύσουμε τα αθροίσματα είναι \(\mathcal{O}(N)\), δηλαδή όσος χρειάζεται για να αποθηκεύσουμε και τις τιμές του πίνακα. Παρ’ όλ’ αυτά, δεν χρειάζεται πλέον να κρατάμε τις τιμές του αρχικού πίνακα, καθώς το μόνο που χρειαζόμαστε είναι τα αθροίσματα.

Για να υπολογίσουμε τα αθροίσματα των λέξεων (τα οποία μπορούμε να τα λέμε και Κ-αθροίσματα), αρχικά θα υπολογίσουμε τον πίνακα \(\texttt{sums}[s]\) που θα κρατάει το άθροισμα των στοιχείων από το κελί \(1\) ως το κελί \(s\). Άρα θα έχουμε ότι

\[\texttt{sums}[s] = \sum_{i=1}^{s} P_i = P_1 + P_2 + \dotsb + P_{s-1} + P_s.\]

Με αυτόν τον πίνακα μπορούμε πολύ εύκολα να υπολογίσουμε το Κ-άθροισμα στη θέση \(s\)

\[\begin{align*} \text{Κ-άθροισμα}[s] & = P_s + P_{s+1} + \dotsb + P_{s + K - 1}\\ & = (P_1 + P_2 + \dotsb + P_{s + K - 1}) - (P_1 + P_2 + \dotsb + P_{s - 1}) \\ & = \texttt{sums}[s + K - 1] - \texttt{sums}[s - 1]. \end{align*}\]

Τα αθροίσματα \(\texttt{sums}[i]\) μπορούν να υπολογιστούν κατά το διάβασμα του αρχείου, και τα αθροίσματα μπορούν τώρα να υπολογιστούν σε μία γραμμή.

#include <cstdio>

using namespace std;

const size_t MAXN = 2000000;
const size_t MAXK = 1000000;

long N, K;
long sums[MAXN]; // Το άθροισμα των πόντων ξεκινώντας από την αρχή

int main () {
	freopen("scrabble1d.in", "r", stdin);
	freopen("scrabble1d.out", "w", stdout);

	sums[0] = 0;
	scanf("%ld %ld", &N, &K);
	long val;
	for (int i = 1; i <= N; i++) {
		scanf("%ld", &val);
		// Ανανεώνουμε το επόμενο στοιχείο του πίνακα sums
		sums[i] = sums[i-1] + val;
	}

	long maxSum = 0;
	for (int s1 = 1; s1 <= N - 2 * K + 1; s1++) {
		long sum1 = sums[s1 + K - 1] - sums[s1 - 1];
		long maxSum2 = 0;
		for (int s2 = s1 + K; s2 <= N - K + 1; s2++) {
			long sum2 = sums[s2 + K - 1] - sums[s2 - 1];
			if (sum2 > maxSum2) { maxSum2 = sum2; }
		}
		if (sum1 + maxSum2 > maxSum) {
			maxSum = sum1 + maxSum2;
		}
	}
	printf("%ld\n", maxSum);
	return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(N)\)

Μια ακόμα παρατήρηση που μπορούμε να κάνουμε, είναι ότι υπολογίζουμε το \(\texttt{maxSum2}\) κάθε φορά από την αρχή για κάθε τιμή του \(s_1\). Όμως, το μέγιστο Κ-άθροισμα \(\texttt{maxSum2}\) για τη θέση \(s_1\) (για κάθε \(s_2 \ge s_1 + K\)) είναι όσο το μέγιστο από τα

  • \(\texttt{maxSum2}\) για τη θέση \(s_1 + 1\)
  • το Κ-άθροισμα που ξεκινάει από τη θέση \(s_1 + K\)

Επομένως αν έχουμε υπολογίσει το \(\texttt{maxSum2}\) για τη θέση \(s_1 + 1\), μπορούμε με μία σύγκριση να βρούμε το \(\texttt{maxSum2}\) για τη θέση \(s_1\). Αρκεί να διασχίσουμε τον πίνακα ανάποδα και να κρατάμε την τιμή για το έως τώρα μέγιστο \(\texttt{maxSum2}\).

#include <cstdio>

using namespace std;

const size_t MAXN = 2000000;
const size_t MAXK = 1000000;

long N, K;
long sums[MAXN];

int main () {
	freopen("scrabble1d.in", "r", stdin);
	freopen("scrabble1d.out", "w", stdout);
	
	sums[0] = 0;
	scanf("%ld %ld", &N, &K);
	long val;
	for (int i = 1; i <= N; i++) {
		scanf("%ld", &val);
		sums[i] = sums[i-1] + val;
	}

	long maxSum = 0;
	long maxSum2 = 0;
	// Ελέγχουμε για κάθε υποψήφια θέση της αρχής της πρώτης λέξης
	for (int s1 = N - 2 * K + 1; s1 >= 1; s1--) {
		// Υπολογίζουμε των Κ-αθροισμάτων που ξεκινάνε από το s1 και το s1+K αντίστοιχα
		long sum1 = sums[s1 + K - 1] - sums[s1 - 1];
		long sum2 = sums[s1 + 2 * K - 1] - sums[s1 + K - 1];
		// Ανανεώνουμε το καλύτερο άθροισμα maxSum2
		if (sum2 > maxSum2) { maxSum2 = sum2; }
		// Ανανεώνουμε το καλύτερο συνολικό άθροισμα
		if (sum1 + maxSum2 > maxSum) { maxSum = sum1 + maxSum2; }
	}
	printf("%ld\n", maxSum);
	return 0;
}