33ος ΠΔΠ Γ' Φάση: Ο πόλεμος των τσιφλικάδων (landfight) - Λύση

Συγγραφέας: Κωνσταντίνος Μποκής

Πολύ αργή λύση (brute force)

Η πιο απλή λύση είναι για κάθε \(L\) χωράφια του αριστερού τσιφλικά, να ελέγξουμε όλα τα δυνατά \(R\) χωράφια του δεξιού τσιφλικά. Για να αθροίσουμε τα πρώτα \(L\) στοιχεία \(x_1+x_2+\dots+x_L\) θα κάνουμε ένα ακόμα for, άρα συνολική πολυπλοκότητα \(\mathcal{O}(N^3)\).

#include <cstdio>
#include <algorithm>

const long MAXN = 1'000'002L;

long A[MAXN];

long calcsum(long i,long j){
    long sum = 0L;
    while(i<=j)
        sum += A[i++];
    return sum;
}
int main(){
    freopen("landfight.in","r",stdin);
    freopen("landfight.out","w",stdout);
    
    long N;
    scanf("%ld",&N);
    for(long i=1;i<=N;i++)
        scanf("%ld",A+i);
    
    long ans = N;
    for(long i=0;i<=N;i++){
        for(long j=i+1;j<=N+1;j++){
            if(calcsum(1,i) == calcsum(j,N+1)){
                //fprintf(stderr,"N=%ld, calcsum[%ld,%ld]=[%ld,%ld]=%ld\n",N,1,i,j,N+1,calcsum(j,N+1));
                ans = std::min(ans,j-i-1);
                //Δεν έχει νόημα να συνεχίσουμε γιατί τα υπόλοιπα διαστήματα είναι μεγαλύτερα
                break;
            }
        }
    }

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

Λύση με χρήση prefix sums (20% της βαθμολογίας)

Στην παρακάνω λύση αποφεύγουμε τα loop υπολογισμού αθροισμάτων κάνοντας προϋπολογισμό των prefix sums σε έναν πίνακα \(\mathit{PS}\), δηλαδή

\[\mathit{PS}_i=x_1+x_2+ \dots + x_i=\sum_{j=1}^i {A_j}\]

Αντίστοιχα, θα χρειαστούμε και τα suffix sums¹ για το άθροισμα των τελευταίων \(R\) στοιχείων σε έναν πίνακα \(\mathit{SS}\) με

\[\mathit{SS}_i=x_i+x_{i+1}+\dots+x_N=\sum_{j=i}^N{A_j}\]

Χρειάζεται προσοχή στην ειδική περίπτωση που o ένας ή ο άλλος τσιφλικάς δεν θα πάρει κανένα χωράφι. Στην περίπτωση αυτή θα υπάρχει suffix sum ή prefix sum με άθροισμα \(0\). Για να καλυφθούν οι περιπτώσεις αυτές, ξεκινάμε τον έλεγχο των prefix sums από τη θέση \(0\) (με τιμή \(0\)) ενώ τον πίνακα suffix sums από τη θέση \(\mathit{SS}_{N+1}\) (με τιμή \(0\)). Συνολική πολυπλοκότητα της λύσης είναι \(\mathcal{O}(N^2)\).

#include <cstdio>
#include <algorithm>

const long MAXN = 1'000'002L;

long A[MAXN];

//Στον υπολογισμό των prefix sums χρησιμοποιούμε το προηγούμενο 
//στοιχείο για να υπολογίσουμε το τρέχον. Στον πίνακα A
//χρησιμοποιούνται τα στοιχεία 1 έως και N άρα στον PS 
//χρησιμοποιούνται τα στοιχεία από τη θέση 0 έως και τη N
long PS[MAXN];

//Στον υπολογισμό των suffix sums χρησιμοποιούμε το επόμενο
//στοιχείο για να υπολογίσουμε το τρέχον. Στον πίνακα A
//χρησιμοποιούνται τα στοιχεία 1 έως και N άρα στον SS
//χρησιμοποιούνται τα στοιχεία από τη θέση 1 έως και την N+1
long SS[MAXN];

int main(){
    freopen("landfight.in","r",stdin);
    freopen("landfight.out","w",stdout);
    
    long N;
    scanf("%ld",&N);
    for(long i=1;i<=N;i++){
        scanf("%ld",A+i);
        PS[i] = PS[i-1] + A[i];
    }
    for(long i=N;i>0;i--)
        SS[i] = SS[i+1] + A[i];
    
    long ans = N;
    for(long i=0;i<=N;i++){
        for(long j=i+1;j<=N+1;j++){
            //Το j==N+1 αντιστοιχεί στην περίπτωση που δεν πάρει χωράφια ο δεξιός
            //Το i==0 για την περίπτωση που ο αριστερός δεν πάρει χωράφια
            if(PS[i] == SS[j]){
                ans = std::min(ans, j-i-1);
                break;
                //Δεν έχει νόημα να συνεχίσουμε γιατί τα υπόλοιπα διαστήματα είναι μεγαλύτερα
            }
        }
    }
    printf("%ld\n",ans);
    return 0;
}

Στην παραπάνω λύση, μπορεί να γίνει μια μικρή βελτίωση στο εσωτερικό loop. Όταν έχουμε υπολογίσει κάποια τιμή \(\mathit{ans}\) έως τώρα, δεν μας ενδιαφέρει να ελέγχουμε τιμές χειρότερες από την τιμή αυτή. Το δεύτερο loop μπορεί να γραφτεί ως:

    for(long j=i+1,n2=min(N,ans+i+1);j<n2;j++)

Λύση με χρήση δύο pointers (70% της βαθμολογίας)

Σύμφωνα με τους περιορισμούς της εκφώνησης, για περιπτώσεις ελέγχου συνολικής αξίας 70% έχουμε μόνο μη μηδενικές θετικές τιμές για τα \(x_i\). Αποτέλεσμα αυτού, είναι τόσο τα prefix sums όσο και τα suffix sums να αποτελούν γνησίως μονότονες ακολουθίες εφόσον:

\[\mathit{PS}_{i+1}=\mathit{PS}_i+x_{i+1} > \mathit{PS}_i\] \[\mathit{SS}_i=\mathit{SS}_{i+1}+x_i > \mathit{SS}_{i+1}\]

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

Απόδειξη:
Έστω ότι υπάρχουν δυο κοινά σημεία των δύο ακολουθιών στις θέσεις \(i\) και \(j\) με \(i<j\) άρα \(\mathit{PS}_{i}=\mathit{SS}_{i}=\mathit{PS}_{j}=\mathit{SS}_{j}\). Εφόσον \(i<j\) και οι ακολουθίες είναι γνησίως μονότονες, τότε \(\mathit{PS}_{i} \lt \mathit{PS}_{j}\) πράγμα άτοπο.

Παρατηρήστε το παρακάτω σχήμα που αντιστοιχεί στο πρώτο παράδειγμα της εκφώνησης:

Διάγραμμα με την τιμή του prefix και suffix sum για κάθε i

Οι πράσινες κουκίδες αντιστοιχούν στην ακολουθία των prefix sums και οι μωβ στα suffix sums. Μας ενδιαφέρει να εντοπίσουμε τιμές του κατακόρυφου άξονα (τιμές sum) που να υπάρχουν και στις δύο ακολουθίες. Τέτοιες τιμές είναι οι \(0\),\(10\),\(18\) και \(28\). Από αυτές αποδεκτές είναι μόνο η τιμή \(0\) (με απάντηση \(7\) αδιάθετα χωράφια) και η \(10\) (με απάντηση \(2\) αδιάθετα χωράφια). Οι τιμές \(18\) και \(28\) βρίσκονται μετά τη διασταύρωση των δυο ακολουθιών και απορρίπτονται διότι τα χωράφια του ενός τσιφλικά έχουν υπερκαλύψει χωράφια του άλλου.

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

#include <cstdio>
#include <algorithm>

const long MAXN = 1'000'002L;

long A[MAXN];

int main(){
    freopen("landfight.in","r",stdin);
    freopen("landfight.out","w",stdout);
    
    long N;
    scanf("%ld",&N);
    for(long i=1;i<=N;i++)
        scanf("%ld",A+i);
    
    long ans=N,prefix=0,suffix=0,lptr=0,rptr=N+1;
    while(lptr<rptr){
        if(prefix == suffix){
            ans = std::min(ans,rptr-lptr-1);
            prefix += A[++lptr];
            suffix += A[--rptr];
        } else if(prefix < suffix)
            prefix += A[++lptr];
        else //suffix < prefix
            suffix += A[--rptr];
    }

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

Λύση με δυαδική αναζήτηση στα suffix sums (100% της βαθμολογίας)

Για κάθε δυνατό πλήθος αριστερών χωραφιών θέλουμε να ελέγξουμε μόνο τα suffix sums με ίδια τιμή. Ας ταξινομήσουμε αυτά τα suffix sums, διατηρώντας τις θέσεις που αυτά εμφανίστηκαν, ώστε να μπορούμε να κάνουμε δυαδική αναζήτηση σε αυτά. Δηλαδή για κάθε πλήθος \(i\) χωραφιών του αριστερού τσιφλικά με prefix sum \(\mathit{PS}_i\), ψάχνουμε τις θέσεις που εμφανίζονται suffix sums με \(\mathit{SS}_j=\mathit{PS}_i\) και \(i\lt j\). Θα χρησιμοποιήσουμε έναν πίνακα με pair από τη βιβλιοθήκη stl της C++, όπου αποδίδουμε στο πρώτο στοιχείο του την τιμή του suffix sum \(\mathit{SS}_i\) και στο δεύτερο τη θέση \(i\) που βρέθηκε το suffix sum αυτό. Η ταξινόμηση στα pair γίνεται με το πρώτο στοιχείο και σε περίπτωση ισότητας και με το δεύτερο. Συνολική πολυπλοκότητα της λύσης είναι \(\mathcal{O}(N\cdot \log{N})\).

#include <cstdio>
#include <algorithm>
using namespace std;

const long MAXN = 1'000'002L;

long A[MAXN], PS[MAXN];
pair<long,long> SS[MAXN];

int main(){
    freopen("landfight.in","r",stdin);
    freopen("landfight.out","w",stdout);
    
    long N;
    scanf("%ld",&N);
    for(long i=1;i<=N;i++){
        scanf("%ld",A+i);
        PS[i] = PS[i-1] + A[i];
    }
    for(long sum=0L, i=N;i>0;i--){
        sum +=A[i];
        SS[i] = {sum,i};
    }
    SS[0] = {0,N+1};
    sort(SS,SS+N+1);
    
    long ans = N;
    for(long i=0;i<=N;i++){
        pair<long,long> test = {PS[i],i+1};
        size_t pos = lower_bound(SS,SS+N+1,test) - SS;
        if(pos != N+1 && SS[pos].first==PS[i])
            ans = min(ans,SS[pos].second-i-1);
    }
    
    printf("%ld\n",ans);
    return 0;
}

Λύση με χρήση αραιού πίνακα από δομές αποθήκευσης (100% της βαθμολογίας)

Γνώσεις που θα χρειαστούμε: unordered_map, stack

Αντί να βάλουμε τα suffix sums σε έναν πίνακα και να τον ταξινομήσουμε, θα μπορούσαμε να τα έχουμε σε έναν δισδιάστατο πίνακα όπου η πρώτη διάσταση είναι η τιμή του suffix sum και στη δεύτερη διάσταση του θα έχουμε τις θέσεις που συναντήσαμε το suffix sum. Οι τιμές των suffix sum όμως δεν είναι συνεχείς και μπορεί να έχουν τιμές από \(-10^9\) έως \(10^9\) σύμφωνα με τους περιορισμούς της εκφώνησης του προβλήματος. Ο συνολικός αριθμός των διαφορετικών τιμών δεν μπορεί όμως να ξεπεράσει το \(N\), άρα χρειαζόμαστε μια δομή να αποθηκεύσουμε έναν αραιό πίνακα από πίνακες όπως το map ή το unordered_map που περιέχονται στην stl της C++.

Παράδειγμα:

    unordered_map<long, vector<long>> M;
    M[0].push_back(N+1);//περίπτωση κανενός χωραφιού στο δεξιό τσιφλικά
    for(long sum=0,k=N;k>0;k--){
        sum += A[k];
        M[sum].push_back(k);
    }

Παρατήρηση: Στον κάθε πίνακα vector, οι θέσεις \(k\) που αποθηκεύονται μειώνονται σε κάθε βήμα της επανάληψης καθώς υπολογίζουμε τα suffix sums από τη θέση \(N\) προς τη θέση \(1\). Άρα κάθε vector περιέχει μια γνησίως φθίνουσα ακολουθία.

Ας δούμε ένα παράδειγμα με το ακόλουθο test case:

landfight.in
11 -3 -5 5 4 -9 5 -2 -1 0 3 7

Το παρακάτω διάγραμμα αναπαριστά την ακολουθία των suffix sums

και αποθηκεύεται στο unordered_map (πράσινα κελιά) από vectors (κίτρινα κελιά) του παρακάτω σχήματος, αναπαριστώντας έναν δισδιάστατο αραιό πίνακα

Μια απλοποιημένη και μη αποδοτική αναζήτηση² της απάντησης του προβλήματος, μπορεί να γίνει ως εξής:

    long ans = N;
    for(long prefix=0,i=1;i<=N;i++){
        prefix += A[i];
        for(long j:M[prefix]){
            if(j>i)
                ans = min(ans,j-i-1);
        }
    }

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

Μια λύση με vector ακολουθεί:

#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

const long MAXN = 1'000'001L;

long A[MAXN];
unordered_map<int, vector<long> > M;

int main(){
    freopen("landfight.in","r",stdin);
    freopen("landfight.out","w",stdout);
    
    long N;
    scanf("%ld",&N);
    for(long i=1;i<=N;i++)
        scanf("%ld",A+i);
    
    M[0].push_back(N+1);
    for(long suffix=0L,i=N;i>0;i--){
        suffix +=A[i];
        M[suffix].push_back(i);
    }
    
    long ans = N;
    for(long prefix=0L,i=0;i<=N;i++){
        prefix += A[i];
        if(M.find(prefix) == M.end())
            continue;
        vector<long>& V = M[prefix];
        //διέγραψε τα ξεπερασμένα
        while(!V.empty() && V.back()<=i)
            V.pop_back();
        if(!V.empty())
            ans = min(ans,V.back()-i-1);
    }
    
    printf("%ld\n",ans);
    return 0;
}

Αντί για vector μπορούμε να χρησιμοποιήσουμε και άλλες δομές που μας επιτρέπουν διαγραφή στοιχείων όπως η διπλά συνδεδεμένη λίστα³ ή το stack⁴.

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

Η ύπαρξη των suffix sum κάνει πιο κατανοητό τον κώδικα αλλά δεν είναι απαραίτητη, διότι: \(SS_i = PS_{n}-PS_{i-1}\) ↩
Ο απλοποιημένος αυτός κώδικας δεν είναι αποδοτικός και έχει πολυπλοκότητα \(\mathcal{O}(N^2)\) καθώς μπορεί για παράδειγμα ένα test case να έχει όλα τα \(x_i=0\) οπότε το vector στη θέση \(M_0\) θα έχει \(N\) στοιχεία. Ένα ακόμα πρόβλημα του παραπάνω κώδικα είναι ότι δεν ελέγχει αν υπάρχει το στοιχείο \(M_{\mathit{prefix}}\) πριν το χρησιμοποιήσει, με αποτέλεσμα τη δημιουργία κενών στοιχείων στο unordered_map. ↩
Ενδεικτική λύση με διπλά συνδεδεμένη λίστα ↩
Ενδεικτική λύση με stack ↩