29ος ΠΔΠ Α' Φάση: Πανελλήνιο σχολικό δίκτυο (sch) - Λύση

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

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

Οι λύσεις που θα παρουσιάσουμε ακολουθούν την εξής μορφή:

καταμέτρηση εμφανίσεων για το κάθε στοιχείο.
Εύρεση των τριών πιο συχνών στοιχείων.

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

1. Καταμέτρηση ίδιων στοιχείων

Brute force \(\mathcal{O}(NS)\)

Για κάθε στοιχείο πιθανό στοιχείο \(s\in [1, 10.000]\), διατρέχουμε όλον τον πίνακα και μετράμε πόσες φορές εμφανίζεται.

// Διατρέχουμε όλες τις δυνατές τιμές.
for (int s = 1; s <= MAXS; ++s) {
  count = 0;
  // Διατρέχουμε όλα τα στοιχεία του πίνακα.
  for (long i = 0; i < N; ++i) {
    if (A[i] == s) ++count;
  }
  // Κάνουμε κάτι με το count
  // ...
}

Ο αλγόριθμος αυτός έχει πολυπλοκότητα \(\mathcal{O}(NS)\) και μνήμη \(\mathcal{O}(N)\).

Ταξινόμηση και καταμέτρηση

Αν ταξινομήσουμε τον πίνακα, τότε όλα τα ίδια στοιχεία θα έρθουν το ένα δίπλα στο άλλο. Άρα το πρόβλημα της καταμέτρησης ανάγεται στην καταμέτρηση ίδιων γειτονικών στοιχείων.

#include <algorithm>

//...

A[N] = S + 1; // Βοηθάει στην καταμέτρηση του μεγαλύτερου στοιχείου.
std::sort(A, A + N);
long prev = -1; // Το προηγούμενο στοιχείο που συναντήσαμε.
long count = 0;
for (long i = 0; i <= N; ++i) {
  if (A[i] == prev) ++count;
  else {
    if (prev != -1) {
      // Κάνουμε κάτι με το count
      // ...
    }
    prev = A[i];
    count = 1;
  }
}

