28ος ΠΔΠ Α' Φάση: Υπερυπολογιστής ARIS (aris) - Λύση

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

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

Η λύση αυτή είναι η πρώτη λύση που μπορεί να μας έρθει στο μυαλό και είναι ωμής βίας (brute force). Για κάθε πιθανή ομάδα \(m\) από το \(1\) ως το \(M\), μπορούμε να μετρήσουμε πόσες φορές εμφανίζεται ο αριθμός αυτής της ομάδας στα “παράθυρα εκτέλεσης”.

Η λύση είναι απλή στην υλοποίηση αλλά αργή (\(\max(NM) = 10^6\times10^6 = 10^{12}\)).

Το πρόγραμμα \(m\) έχει εκτελεστεί μόνο άμα υπάρχει τουλάχιστον μια εμφάνιση του \(m\) στα “παράθυρα εκτέλεσης”. Αλλιώς δεν έχει εκτελεστεί το \(m\).

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

Η υλοποίηση σε c++ είναι η ακόλουθη:

#include <cstdio>

const size_t MAXN = 1000000;

long N, M;
long windows[MAXN + 1];

int main () {
    // Διάβασμα του αρχείου εισόδου
    freopen("aris.in", "r", stdin);
    scanf("%ld %ld", &N, &M);
    for (long i = 0; i < N; ++i) { scanf("%ld", &windows[i]); }
    
    // Αρχικοποίηση των μεγεθών που ψάχνουμε
    long progs = 0; // Πόσα προγράμματα έχουν τρέξει
    long minCount = N; // Ελάχιστη υπολογιστική ισχύς
    long maxCount = 0; // Μέγιστη υπολογιστική ισχύς
    
    for (long m = 1; m <= M; ++m) {
        long count = 0; // Πόσες φορές βρήκαμε το πρόγραμμα m
        for (long i = 0; i < N; ++i) {
            if (windows[i] == m) { count ++; } // Βρήκαμε άλλο ένα παράθυρο με το m
        }
        // Άμα το count δεν είναι 0, βρήκαμε κι άλλο πρόγραμμα που εκτελέστηκε
        if (count > 0) {
			progs ++;
			// Αν το count είναι μεγαλύτερο από το ως τώρα μεγαλύτερο, ανανεώνουμε την
			// τιμή του μεγαλύτερου
			if (count > maxCount) { maxCount = count; }
			// Αντίστοιχα ανανεώνουμε την τιμή του μικρότερου
			if (count < minCount) { minCount = count; }
		}
    }
    
    // Αφού ελέγξουμε για όλα τα πιθανά Μ, έχουμε τις 
    // απαντήσεις οπότε τις εκτυπώνουμε
    freopen("aris.out", "w", stdout);
    printf("%ld %ld %ld\n", progs, minCount, maxCount);
    return 0;
}

Λύση πολυπλοκότητας \(\mathcal{O}(N + Μ)\), χώρου \(\mathcal{O}(M)\)

Έως τώρα αποθηκεύαμε τις τιμές για τα διάφορα \(m\) σε μια μεταβλητή (\(\mathit{count}\)) την οποία μηδενίζαμε σε κάθε επανάληψη. Αντί για αυτό μπορούμε να αποθηκεύουμε το \(\mathit{count}\) του κάθε \(m\) σε ένα πίνακα \(\mathit{counts}\). Το πλεονέκτημα αυτού είναι ότι δεν χρειάζεται να μετρήσουμε από την αρχή τα προγράμματα για κάθε τιμή του \(m\) αλλά αρκεί ένα πέρασμα.

Ας υποθέσουμε ότι \(N = 4\), \(M = 5\), και οι τιμές είναι \([1, 4, 2, 4]\).

Αρχικά ο πίνακας \(\mathit{counts}\) έχει τιμή \(0\) για κάθε \(m\).

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(0\)	\(0\)	\(0\)	\(0\)	\(0\)

Η πρώτη τιμή που διαβάζουμε από το αρχείο είναι \(1\). Άρα ενημερώνουμε τον πίνακά μας ότι συναντήσαμε το \(1\) μία φορά.

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(1\)	\(0\)	\(0\)	\(0\)	\(0\)

Η επόμενη τιμή είναι \(4\).

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(1\)	\(0\)	\(0\)	\(1\)	\(0\)

Μετά ακολουθεί το \(2\).

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(1\)	\(1\)	\(0\)	\(1\)	\(0\)

Τέλος, συναντάμε το \(4\) για δεύτερη φορά.

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(1\)	\(1\)	\(0\)	\(2\)	\(0\)

Αφού επεξεργαστήκαμε όλα τα “παράθυρα εκτέλεσης”, η τελική μορφή του πίνακα είναι

\(\mathbf{1}\)	\(\mathbf{2}\)	\(\mathbf{3}\)	\(\mathbf{4}\)	\(\mathbf{5}\)
\(1\)	\(1\)	\(0\)	\(2\)	\(0\)

Από τον πίνακα αυτό μπορούμε να αντλήσουμε κατ’ ευθείαν τις πληροφορίες που χρειαζόμαστε. Βλέπουμε πόσα προγράμματα έχουν τρέξει (αυτά που έχουν \(\mathit{count}\) > \(0\), δηλαδή το \(1\), το \(2\) και το \(4\)), όπως επίσης και ποια προγράμματα έχουν τον ελάχιστο αριθμό εμφανίσεων (\(1\), \(2\) με τιμή \(1\)) και ποια το μέγιστο (\(4\) με τιμή \(2\)). Με ένα πέρασμα αυτού του πίνακα βρίσκουμε την μέγιστη τιμή, την ελάχιστη μη μηδενική τιμή, και το πλήθος των μη μηδενικών τιμών.

Σε κώδικα:

#include <cstdio>

const size_t MAXN = 1000000;

long N, M;
long counts[MAXN + 1]; // Αρχικοποίηση του πίνακα counts με μηδενικά

int main () {
    // Διάβασμα του αρχείου εισόδου
    freopen("aris.in", "r", stdin);
    scanf("%ld %ld", &N, &M);
    for (long i = 0; i < N; ++i) {
        long m;
        scanf("%ld", &m);
        counts[m] ++; // Συναντήσαμε την τιμή m, άρα αυξάνουμε την θέση m του πίνακα
    }    

    // Αρχικοποίηση των μεγεθών που ψάχνουμε
    long progs = 0;
    long minCount = N;
	long maxCount = 0;    

    for (long m = 1; m <= M; ++m) {
        if (counts[m] > 0) {
            // Μη μηδενική τιμή
            // Αυξάνουμε τον αριθμό των προγραμμάτων
            // και συγκρίνουμε με τo μέχρι στιγμής μέγιστo
            // και ελάχιστo
            progs ++;
            if (counts[m] < minCount) { minCount = counts[m]; }
            if (counts[m] > maxCount) { maxCount = counts[m]; }
        }
    }
    
    // Αφού ελέγξουμε για όλα τα πιθανά Μ, έχουμε τις 
    // απαντήσεις οπότε τις εκτυπώνουμε
    freopen("aris.out", "w", stdout);
    printf("%ld %ld %ld\n", progs, minCount, maxCount);
    return 0;
}