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

38ος ΠΔΠ Α' Φάση: Οι φούρνοι του Τάκη (ovens) - Λύση

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

Μας δίνονται \(N\) φούρνοι με την αρχική τους κατάσταση (αναμμένος ή σβηστός) και \(N\) διακόπτες ένας για κάθε φούρνο \(i\) ο οποίος όταν πατηθεί αλλάζει την κατάσταση των φούρνων από τον \(i\)-οστό έως και τον \(i + k_i\).

Λύση από τα αριστερά προς τα δεξιά (32%)

Παρατήρηση 0: Αν αναβοσβήσουμε έναν φούρνο ζυγό αριθμό φορών τότε η κατάστασή του είναι η ίδια με την αρχική. Αν τον αναβοσβήσουμε μονό, τότε είναι η αντίθετη.

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

Παρατήρηση 2η: Έχοντας αποφασίσει ποιους από τους πρώτους \(i-1\) διακόπτες θα πατήσουμε, πρέπει να πατήσουμε τον διακόπτη \(i\) αν και μόνο αν ο \(i\)-οστός φούρνος είναι αναμμένος εκείνη την στιγμή. (Διαφορετικά, δεν θα έχουμε άλλη ευκαιρία να τον σβήσουμε)

Χρησιμοποιώντας αυτή την παρατήρηση, ξεκινάμε με τον πρώτο διακόπτη και αν ο φούρνος είναι αναμμένος, τότε πρέπει να τον σβήσουμε. Παρόμοια συνεχίζουμε για τους φούρνους \(2, 3, \ldots\). Καθώς σβήνουμε τον \(i\)-οστό φούρνο, ανανεώνουμε και την κατάσταση των φούρνων στις θέσεις \(i + 1\) έως και \(i + k_i\). Για κάθε ανανέωση πρέπει να αλλάξουμε την κατάσταση \(k_i+1\) φούρνων. Επομένως, ο αλγόριθμος αυτός χρειάζεται \(O(\sum_{i=1}^n (k_i+1))\) χρόνο που στην χειρότερη περίπτωση μπορεί να είναι \(\Omega(n^2)\).

Αυτό είναι αρκετό για να περάσει περίπου το 32% των βαθμών (τα υποπροβλήματα 1 και 3).

#include <cstdio>

const size_t MAXN = 200'000;

bool a[MAXN];
long k[MAXN];

