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

30ος ΠΔΠ Γ' Φάση: Παιχνίδι με λίστα (listgame) - Λύση

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

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

Ας ξεκαθαρίσουμε ότι το να διαλέγουμε πάντα το μέγιστο δεν είναι η βέλτιστη στρατηγική. Για παράδειγμα, αν οι αριθμοί είναι \(1, 1, 100, 10\) τότε αν πάρουμε το \(10\) στην επόμενη κίνηση ο αντίπαλος θα πάρει το \(100\) και μετά θα πάρουμε το \(1\) (τελικό άθροισμα \(11\)). Αν όμως πάρουμε το \(1\), τότε ο αντίπαλος όποιον αριθμό \(1\) ή \(10\) και να πάρει, θα μας αφήσει το \(100\). Άρα θα έχουμε τελικό άθροισμα \(101\) που είναι το μέγιστο.

Αυτό το παράδειγμα δείχνει ότι και ο αντίπαλος προσπαθεί να μεγιστοποιήσει το άθροισμα του, άρα αν μπορεί δεν θα μας αφήσει το \(100\).

Θα χρησιμοποιήσουμε την εξής παρατήρηση για να ορίσουμε αυστηρά τι σημαίνει να παίζουμε βέλτιστα:

Παρατήρηση 1: Η μεγιστοποίηση του αθροίσματός μας ισοδυναμεί με την μεγιστοποίηση της διαφοράς του αθροίσματός μας και του αθροίσματος του αντιπάλου μας.

Απόδειξη. Έστω ότι διαλέγουμε στοιχεία συνολικού κόστους \(A\) και ο αντίπαλος συνολικού κόστους \(B\). Τότε το άθροισμα όλων των στοιχείων \(\mathit{total} = A + B\) (που είναι σταθερό). Άρα η μεγιστοποίηση του \(A-B = A - (\mathit{total} - A) = 2A - \mathit{total}\), ισοδυναμεί με την μεγιστοποίηση του \(A\).

Έπεται, ο αντίπαλος προσπαθεί να ελαχιστοποιήσει αυτή τη διαφορά.

Σημείωση: Αν γνωρίζουμε τη διαφορά \(A - B = d\), τότε μπορούμε να βρούμε το \(A\) χρησιμοποιώντας \(\mathit{total} = A + B\). Λύνοντας το σύστημα \(A = (\mathit{total} + d)/2\).

Brute force

Αναφερόμαστε σε εμάς ως παίχτη \(A\) και στον αντίπαλο ως παίχτη \(B\). Έστω \(\mathit{best}_A(i, j)\) είναι η μέγιστη διαφορά που μπορεί να πετύχει ο \(A\) αν έχουν μείνει τα στοιχεία \(a[i], \ldots, a[j]\) (και οι δύο παίχτες παίζουν βέλτιστα). Αντίστοιχα, έστω \(\mathit{best}_B(i, j)\) είναι η ελάχιστη διαφορά που μπορεί να πετύχει ο \(B\) αν έχουν μείνει τα στοιχεία \(a[i], \ldots, a[j]\).

Εμείς θέλουμε να υπολογίσουμε το \(\mathit{best}_A(0, N-1)\), τη μέγιστη διαφορά που μπορούμε να πετύχουμε.

Θα ορίσουμε μία αναδρομική σχέση για να υπολογίσουμε αυτές τις τιμές.

Αν παίζει ο \(A\) τότε έχει δύο επιλογές:

  1. Να πάρει το πρώτο στοιχείο. Τότε το άθροισμα του \(A\) θα αυξηθεί κατά \(a[i]\) και ο \(B\) θα προσπαθήσει να ελαχιστοποιήσει την διαφορά όταν έχουν μείνει τα στοιχεία \(a[i + 1], \ldots, a[j]\). Άρα η διαφορά είναι
\[a[i] + \mathit{best}_B(i + 1, j)\]

  1. Να πάρει το τελευταίο στοιχείο. Τότε το άθροισμα του \(A\) θα αυξηθεί κατά \(a[j]\) και ο \(B\) θα προσπαθήσει να ελαχιστοποίησει την διαφορά όταν έχουν μείνει τα στοιχεία \(a[i], \ldots, a[j - 1]\). Άρα η διαφορά είναι

    \[\mathit{best}_B(i, j - 1) + a[j]\]

Ο \(A\) θα διαλέξει τη μέγιστη από τις δύο επιλογές, άρα:

