22ος ΠΔΠ Α' Φάση: Hydrogen (hydrogen) - Λύση

Λύση με Bubble Sort

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

Για διευκόλυνσή μας μπορούμε να ορίσουμε ένα struct, έστω car_part, το οποίο θα περιέχει τον αριθμό ενός τμήματος του αυτοκινήτου και τη συχνότητα εμφάνισης βλαβών υπευθυνότητας του κατασκευαστή σε αυτό. Έπειτα μπορούμε να ορίσουμε έναν πίνακα, έστω \(A\), στον οποίο θα αποθηκεύουμε structs αυτού του τύπου ανάλογα με την είσοδο, αγνοώντας τα τμήματα με μηδενική συχνότητα βλαβών. Αν ταξινομήσουμε τον πίνακα αυτό σε φθίνουσα σειρά με βάση τη συχνότητα βλαβών και επιλύοντας ισοβαθμίες με βάση τον αριθμό τμήματος, τότε οι αριθμοί των τμημάτων των αυτοκινήτων θα έχουν την επιθυμητή σειρά.

Η ταξινόμηση αυτή μπορεί να γίνει με bubblesort. Αυτό σημαίνει ότι θα κάνουμε περάσματα του πίνακα \(A\) από το τέλος προς την αρχή σταματώντας κάθε φορά μία θέση δεξιότερα. Με άλλα λόγια, το πρώτο πέρασμα θα ξεκινάει από τη θέση \(L\) (δεξιότερη θέση) και θα τελειώνει στη θέση \(1\), το επόμενο από την \(L\) ως τη \(2\), το επόμενο από την \(L\) ως την \(3\), κι ούτω καθεξής. Σε κάθε πέρασμα αλλάζουμε σειρά στα αταξινόμητα γειτονικά στοιχεία. Μετά από κάθε πέρασμα το τελευταίο στοιχείο που επισκεφθήκαμε βρίσκεται στη σωστή θέση.

Επειδή απαιτείται ένα διάβασμα των δεδομένων για \(C\) τμήματα αυτοκινήτου και κατόπιν ταξινομούμε τα \(L\) από αυτά που δεν έχουν μηδενικό αριθμό σφαλμάτων, τότε θέλουμε \(\mathcal{O}(C)\) χρόνο για το διάβασμα και \(L\) περάσματα του πίνακα για την ταξινόμηση. Τα πρώτα \(\frac{L}{2}\) περάσματα θα δούνε τουλάχιστον \(\frac{L}{2}\) στοιχεία, και συνεπώς η ταξινόμηση θα χρειαστεί τουλάχιστον \(\frac{L^2}{4}\) πράξεις. Επίσης κανένα πέρασμα δε θα κάνει περισσότερο από \(L\) πράξεις, και συνεπώς η ταξινόμηση θα χρειαστεί το πολύ \(L^2\) πράξεις. Καταλήγουμε ότι η χρονική πολυπλοκότητα του αλγορίθμου, στη χειρότερη περίπτωση, είναι \(\Theta(C+L^2)\). Αυτή η πολυπλοκότητα είναι οριακά καλή για \(L=10000\), κι αν δεν κάνουμε καλή υλοποίηση, ίσως χάσουμε λίγα testcases. Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(L)\).

#include <cstdio>
#include <algorithm>
using namespace std;
const long MAXL = 10005;
struct car_part {
    long id, freq;
};

car_part A[MAXL];

int main() {
    freopen("hydrogen.in", "r", stdin);
    freopen("hydrogen.out", "w", stdout);
    long C, L = 0;
    scanf("%ld", &C);
    for (long i = 0; i < C; i++) {
        long id, freq;
        scanf("%ld %ld", &id, &freq);
        // Αποθήκευση δεδομένων για τμήματα με βλάβες ευθύνης κατασκευαστή
        if (freq)
           A[L++] = { id, freq };
    }
    // Εκτύπωση πλήθους τμημάτων με βλάβες ευθύνης κατασκευαστή
    printf("%ld\n", L);
    // Ταξινόμηση με bubblesort
    for (long i = 0; i < L; i++) {
        // Πέρασμα από δεξιά προς τα αριστερά
        for (long j = L - 1; j > i; j--) {
            // Αντιμετάθεση γειτονικών αταξινόμητων στοιχείων
            if (A[j].freq > A[j - 1].freq || A[j].freq == A[j - 1].freq && A[j].id < A[j - 1].id)
                swap(A[j], A[j - 1]);
        }
        // Εμφάνιση έτοιμων αποτελεσμάτων
        printf("%ld\n", A[i].id);
    }
    return(0);
}

Καλύτερη λύση με Quicksort

Μπορούμε να βελτιώσουμε τον προηγούμενο αλγόριθμο από άποψη χρονικής πολυπλοκότητας, αλλά και από άποψη έκτασης και απλότητας κώδικα, εάν την ταξινόμηση την κάνουμε με χρήση της μεθόδου quicksort μέσω της συνάρτησης sort που είναι υλοποιημένη στη βιβλιοθήκη algorithm. Θα χρειαστεί να χρησιμοποιήσουμε μία συνάρτηση σύγκρισης, έστω comp, για να ορίσουμε ότι η ταξινόμηση πρέπει να είναι πρωτίστως φθίνουσα ως προς τη συχνότητα βλαβών λόγω κατασκευαστή και δευτερευόντως αύξουσα ως προς τον αριθμό τμήματος.

Η χρονική πολυπλοκότητα μειώνεται λόγω της νέας μεθόδου ταξινόμησης σε \(\mathcal{O}(C + L\log{L})\) που είναι αρκετά καλή για να περάσουμε όλα τα testcases. Η χωρική πολυπλοκότητα είναι και πάλι \(\mathcal{O}(L)\).

#include <cstdio>
#include <algorithm>
using namespace std;
const long MAXL = 10005;
struct car_part {
    long id, freq;
};

car_part A[MAXL];
bool comp(car_part a, car_part b) {
   if (a.freq == b.freq) return a.id < b.id;
   return a.freq > b.freq;
}

int main() {
    freopen("hydrogen.in", "r", stdin);
    freopen("hydrogen.out", "w", stdout);
    long C, L = 0;
    scanf("%ld", &C);
    for (long i = 0; i < C; i++) {
        long id, freq;
        scanf("%ld %ld", &id, &freq);
        // Αποθήκευση δεδομένων για τμήματα με βλάβες ευθύνης κατασκευαστή
        if (freq)
           A[L++] = { id, freq };
    }
    // Εκτύπωση πλήθους τμημάτων με βλάβες ευθύνης κατασκευαστή
    printf("%ld\n", L);
    // Ταξινόμηση με quicksort
    sort(A, A + L, comp);
    // Εμφάνιση αποτελεσμάτων
    for (long i = 0; i < L; i++) {
        printf("%ld\n", A[i].id);
    }
    return(0);
}