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

32ος ΠΔΠ B' Φάση: Τα δύο καταστήματα (shops) - Λύση

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

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

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

Για παράδειγμα αν μας δίνεται ο πίνακας

\[2,~4,~15,~12,~10,~1,~1,~20,~4,~10\]

Τότε η απάντηση είναι \(71\), διότι μπορούμε να διαλέξουμε τα διαστήματα \(15,~12,~10\) και \(20,~4,~10\).

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

  1. Μία πολύ απλή/πολύ αργή λύση, πολυπλοκότητας \(\mathcal{O}(N^2\cdot K)\). Δε χρειάζεται καμμία προ-απαιτούμενη γνώση.
  2. Μία λίγο αργή βελτίωση της λύσης \(1\), πολυπλοκότητας \(\mathcal{O}(N^2)\). Θα χρειαστούμε την τεχνική cumulative sums (δείτε το θέμα Β Φάσης Γυμνασίου 31ου ΠΔΠ).
  3. Βέλτιστη λύση! Πολυπλοκότητας \(\mathcal{O}(N)\). Δε χρειάζεται κάποια επιπλέον γνώση πέρα από τα cumulative sums.

Παρατήρηση

Δεν υπάρχει κανένας λόγος τα διαστήματα να έχουν επικάλυψη. Εφόσον ξέρουμε ότι ο πίνακας είναι αρκετά μεγάλος (μεγαλύτερος από 2K κατά την εκφώνηση) τότε οποιαδήποτε λύση με επικάλυψη μπορεί να βελτιωθεί μετακινόντας είτε το αριστερότερο διάστημα προς τα αριστερά, είτε το δεξιότερο προς τα δεξιά. Έτσι προσθέτουμε πάντα περισσότερα στοιχεία, και εφόσον κανένας αριθμός δεν είναι αρνητικός, αυτό μας συμφέρει.

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

Γνώσεις που θα χρειαστούμε: Καμμία.

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

Κάθε φορά που έχουμε ένα τέτοιο συνδυασμό, υπολογίζουμε το άθροισμα των \(2K\) στοιχείων.

Η τελική πολυπλοκότητα είναι λοιπόν \(\mathcal{O}(N^2\cdot K)\).

Παρακάτω δίνεται μία ενδεικτική υλοποίηση αυτής της λύσης.

#include <bits/stdc++.h>
const long MAXN = 2000000;
using namespace std;

long N, K, ans, s, sum, A[MAXN+5];

