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

32ος ΠΔΠ B' Φάση: Πάμε πάλι διακοπές (longsumk) - Λύση

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

Σημείωση: Το σημαντικό αυτού του προβλήματος είναι να μάθετε την τεχνική cumulative sums. Για μία εισαγωγή σε αυτήν, θα προτείναμε να διαβάσετε πολύ προσεκτικά το πρόβλημα Β Φάσης Γυμνασίου 31ου ΠΔΠ.

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

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

Για παράδειγμα, έστω ότι ο πίνακας μας είναι:

\[110,~10,~20,~111,~30\]

και ζητάμε \(K=30\).

Υπάρχουν δύο υποψήφια διαστήματα, το \(10,~20\) και το \(30\). Το μέγιστου μήκους διάστημα είναι το \(10,~20\) που αποτελείται από δύο αριθμούς, οπότε η απάντησή μας είναι \(2\).

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

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

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

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

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

Η λύση αυτή πρόκειται για μία απλή δοκιμή όλων των πιθανών διαστημάτων. Κατόπιν εξετάζουμε αυτό ακριβώς που μας υπαγορεύει η εκφώνηση, αν δηλαδή το άθροισμα είναι \(K\).

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

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

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

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

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

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

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

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

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

Υπάρχουν διάφορες λύσεις \(\mathcal{O}(N^2)\) που βασίζονται στην \(\mathcal{O}(N^3)\) αλλά απαριθμούν με έξυπνο τρόπο τα διαστήματα, ώστε να υπολογίζουν τα αθροίσματα πιο γρήγορα. Η πιο γενική από αυτές βασίζεται στη χρήση prefix sums, ή 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^3)\), με τη διαφορά ότι αντί να υπολογίζουμε το άθροισμα σε \(\mathcal{O}(N)\) χρόνο, το υπολογίζουμε σε \(\mathcal{O}(1)\) χρόνο.

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

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