\[\mathit{best}_A(i, j) = \max{\lbrace a[i] + \mathit{best}_B(i + 1, j), \mathit{best}_B(i, j - 1) + a[j] \rbrace}\]

Αντίστοιχα, αν παίζει ο \(B\), τότε η σχέση είναι

\[\mathit{best}_B(i, j) = \min{\lbrace -a[i] + \mathit{best}_A(i + 1, j), \mathit{best}_A(i, j - 1) - a[j] \rbrace}\]

καθώς προσπαθεί να ελαχιστοποιήσει τη διαφορά.

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

#include <algorithm>
#include <cstdio>

const size_t MAXN = 10000;

long a[MAXN];

long best_b(long i, long j);

long best_a(long i, long j) {
   // Βασική συνθήκη.
   if (i == j) return a[i];
   // Διαλέγουμε το καλύτερο από τα δύο ενδεχόμενα.
   return std::max(a[i] + best_b(i + 1, j), best_b(i, j - 1) + a[j]);
}

long best_b(long i, long j) {
   // Βασική συνθήκη.
   if (i == j) return -a[i];
   // Διαλέγουμε το καλύτερο από τα δύο ενδεχόμενα.
   return std::min(-a[i] + best_a(i + 1, j), best_a(i, j - 1) - a[j]);
}

int main() {
   long N;
   FILE *fi = fopen("listgame.in", "r");
   fscanf(fi, "%ld", &N);
   long total = 0;
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &a[i]);
      total += a[i];
   }
   fclose(fi);

   FILE *fo = fopen("listgame.out", "w");
   long outcome = best_a(0, N - 1); 
   fprintf(fo, "%ld\n", (outcome + total)/2);
   fclose(fo);
   return 0;
}

Δυναμικός προγραμματισμός

Παρατηρούμε ότι για κάθε \(i\) και \(j\) υπολογίζουμε το \(\mathit{best}_A(i, j)\) και \(\mathit{best}_B(i, j)\) πολλές φορές. Μπορούμε όταν υπολογίσουμε για πρώτη φορά αυτή την τιμή, να την αποθηκεύουμε σε έναν πίνακα και όποτε την χρειαζόμαστε να ανατρέχουμε στον πίνακα. Αυτό μας εγγυάται ότι κάθε τιμή υπολογίζεται μόνο μία φορά, που οδηγεί σε συνολικό χρόνο \(\mathcal{O}(N^2)\) και μνήμη \(\mathcal{O}(N^2)\). Η τεχνική αυτή λέγεται δυναμικός προγραμματισμός.

#include <algorithm>
#include <cstdio>

const size_t MAXN = 10000;

long a[MAXN];

// Παρατηρήστε ότι για συγκεκριμένο i και j μόνο ένα από τα best_a(i, j)
// και best_b(i, j) είναι δυνατό (γιατί μετά από συγκεκριμένο αριθμό κινήσεων
// πάντα παίζει ο ίδιος παίχτης).
bool already_calculated[MAXN][MAXN]; // Αν έχουμε υπολογίσει την τιμή για το (i, j).
long dp[MAXN][MAXN]; // Η τιμή για το (i, j).

long set_and_return(long i, long j, long v) {
   already_calculated[i][j] = true;
   return dp[i][j] = v;
}

long best_b(long i, long j);

long best_a(long i, long j) {
   if (already_calculated[i][j]) return dp[i][j];
   // Βασική συνθήκη.
   if (i == j) return a[i];
   // Διαλέγουμε το καλύτερο από τα δύο ενδεχόμενα.
   long v = std::max(a[i] + best_b(i + 1, j), best_b(i, j - 1) + a[j]);
   return set_and_return(i, j, v);
}

long best_b(long i, long j) {
	if (already_calculated[i][j]) return dp[i][j];
   // Βασική συνθήκη.
   if (i == j) return -a[i];
   // Διαλέγουμε το καλύτερο από τα δύο ενδεχόμενα.
   long v = std::min(-a[i] + best_a(i + 1, j), best_a(i, j - 1) - a[j]);
   return set_and_return(i, j, v);
}

int main() {
    long N;
    FILE *fi = fopen("listgame.in", "r");
	fscanf(fi, "%ld", &N);
	long total = 0;
	for (long i = 0; i < N; ++i) {
	   fscanf(fi, "%ld", &a[i]);
	   total += a[i];
	}
	fclose(fi);

	FILE *fo = fopen("listgame.out", "w");
	long outcome = best_a(0, N - 1); 
	fprintf(fo, "%ld\n", (outcome + total)/2);
	fclose(fo);
	return 0;
}