Ο αλγόριθμος αυτός θέλει \(\mathcal{O}(N \log N)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.

Χρήση map

Θα διατηρήσουμε ένα map \(\mathit{counts}\). Διατρέχοντας τον πίνακα \(A\), το \(\mathit{counts}[v]\) κρατάει πόσες φορές που εμφανίζεται το στοιχείο \(v\).

#include <map>

//...

map<int, long> count;
// Διατρέχουμε όλα τα στοιχεία του πίνακα.
for (long i = 0; i < N; ++i) {
  ++counts[A[i]];
}

Υπάρχουν το πολύ \(\mathcal{O}(S)\) στοιχεία μέσα στον πίνακα, άρα κάθε προσθήκη θέλει \(\mathcal{O}(\log S)\) χρόνο. Συνεπώς, ο αλγόριθμος έχει πολυπλοκότητα \(\mathcal{O}(N\log S)\) και μνήμη \(\mathcal{O}(N)\).

Πίνακας καταμέτρησης

Επειδή το εύρος των στοιχείων είναι μικρό, μπορούμε να διατηρήσουμε έναν πίνακα \(\mathit{counts}[0..S]\), αντί για map.

const size_t MAXS = 10000;
//...

long counts[MAXS + 1];
// Διατρέχουμε όλα τα στοιχεία του πίνακα.
for (long i = 0; i < N; ++i) {
  ++counts[A[i]];
}

Ο αλγόριθμος αυτός έχει πολυπλοκότητα \(\mathcal{O}(N)\) και μνήμη \(\mathcal{O}(S)\).

2. Εύρεση των τριών πιο συχνών στοιχείων

Ταξινόμηση

Μπορούμε να ταξινομήσουμε όλα τα \(\mathit{counts}\) που έχουμε βρει και η απάντηση είναι τα τρία μεγαλύτερα.

#include <algorithm>

//...

// Ζευγάρια (πλήθος, τιμή).
pair<long, int> counts[MAXS];

//...

// Τακξινόμηση με βάση το πλήθος.
std::sort(counts, counts + counts_size);
fprintf(fo, "%ld %ld %ld\n", counts[counts_size - 1],
    counts[counts_size - 2], counts[counts_size - 3]);

Αυτό θέλει \(\mathcal{O}(S \log S)\), αφού υπάρχουν το πολύ \(S\) διαφορετικά στοιχεία.

Σημείωση: Υπάρχει και η συνάρτηση partial_sort'' τηςC++’’, που επιτρέπει να ταξινομήσουμε μόνο τα τρία πρώτα στοιχεία σε χρόνο \(\mathcal{O}(S)\).

Χρήση set

Βάζουμε τα \(\mathit{counts}\) σε set, και τυπώνουμε τα τρία μεγαλύτερα στοιχεία.

#include <set>

// Ζευγάρια (πλήθος, τιμή).
typedef std::pair<long, int> Candidate;

//...

// Θέλουμε το μεγαλύτερο πρώτα.
std::set<Candidate, std::greater<Candidate>> candidates;
for (int v = 1; v <= MAXS; ++v) {
  candidates.insert(std::make_pair(count[v], v));
}

//...

fprintf(fo, "%d %d %d\n", 
  candidates.begin()->second, 
  std::next(candidates.begin())->second,
  std::next(std::next(candidates.begin()))->second);

Αυτό θέλει \(\mathcal{O}(S \log S)\), αφού υπάρχουν το πολύ \(S\) διαφορετικά στοιχεία.

\(3\) μεταβλητές

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

Για παράδειγμα: Αν βρούμε ένα στοιχείο που είναι μεγαλύτερο από το πρώτο, τότε:

ανανεώνουμε το πρώτο στοιχείο
το δεύτερο στοιχείο παίρνει την τιμή του προηγούμενου πρώτου
το τρίτο στοιχείο παίρνει την τιμή του προηγούμενου δεύτερου

(Αλλά πρέπει να εκτελεστούν με ανάποδη σειρά. Δείτε τον κώδικα παρακάτω)

Ο αλγόριθμος αυτός έχει πολυπλοκότητα \(\mathcal{O}(S)\) και μνήμη \(\mathcal{O}(1)\).

Βέλτιστος συνδυασμός

Ο βέλτιστος συνδυασμός είναι η χρήση πινάκων για την καταμέτρηση και η χρήση των τριών μεταβλητών για την εύρεση των συχνότερων στοιχείων.

#include <algorithm>
#include <cstdio>

const int MAXS = 10000;
const std::pair<long, int> invalid_pair(0, -1);
long count[MAXS + 1];

int main() {
  FILE *fi = fopen("sch.in", "r");
  long N;
  fscanf(fi, "%ld", &N);
  
  for (long i = 0; i < N; ++i) {
    int value;
    fscanf(fi, "%d", &value); 
    ++count[value];
  }
  
  // Τα μεγαλύτερα τρία συν ένα στοιχείο που αγνοούμε.
  std::pair<long /* count */, int /* value */> largest_three[] = { 
    invalid_pair, invalid_pair, invalid_pair, invalid_pair
  }; 
  for (int v = 1; v <= MAXS; ++v) {
    std::pair<long, int> current = std::make_pair(count[v], v);
    int position_found = 3;
    for (int j = 0; j < 3; ++j) {
      if (largest_three[j].first < current.first) {
        position_found = j;
        break;
      }
    }
    // Μετακινούμε όλα τα στοιχεία μία θέση κάτω.
    for (int j = 2; j > position_found; --j) {
      largest_three[j] = largest_three[j - 1];
    }
    
    // Βάζουμε το τωρινό.
    largest_three[position_found] = current;
  }
  fclose(fi);
  
  FILE *fo = fopen("sch.out", "w");  
  fprintf(fo, "%d %d %d\n", 
      largest_three[0].second, 
      largest_three[1].second,
      largest_three[2].second);
  fclose(fo);
  return 0;
}

Ο αλγόριθμος έχει συνολική πολυπλοκότητα \(\mathcal{O}(S + N)\) και χρειάζεται \(\mathcal{O}(S)\) μνήμη.