int main() {
  freopen("longsumk.in","r",stdin);
  freopen("longsumk.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 i=1; i<=N; ++i)
    for(long j=1; j<=i; ++j)
      if(s[i]-s[j-1]==K && ans < i-j+1)
        ans = i-j+1;

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

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

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

Τώρα που μάθαμε τα cumulative sums, είμαστε έτοιμοι να τα αξιοποιήσουμε. Θα προσπαθήσουμε να βρούμε το μέγιστου μήκους διάστημα που έχει άθροισμα \(K\) και τελειώνει ακριβώς στη θέση \(1000\). Αν μπορέσουμε να το πετύχουμε γρήγορα, επαναλαμβάνουμε για κάθε πιθανό τέλος του διαστήματος, και κρατάμε τη βέλτιστη απάντηση (μέγιστη).

Τι ακριβώς ζητάμε; Να βρούμε μία αρχική θέση \(i\) ώστε το άθροισμα μεταξύ \(i\) και \(1000\) να είναι ακριβώς \(K\). Με τα εργαλεία που μας δίνουν τα cumulative sums, αυτό μεταφράζεται ως:

Βρες το ελάχιστο \(i\) ώστε \(S[1000] - S[i-1] = K\). Με απλούστατα μαθηματικά παίρνουμε \(S[i-1] = S[1000]-K\). Προσέξτε ότι αφού ξέρουμε και το \(S[1000]\) και το \(K\), ξέρουμε και τη διαφορά τους. Άρα ψάχνουμε μία θέση \(i\) με συγκεκριμένη τιμή \(S[i]\), για παράδειγμα μία θέση \(i\) με τιμή \(150\).

Το μόνο που μας λείπει λοιπόν είναι ένας τρόπος να ρωτάμε για μία τιμή, και να βρίσκουμε την ελάχιστη θέση που περιέχει αυτή την τιμή. Αυτό λύνεται με ένα map/unordered_map της C++. Κάνουμε ένα πέρασμα στον πίνακα \(S\), και για κάθε τιμή που εντοπίζουμε, ενημερώνουμε ένα map για την θέση που περιείχε αυτή την τιμή (και μάλιστα την ελάχιστη θέση, αν υπάρχουν πολλές). Κατόπιν ακολουθούμε την παραπάνω τεχνική.

Πολυπλοκότητα: Οι πράξεις που κάνουμε είναι οι εξής:

  1. Η δημιουργία του πίνακα \(S\). Χρόνος \(\mathcal{O}(N)\).
  2. Ένα πέρασμα για να ενημερώσουμε το map ή το unordered_map που θα χρησιμοποιήσουμε. Χρόνος \(\mathcal{O}(N \log{N})\) ή \(\mathcal{O}(N)\).
  3. Κατόπιν ένα πέρασμα πάνω σε όλα τα πιθανά υποψήφια τέλη, και ένα ερώτημα κάθε φορά στο map ή το unordered_map. Χρόνος \(\mathcal{O}(N \log{N})\) ή \(\mathcal{O}(N)\).

Σημείωση: Εν προκειμένου αξίζουν τα unordered_map. Γενικά τα map είναι ελάχιστα πιο αργά και προσφέρουν πολλές περισσότερες δυνατότητες, οπότε υπάρχει κόσμος που μαθαίνει μόνο αυτά.

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

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

long N, K, ans, A[MAXN+5], s[MAXN+5];
unordered_map<long,long> positionOfValue;

int main() {
  freopen("longsumk.in","r",stdin);
  freopen("longsumk.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 i=N; i>=1; --i) positionOfValue[s[i]]=i;
  for(long i=1; i<=N; ++i)
    if (positionOfValue.find(s[i] - K) != positionOfValue.end()) //s[i]-K exists
      ans = max(ans,i-positionOfValue[s[i]-K]);

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

Εναλλακτική βέλτιστη λύση

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

Θα λέμε ότι ένας υποπίνακας είναι υποψήφιος, αν έχει άθροισμα ακριβώς \(K\) και δε μπορεί να επεκταθεί προς τα αριστερά (δηλαδή δεν έχει στην ακριβώς αριστερά του θέση τιμή \(0\)).

Παρατηρούμε κάτι πολύ απλό. Έστω ότι έχουμε έναν υποψήφιο υποπίνακα μεταξύ των θέσεων \(3\) και \(7\). Αν υπάρχει κι άλλος υποψήφιος υποπίνακας ο οποίος τελειώνει στη θέση \(10\), τότε αποκλείεται να αρχίζει πριν τη θέση \(3\).

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

Πώς μπορούμε να αξιοποιήσουμε αυτή την ιδέα; Κάθε φορά που βρίσκουμε έναν υποψήφιο υποπίνακα, προσπαθούμε να εντοπίσουμε τον επόμενο. Έτσι προχωράμε το δεξί του άκρο κατά μία θέση. Ως αποτέλεσμα, το άθροισμα που θα έχουμε θα είναι μεγαλύτερο από \(K\), αφού ήταν ακριβώς \(K\) προηγουμένως. Από την παρατήρησή μας, αυτό σημαίνει ότι αν υπάρχει υποψήφιος υποπίνακας που τελειώνει στο νέο δεξί άκρο, τότε το νέο αριστερό άκρο δε βρίσκεται αριστερότερα. Άρα προχωράμε το δεξί άκρο μέχρι το άθροισμα να πάψει να είναι μεγαλύτερο από \(K\). Προσέξτε ότι μπορεί να προχωρήσουμε πάρα πολλά βήματα προς τα δεξιά το αριστερό άκρο (πχ \(\frac{N}{2}\) βήματα).

Αν με αυτό τον τρόπο εντοπίσουμε υποπίνακα με άθροισμα \(K\), είμαστε χαρούμενοι. Αλλιώς προχωράμε άλλη μία θέση το δεξί άκρο, και επαναλαμβάνουμε την ίδια διαδικασία.

Η ορθότητα του αλγορίθμου μας προκύπτει από το γεγονός ότι δοκιμάζουμε κάθε πιθανό δεξί άκρο. Λόγω της παρατήρησής μας, το αριστερό δε χρειάζεται ποτέ να πάει αριστερά. Προφανώς επίσης δε χρειάζεται να προχωρήσει περισσότερο από όσο το προχωράμε, αφού σταματάμε όταν το άθροισμα είναι είτε ακριβώς \(K\), είτε μικρότερο από \(K\).

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

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

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

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

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

int main() {
  freopen("longsumk.in","r",stdin);
  freopen("longsumk.out","w",stdout);
  scanf("%ld %ld", &N, &K);
  long left=1, sum=0, ans=0;
  for(long right=1; right<=N; ++right) {
    scanf("%ld", &A[right]);
    sum += A[right];
    while (sum > K) {
      sum -= A[left];
      ++left;
    }
    if (sum==K && ans < right-left+1)
      ans = right-left+1;
  }

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