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

38ος ΠΔΠ Α' Φάση: Κήπος με μπαμπού (bamboo) - Λύση

Συγγραφέας: Γιώργος Βενιζέλος

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

Παρατηρούμε ότι κάθε μέρα ο Τάκης κόβει όλα τα μπαμπού με ένα συγκεκριμένο ύψος, το μέγιστο εκείνης της ημέρας. Άρα έχουμε,

  • Την πρώτη μέρα κόβει τα μπαμπού με το μεγαλύτερο ύψος.
  • Τη δεύτερη μέρα κόβει τα μπαμπού με το δεύτερο μεγαλύτερο ύψος.
  • Και ούτω καθεξής…

Άρα, το πλήθος των ημερών που θα χρειαστεί ο Τάκης είναι ίσος με το πλήθος των διαφορετικών υψών.

Στο παράδειγμα: \([1, 7, 3, 7, 3]\) τα διαφορετικά ύψη είναι \(\{1, 3, 7\} \rightarrow 3\) ημέρες.

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

Λύση για το 1ο υποπρόβλημα

Σε αυτή την περίπτωση έχουμε μόνο \(2\) μπαμπού, οπότε υπάρχουν δύο περιπτώσεις:

  1. Τα μπαμπού είναι ίσα, άρα τα κόβουμε σε \(1\) μέρα, ή
  2. Τα μπαμπού είναι διαφορετικά, οπότε την πρώτη μέρα κόβουμε το ένα και την δεύτερη το άλλο, και χρειαζόμαστε συνολικά \(2\) μέρες.
  // Αν είναι ίσα τα μήκη, χρειαζόμαστε 1 μέρα, αλλιώς 2 μέρες
  if (lengths[0] == lengths[1]) {
    printf("1\n");
  } else {
    printf("2\n");
  }

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

Τελικές Λύσεις

Για την πλήρη λύση του προβλήματος έχουμε δύο εναλλακτικές:

  1. Να χρησιμοποιήσουμε μια δομή δεδομένων που να κρατάει μοναδικές τιμές (π.χ. set ή unordered_set)
  2. Να ταξινομήσουμε τα ύψη και να μετρήσουμε πόσα διαφορετικά γειτονικά στοιχεία υπάρχουν.

1. Λύση με set

Οι δομές set και unordered_set κρατάνε τις μοναδικές τιμές από τις τιμές που μπαίνουν σε αυτές. Η εισαγωγή τιμών σε αυτές γίνεται σε χρόνο \(\mathcal{O}(\log N)\) και \(\mathcal{O}(1)\) αντίστοιχα. Αφού έχουμε \(N\) ύψη, οι συνολικοί χρόνοι είναι \(\mathcal{O}(N \log N)\) και \(\mathcal{O}(N)\) αντίστοιχα. Και οι δύο είναι αρκετοί για να περάσουν όλα τα tests. Η τελική λύση είναι το μέγεθος της δομής αυτής μετά την εισαγωγή όλων των υψών.

unordered_set<long> unique_lengths;

  scanf("%ld", &N);
  long len;
  for (long i = 0; i < N; i++) {
    scanf("%ld", &len);
    unique_lengths.insert(len);
  }

  printf("%zu\n", unique_lengths.size());

Δείτε ολόκληρο τον κώδικα εδώ

Σημείωση: Μια άλλη δομή δεδομένων της STL που μπορούμε να χρησιμοποιήσουμε είναι η priority_queue. Αυτή η δομή επιστρέφει το μεγαλύτερο στοιχείο, από αυτά που της έχουμε εισάγει. Βάζοντας όλα τα στοιχεία, και μετά εξάγοντάς τα ένα-ένα, αυξάνουμε τον αριθμό των ημερών κάθε φορά που δυο διαδοχικές εξαγωγές έχουν διαφορετικά μήκη. Η εισαγωγή και εξαγωγή στοιχείων έχουν πολυπλοκότητα \(\mathcal{O}(\log N)\), οπότε ησυνολική πολυπλοκότητα είναι \(\mathcal{O}(N \log N)\). Δείτε τον κώδικα εδώ

2. Λύση με ταξινόμηση