int main(){
  long N;
  scanf("%ld", &N);
   
  for(long i = 0; i < N; ++i) {
    int temp;
    scanf("%d", &temp);
    a[i] = temp;
  }
  for(long i = 0; i < N; ++i) {
    scanf("%ld", &k[i]);
  }
   
  long num_switch = 0; // Το πλήθος των διακοπτών που πατήσαμε.
  for (long i = 0; i < N; ++i) {
    if (a[i]) {
      a[i] = 0;
      ++num_switch;
      // Αλλάζουμε την κατάσταση των επόμενων k[i] διακοπτών.
      for (int j = i + 1; j <= i + k[i]; ++j) {
        a[j] = !a[j];
      }
    }
  }

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

Σημείωση: Με μερικές μικρές τροποποιήσεις, η λύση μπορεί να περάσει και τα υποπροβλήματα 2 και 4 (δείτε παρακάτω).

Βέλτιστη λύση (100%)

Σε αυτή την λύση θα προσπαθήσουμε να κάνουμε την ανανέωση των \(k_i\) φούρνων πιο αποδοτικά.

Κρατώντας σε κάθε στιγμή το πλήθος active_switch_mod_2 των διακοπτών στα αριστερά που επηρεάζουν τον \(i\)-οστό φούρνο, ξέρουμε την κατάστασή του (a[i] αν active_switch_mod_2 είναι ζυγός ή !a[i] αν είναι μονός). Κρατάμε επίσης switch_ending[j] το πλήθος των διακοπτών που τελειώνουν στην θέση j. Από την Παρατήρηση 0, και για τις δύο μεταβλητές μπορούμε να κρατήσουμε μόνο το υπόλοιπό τους με τον αριθμό 2.

Στο \(i\)-οστό βήμα:

  • η κατάσταση ενός φούρνου είναι \(a_i \oplus \texttt{active\_switch\_mod\_2}\) (όπου \(\oplus\) είναι η αποκλειστική διάζευξη (xor)),
  • αν ο φούρνος ήταν αναμμένος, τότε
    • αυξάνουμε το πλήθος των τωρινών πατημένων διακοπτών, active_switch_mod_2 = !active_switch_mod_2 και
    • ενημερώνουμε ότι ένας ακόμα διακόπτης τελειώνει στο βήμα j = i + k[i], δηλαδή switch_ending[j] = !switch_ending[j], και επίσης
  • στο τέλος κάθε βήματος \(\texttt{active\_switch\_mod\_2} = \texttt{active\_switch\_mod\_2} \oplus \texttt{switch\_ending}[\texttt{i}]\).

Άρα κάθε ανανέωση γίνεται σε \(O(1)\) χρόνο και επομένως η λύση αυτή χρειάζεται \(O(N)\) χρόνο συνολικά, και περνάει όλα τα testcases.

#include <cstdio>

const size_t MAXN = 200'000;

bool a[MAXN];
long k[MAXN];

// switch_ending[i] = Το πλήθος των διακοπτών (mod 2) 
//      που τελειώνει στην θέση i. 
bool switch_ending[MAXN];

int main(){
  long N;
  scanf("%ld", &N);
   
  for(long i = 0; i < N; ++i) {
    int temp;
    scanf("%d", &temp);
    a[i] = temp;
  }
  for(long i = 0; i < N; ++i) {
    scanf("%ld", &k[i]);
  }
   
  long num_switch = 0; // Το πλήθος των διακοπτών που πατήσαμε.
  bool active_switch_mod_2 = 0; // Το πλήθος των ενεργών διακοπτών mod 2.
  for (long i = 0; i < N; ++i) {
    bool is_current_oven_on = a[i] ^ active_switch_mod_2;
    if (is_current_oven_on) { 
      // Πατάμε τον i-οστό διακόπτη.
      ++num_switch;
      // Δηλώνουμε ότι υπάρχει ένας διακόπτης που επηρεάζει τους φούρνους
      // (από το i) έως το i + k[i].
      switch_ending[i + k[i]] = !switch_ending[i + k[i]];
      // Το πλήθος των ενεργών διακοπτών αλλάζει κατά ένα
      // (άρα το υπόλοιπο με το δύο αντιστρέφεται).
      active_switch_mod_2 = !active_switch_mod_2;
    }
    // Αν υπάρχει μονό πλήθος διακοπτών που τελειώνει στο i, 
    // τότε αλλάζουμε το υπόλοιπο των ενεργών διακοπτών.
    if (switch_ending[i]) {
      active_switch_mod_2 = !active_switch_mod_2;
    }
  }

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

Λύσεις για συγκεκριμένα υποπροβλήματα

Τα υποπροβλήματα μπορούν να λυθούν ως εξής:

  • Υποπρόβλημα 1 \(k_i = 0\): Κάθε διακόπτης επηρεάζει μόνο τον αντίστοιχο φούρνο, επομένως πρέπει να σβήσουμε τόσους διακόπτες όσοι είναι και οι αναμμένοι φούρνοι (κώδικας).
  • Υποπρόβλημα 2 \(a_i = 1\): Επεκτείνουμε την πρώτη λύση ως εξής: Όταν είμαστε στον \(i\)-οστό φούρνο μπορούμε απλά να προσπεράσουμε τους επόμενους \(k[i]\) καθώς θα σβήσουν όταν πατήσουμε τον διακόπτη του \(i\)-οστού (κώδικας).
  • Υποπρόβλημα 3 \(k_i \leq 10\): Μπορούμε να εφαρμόσουμε αυτούσια την πρώτη λύση.
  • Υποπρόβλημα 4 \(k_i = N - i\): Επεκτείνουμε την πρώτη λύση ως εξής: Κρατάμε μόνο το πλήθος των ενεργών διακοπτών mod 2 (δηλαδή το active_switch_mod_2 της βέλτιστης λύσης), καθώς ξέρουμε ότι όλοι λήγουν στο τέλος (κώδικας).