Iterative δυναμικός προγραμματισμός

Η παραπάνω λύση βρίσκει τις τιμές \(\mathit{best}_A\) και \(\mathit{best}_B\) αναδρομικά. Αν και θεωρητικά δεν οδηγεί σε πιο γρήγορη λύση, μπορούμε να αφαιρέσουμε την αναδρομή που στην πράξη επιταχύνει την λύση. Αυτό θα μας βοηθήσει στην επόμενη λύση να μειώσουμε τη μνήμη που χρειαζόμαστε.

Παρατήρηση 3: Κοιτώντας τις αναδρομικές σχέσεις:

  • \[\mathit{best}_A(i, j) = \max{\lbrace a[i] + \mathit{best}_B(i + 1, j), \mathit{best}_B(i, j - 1) + a[j] \rbrace}\]
  • \[\mathit{best}_B(i, j) = \min{\lbrace -a[i] + \mathit{best}_A(i + 1, j), \mathit{best}_A(i, j - 1) - a[j] \rbrace}\]

στο δεξιό μέρος κοιτάμε διαστήματα με μήκος ένα μικρότερο από το τωρινό (\(j - i - 1\) αντί για \(j - i\)). Επομένως μπορούμε να υπολογίσουμε τις τιμές \(\mathit{best}\) ξεκινώντας από τις μικρότερες διαφορές προς τις μεγαλύτερες.

#include <algorithm>
#include <cstdio>

const size_t MAXN = 10000;

long a[MAXN];
long dp[MAXN][MAXN]; // dp[i][j] = καλύτερο από το j στο i + j

int main() {
   long N;
   FILE *fi = fopen("listgame.in", "r");
   fscanf(fi, "%ld", &N);
   long total = 0;
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &a[i]);
      total += a[i];
   }
   fclose(fi);
   
   for (long i = 0; i < N; ++i) {
      for (long j = 0; j + i < N; ++j) {
        if (i == 0) dp[j][j] = a[j];
        else if (i % 2 == 0) {
           dp[j][j + i] = std::max(a[j] + dp[j + 1][j + i], a[i + j] + dp[j][j + i - 1]);
        } else dp[j][j + i] = std::min(-a[j] + dp[j + 1][j + i], -a[i + j] + dp[j][j + i - 1]);
      }
   }
   
   FILE *fo = fopen("listgame.out", "w");
   if (N % 2 == 1) fprintf(fo, "%ld\n", (dp[0][N-1] + total)/2);
   else fprintf(fo, "%ld\n", (total - dp[0][N-1])/2);
   fclose(fo);
   return 0;
}

Δυναμικός προγραμματισμός με memoisation

Χρησιμοποιώντας την Παρατήρηση \(3\), όταν συμπληρώνουμε τις τιμές για διαφορά \(d+1\) τότε χρειαζόμαστε μόνο της τιμές με διαφορά \(d\). Επομένως μπορούμε να κρατάμε μόνο δύο σειρές στον πίνακα. Αυτή η τεχνική λέγαται δυναμικός προγραμματισμός με memoisation και οδηγεί σε λύση που χρειάζεται \(\mathcal{O}(N)\) μνήμη.

#include <algorithm>
#include <cstdio>

const size_t MAXN = 10000;

long a[MAXN];

// Δύο σειρές που αντιστοιχούν στις διαφορές d και d + 1.
long dp[MAXN][2];

int main() {
   long N;
   FILE *fi = fopen("listgame.in", "r");
   fscanf(fi, "%ld", &N);
   long total = 0;
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &a[i]);
      total += a[i];
   }
   fclose(fi);
   // dp[i][j] = best from j to i + j
   for (long i = 0; i < N; ++i) {
      long cur = i % 2; // Διαφορά d + 1
      long prev = (i + 1) % 2; // Διαφορά d
      for (long j = 0; j + i < N; ++j) {
        if (i == 0) dp[j][cur] = a[j];
        else if (i % 2 == 0) {
           dp[j][cur] = std::max(a[j] + dp[j + 1][prev], a[i + j] + dp[j][prev]);
        } else dp[j][cur] = std::min(-a[j] + dp[j + 1][prev], -a[i + j] + dp[j][prev]);
      }
   }
   FILE *fo = fopen("listgame.out", "w");
   if (N % 2 == 1) fprintf(fo, "%ld\n", (dp[0][0] + total)/2);
   else fprintf(fo, "%ld\n", (total - dp[0][1])/2);
   fclose(fo);
   return 0;
}