Αν πάρουμε τις τιμές του παραδείγματος \([1, 7, 3, 7, 3]\) και τις ταξινομήσουμε έχουμε \([1, 3, 3, 7, 7]\). Παρατηρούμε ότι με την ταξινόμηση οι ίδιες τιμές ομαδοποιούνται σε διαδοχικές θέσεις. Κάθε διαφορετικό ύψος αποτελεί και μία τέτοια ομάδα, οπότε πρέπει να μετρήσουμε το πλήθος αυτών των ομάδων. Ένα νέο ύψος ξεκινάει στην αρχή του πίνακα (μικρότερο ύψος) και κάθε φορά που δύο διαδοχικά ύψη είναι διαφορετικά (δηλαδή στο παράδειγμα μας στην 1η και 2η θέση του πίνακα (\([1, 3]\)) και στην 3η και 4η θέση (\([3, 7]\))).

Η πολυπλοκότητα της λύσης είναι \(\mathcal{O}(N\log N)\) για την ταξινόμηση και \(\mathcal{O}(N)\) για την καταμέτρηση άρα συνολικά \(\mathcal{O}(N\log N)\).

  // Ταξινομούμε τα μήκη για να μετρήσουμε τα μοναδικά μήκη
  sort(lengths, lengths + N);

  long last_length = -1;
  long unique_count = 0;
  for (long i = 0; i < N; i++) {
    // Αν το μήκος είναι διαφορετικό από το προηγούμενο, αυξάνουμε τον μετρητή
    // μοναδικών μηκών και ενημερώνουμε το τελευταίο μήκος
    if (lengths[i] != last_length) {
      unique_count++;
      last_length = lengths[i];
    }
  }

Δείτε ολόκληρο τον κώδικα εδώ

Σημείωση: Για αυτή τη λύση μπορούν να χρησιμοποιηθούν και οι έτοιμες συναρτήσεις της STL.

  sort(lengths.begin(), lengths.end());
  lengths.erase(unique(lengths.begin(), lengths.end()), lengths.end());
  printf("%zu\n", lengths.size());

Δείτε ολόκληρο τον κώδικα εδώ

Υπόλοιπα υποπροβλήματα

Λύση για το 2ο υποπρόβλημα

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

Δείτε ολόκληρο τον κώδικα εδώ

Λύση για το 3ο υποπρόβλημα

Επειδή στο 3ο υποπρόβλημα το \(N \leq 5.000\), μπορούμε να προσομοιώσουμε την διαδικασία κοψίματος:

  1. Κάθε μέρα βρίσκουμε το κάποιο ύψος που δεν έχει ήδη κοπεί
  2. Κόβουμε όλα τα μπαμπού με αυτό το ύψος (κάνουμε το ύψος τους \(0\))
  3. Αν δεν έχουν κοπεί όλα τα μπαμπού, ξαναπάμε στο βήμα 1 και στην επόμενη μέρα

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

  // Το μήκος του μπαμπού που κόβουμε την τρέχουσα μέρα
  long current_bamboo_length = 0;
  // Συνολικές μέρες που χρειάστηκαν
  long total_days = 0;
  while (true) {
    current_bamboo_length = 0;
    // Βρίσκουμε κάποιο μήκος μπαμπού που δεν έχει κοπεί ακόμα και κόβουμε
    // όλα τα μπαμπού με αυτό το μήκος.
    for (long i = 0; i < N; i++) {
      if (lengths[i] == 0)
        continue;
      if (current_bamboo_length == 0)
        current_bamboo_length = lengths[i];
      if (current_bamboo_length == lengths[i])
        lengths[i] = 0;
    }

    // Αν current_bamboo_length = 0, τότε έχουν κοπεί όλα τα bamboo και
    // σταματάμε
    if (current_bamboo_length > 0)
      total_days++;
    else
      break;
  }

  printf("%ld\n", total_days);

Δείτε ολόκληρο τον κώδικα εδώ

Λύση για το 4ο υποπρόβλημα

Στο 4ο υποπρόβλημα, τα μπαμπού μπορεί να είναι πολλά, αλλά έχουν σχετικά μικρά ύψη (\(1 \leq h_i \leq 10^5\)). Μπορούμε να δημιουργήσουμε ένα πίνακα έως το \(10^5\), που να κρατάει αν έχουμε συναντήσει το κάθε ύψος. Έπειτα για να βρούμε πόσα μοναδικά ύψη υπάρχουν, αρκεί να μετρήσουμε πόσα στοιχεία αυτού του πίνακα είναι \(\texttt{true}\) (βλέπε Counting Sort).

bitset<MAXH + 1> lengths_found;

  scanf("%ld", &N);
  long len;
  for (long i = 0; i < N; i++) {
    // Διαβάζουμε το μήκος κάθε μπαμπού και σημειώνουμε ότι το βρήκαμε
    scanf("%ld", &len);
    lengths_found[len] = true;
  }

  printf("%zu\n", lengths_found.count());

Δείτε ολόκληρο τον κώδικα εδώ