int main() {
  freopen("shops.in","r",stdin);
  freopen("shops.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  for(long i=1; i<=N; ++i)
    scanf("%ld", &A[i]);
  for(long right2=2*K; right2<=N; ++right2)
    for(long right1=K; right1<=right2-K; ++right1) {
      long sum = 0;
      for(long k=1; k<=K; ++k) sum += A[right2-k+1] + A[right1-k+1];
      ans = max (sum, ans);
    }

  printf("%ld\n", ans);
  return 0;
}

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

Γνώσεις που θα χρειαστούμε: cumulative sums.

Η λύση που θα δούμε εισάγει ιδέες που θα χρειαστούν για την βέλτιστη λύση.

Υπάρχουν διάφορες λύσεις \(\mathcal{O}(N^2)\) που βασίζονται στην \(\mathcal{O}(N^2\cdot K)\) αλλά απαριθμούν με έξυπνο τρόπο τα διαστήματα, ώστε να υπολογίζουν τα αθροίσματα πιο γρήγορα. Η πιο γενική από αυτές βασίζεται στη χρήση cumulative sums, τα οποία είναι μία τεχνική για να απαντάμε το άθροισμα οποιουδήποτε συνεχόμενου διαστήματος σε \(\mathcal{O}(1)\) χρόνο! Σε περίπτωση που δε τη γνωρίζετε ήδη, σταματήστε εδώ!! Ελέξτε τη λύση της Β Φάσης Γυμνασίου 31ου ΠΔΠ, και μετά γυρίστε πίσω.

Πολύ σύντομα, υποθέστε ότι η πρώτη θέση του πίνακα είναι η \(1\). Η σκέψη είναι να κρατάμε σε έναν πίνακα \(S[i]\) το άθροισμα \(A[1]+A[2]+\ldots +A[i-1]+A[i]\). Αυτό υπολογίζεται πολύ εύκολα σε γραμμικό χρόνο, αν προσέξουμε ότι \(S[1]=A[1]\) και \(S[i]=S[i-1]+A[i]\). Για ευκολία ορίζουμε \(S[0] = 0\).

Κατόπιν, το άθροισμα από \(A[j]+A[j+1]+\ldots+A[i-1]+A[i]\) είναι ίσο με \(S[i]-S[j-1]\) (δώστε δέκα λεπτά να καταλάβετε γιατί).

Η λύση είναι ίδια με την \(\mathcal{O}(N^2)\), με τη διαφορά ότι αντί να υπολογίζουμε το άθροισμα σε \(\mathcal{O}(K)\) χρόνο, το υπολογίζουμε σε \(\mathcal{O}(1)\) χρόνο.

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

#include <bits/stdc++.h>
const long MAXN = 2000000;
using namespace std;

long N, K, ans, A[MAXN+5], s[MAXN+5];

int main() {
  freopen("shops.in","r",stdin);
  freopen("shops.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  for(long i=1; i<=N; ++i) {
    scanf("%ld", &A[i]);
    s[i] = s[i-1] + A[i];
  }
  for(long right2=2*K; right2<=N; ++right2)
    for(long right1=K; right1<=right2-K; ++right1) {
      ans = max (s[right2]-s[right2-K]+s[right1]-s[right1-K], ans);
    }

  printf("%ld\n", ans);
  return 0;
}

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

Γνώσεις που θα χρειαστούμε: cumulative sums.

Ας υποθέσουμε ότι είμαστε βέβαιοι ότι το δεύτερο διάστημα αρχίζει ακριβώς στη θέση \(1000\). Τότε το πρώτο διάστημα πρέπει να τελειώνει το πολύ στη θέση \(999\). Για την ακρίβεια θα χρειαζόμασταν το βέλτιστο διάστημα μεγέθους \(K\) που τελειώνει μέχρι τη θέση \(999\).

Αυτό είναι πολύ εύκολο να το υπολογίσουμε για κάθε πιθανή θέση, όχι μόνο για την \(999\). Για τις πρώτες \(K-1\) θέσεις δεν ορίζεται, καθώς δε μπορεί το πρώτο διάστημα να τελειώνει πριν τη θέση \(K\). Για τη θέση \(K\), η απάντηση είναι το άθροισμα των πρώτων \(K\) θέσεων. Για επόμενες θέσεις (πχ για την θέση \(K+101\)) η απάντηση είτε τελειώνει στη θέση \(K+101\), και βρίσκουμε την απάντησή της σε \(\mathcal{O}(1)\) χρόνο με cumulative sums, είτε τελειώνει το πολύ στη θέση \(K+100\), το οποίο το έχουμε ήδη υπολογίσει. Επομένως ο παρακάτω κώδικας μας προϋπολογίζει σε ένα πίνακα τις βέλτιστες απαντήσεις, σε περίπτωση που μας ενδιαφέρει μόνο ένα διάστημα (επειδή θεωρούμε ότι αποφασίσαμε ήδη ποιο είναι το δεύτερο).

maxUpTo[K] = s[K]; //s[K]-s[0]==s[K], because s[0]=0
for(long i=K+1; i<=N; ++i)
    maxUpTo[i] = max(maxUpTo[i-1], s[i] - s[i-K]);

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

Πολυπλοκότητα: Οι πράξεις που κάνουμε είναι οι εξής: Η δημιουργία του πίνακα \(S\) για τα cumulative sums. Η δημιουργία του πίνακα maxUpTo. Τέλος, οι μαντεψιές για το δεύτερο διάστημα. Όλες αυτές οι πράξεις είναι γραμμικές, οπότε η τελική πολυπλοκότητα είναι \(\mathcal{O}(N)\).

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

#include <bits/stdc++.h>
const long MAXN = 2000000;
using namespace std;

long N, K, ans, A[MAXN+5], s[MAXN+5], maxUpTo[MAXN+5];

int main() {
  freopen("shops.in","r",stdin);
  freopen("shops.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  for(long i=1; i<=N; ++i) {
    scanf("%ld", &A[i]);
    s[i] = s[i-1] + A[i];
    if(i-K>=0) maxUpTo[i] = max(maxUpTo[i-1], s[i] - s[i-K]);
  }
  for(long right2=2*K; right2<=N; ++right2)
    ans = max (s[right2]-s[right2-K]+maxUpTo[right2-K], ans);

  printf("%ld\n", ans);
  return 0;
}

Όπως εύκολα παρατηρούμε δεν χρειαζόμαστε τον πίνακα \(A[]\) μετά την δημιουργία των cumulative sums. Ακόμα όμως και αν θέλαμε κάποιο στοιχείο του τότε:

long getA(long i){
	return s[i] - s[i-1];
}

Επίσης δεν χρειαζόμαστε ούτε τον πίνακα \(\mathit{maxUpTo}\) καθώς μας ενδιαφέρει μόνο το τελευταίο στοιχείο του.
Μία ακόμα ενδεικτική υλοποίηση παρουσιάζεται παρακάτω:

#include <cstdio>
#include <algorithm>

const long MAXN = 2000000;
using namespace std;

long N, K, ans, Ai, s[MAXN+5], maxUpTo;

int main() {
  freopen("shops.in","r",stdin);
  freopen("shops.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  for(long i=1; i<=N; ++i) {
    scanf("%ld", &Ai);
    s[i] = s[i-1] + Ai;
  }
  for(long i=K;i<=N-K;++i){
      //Δοκιμάζουμε κάθε πιθανή θέση που θα ξεκινά το δεύτερο (δεξιότερο)
      //κατάστημα. Προφανώς δεν έχει νόημα να ξεκινά πρίν τη θέση Κ διότι
      //θα επικάλυπτε το πρώτο (αριστερό) κατάστημα. Καταλαμβάνει τις 
      //θέσεις i+1,i+2,...,i+K άρα μπορεί να ξεκινά το πολύ στη θέση N-K
      //ώστε να τελειώνει στη θέση Ν
      
      maxUpTo = max(maxUpTo, s[i] - s[i-K]);
      //το maxUpTo διατηρεί το καλύτερο κέρδος για το πρώτο κατάστημα
      //όπου και αν αυτό έχει μπεί, αρκεί να τελειώνει το πολύ στη θέση i
      
      ans = max(ans, maxUpTo + s[i+K] - s[i]);
      //το s[i+K]-s[i] είναι το κέρδος του δεύτερου καταστήματος αν αυτό
      //ξεκινά στη θέση i+1 και τελειώνει στην i+K
  }

  printf("%ld\n", ans);
  return 0;
}

Μια ακόμα διαφορετική προσέγγιση χωρίς χρήση cumulative sums αλλά με χρήση sliding window όπου το αριστερό κατάστημα ολισθαίνει κατά μία θέση κάθε φορά προς τα δεξιά και αποθηκεύουμε το μεγαλύτερο κέρδος του στην κάθε θέση \(i\). Το δεξιό κατάστημα ξεκινά από το τέρμα δεξιό σημείο και ολισθαίνει κατά μια θέση κάθε φορά προς τα αριστερά. Το μεγαλύτερο άθροισμα των κερδών των δυο καταστημάτων είναι η απάντηση μας.

#include <cstdio>
#include <algorithm>

const long MAXN = 2000000;
using namespace std;

long N, K, ans, A[MAXN+5], maxUpTo[MAXN+5];

int main() {
  freopen("shops.in","r",stdin);
  freopen("shops.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  for(long i=1; i<=N; ++i) 
    scanf("%ld", &A[i]);

  for(long shopleft=0, i=1; i<=N-K; ++i){
      shopleft += A[i];
      if(i > K){
          //το shopleft έχει άθροισμα Κ+1 διαδοχικών θέσεων. 
          //Αφαίρεσε την παλιότερη.
          shopleft -= A[i-K];
      }
      maxUpTo[i] = max(shopleft,maxUpTo[i-1]);
  }
  for(long shopright=0, i=N; i>K; --i){
      shopright += A[i];
      if(i <= N-K){
          //το shopright έχει άθροισμα Κ+1 διαδοχικών θέσεων. 
          //Αφαίρεσε την παλιότερη.
          shopright -= A[i+K];
      }
      ans = max(ans, maxUpTo[i-1]+shopright);
  }
  printf("%ld\n", ans);
  return 0;
}