Συζητήσαμε τις προηγούμενες μέρες με τον @Κηπουρίδη λίγο παραπάνω την παραλλαγή του προβλήματος με τα updates (όπως ακριβώς στο πρόβλημα του codechef που πόσταρε ο @switch). Προσπαθήσαμε να σκεφτούμε αν υπάρχει αλγόριθμος με χρόνο O((N + Q) log N) -- όπου Q το πλήθος ερωτημάτων -- που να λύνει αυτή την παραλλαγή του προβλήματος (σε συνέχεια και της συζήτησης που έγινε στο τέλος της σύσκεψης zoom του Σαββάτου).
Τελικά καταλάβαμε ότι η λύση που πρότεινε ο Δ. Μπαλάτος το Σάββατο ήταν σωστή και λύνει την παραλλαγή του προβλήματος με τα updates σε O((N + Q) log N) χρόνο! Την περιγράφω εδώ για όποιον ενδιαφέρεται.
Η λύση στηρίζεται σε μια ωραία παρατήρηση. Ας ξεχάσουμε για λίγο τα queries και ας πούμε ότι μας δίνεται ένας πίνακας, στον οποίο θέλουμε να ελέγξουμε αν υπάρχει στοιχείο που εμφανίζεται περισσότερες από τις μισές φορές (αυτά θα τα λέμε
dominant στοιχεία). Ένας τρόπος να το βρούμε αυτό είναι να βάλουμε τα στοιχεία να "παλέψουν" μεταξύ τους και να δούμε ποιο νικάει στο τέλος. Συγκεκριμένα, μπορούμε να εκτελούμε συνεχώς την εξής διαδικασία: επιλέγουμε δύο διαδοχικά στοιχεία του πίνακα με διαφορετική τιμή και τα αφαιρούμε από αυτόν (μειώνοντας το μήκος του κατά 2). Η διαδικασία σταματάει όταν όλα τα στοιχεία που παραμένουν έχουν την ίδια τιμή, που είναι και η νικήτρια. Για παράδειγμα, έστω ότι έχουμε έχουμε τον ακόλουθο πίνακα:
1 1 1 2 3
Αν εκτελέσουμε αυτή την διαδικασία (ή αλγόριθμο) και βάλουμε σε παρένθεση τα στοιχεία που διαγράφονται σε κάθε βήμα παίρνουμε:
1 1 (1 2) 3 -> 1 (1 3) -> 1
Οπότε, το 1 νικάει και μπορούμε να επιβεβαιώσουμε ότι είναι και το dominant στοιχείο. Ο άλλος τρόπος να εκτελέσουμε τον αλγόριθμο είναι να διαγράψουμε τα στοιχεία 2, 3 οπότε στο τέλος να μείνουμε με:
1 1 1
Πάλι νικητής είναι το dominant στοιχείο!
Δεν είναι δύσκολο να δούμε ότι αυτό θα ισχύει πάντα. Δηλαδή (με την προϋπόθεση ότι υπάρχει), το dominant στοιχείο θα νικάει πάντα σε αυτή την διαδικασία. Η μόνη περίπτωση να χάσει θα ήταν αν το πλήθος των άλλων στοιχείων ήταν μεγαλύτερο από το πλήθος εμφανίσεων του dominant. Όμως εξ' ορισμού, το dominant στοιχείο εμφανίζεται μέσα στον πίνακα περισσότερες από τις μισές φορές και, συνεπώς περισσότερες φορές από όλα τα υπόλοιπα στοιχεία μαζί. Συμπεραίνουμε λοιπόν ότι
νικήτης σε αυτή την διαδικασία θα είναι πάντα το dominant στοιχείο.
Τι γίνεται στην περίπτωση που δεν υπάρχει dominant στοιχείο; Τότε, στο τέλος της διαδικασίας μπορεί να μείνει οποιοδήποτε στοιχείο. Για να σιγουρευτούμε λοιπόν ότι το στοιχείο που μας δίνεται είναι και dominant θα πρέπει να ελέγξουμε αν εμφανίζεται περισσότερες από τις μισές φορές.
Ας επανέλθουμε τώρα στο πρόβλημα με τα ερωτήματα (αλλά ακόμα όχι updates). Η ιδέα γενικεύεται εύκολα αν χρησιμοποιήσουμε ένα
Segment Tree. Αυτό που θα κρατάμε σε κάθε κόμβο του Segment Tree είναι το ζεύγος
(value
, count
) =
(τιμή
, υπολειπόμενες εμφανίσεις
) του στοιχείου που μένει στο τέλος αν εφαρμόσουμε με κάποιον τρόπο την διαδικασία στο διάστημα που αντιστοιχεί στον κόμβο. Για να κάνουμε merge δύο διαδοχικούς κόμβους left, right έχουμε:
Κώδικας: Επιλογή όλων
node merge(node left, node right) {
node result;
if (left.value == right.value) { // ειδική περίπτωση
result.value = left.value;
result.count = left.count + right.count;
} else if (left.count > right.count) {
result.value = left.value;
result.count = left.count - right.count;
} else {
result.value = right.value;
result.count = right.count - left.count;
}
return result;
}
Ουσιαστικά χωρίζουμε την εκτέλεση της διαδικασίας σε δύο φάσεις. Στην πρώτη φάση αφήνουμε όλα τα στοιχεία του αριστερού διαστήματος να παλέψουν μέχρι να βγει ένας νικητής (που θα έχει τιμή
left.value και θα έχουν μείνει
left.count αντίγραφα από αυτόν) και, αντίστοιχα, όλα τα στοιχεία του δεξιού διαστήματος (με
right.value και
right.count). Στην δεύτερη φάση παλεύουν τα
left.value και
right.value μεταξύ τους για να βγάλουν τον τελικό νικητή, που είναι το στοιχείο με τις περισσότερες εμφανίσεις (αν είναι ισάριθμα, τότε επιλέγουμε αυθαίρετα το δεξιό στοιχείο, δεν έχει σημασία).
Τελικά, βλέπουμε ότι το segment tree μας επιστρέφει ως αποτέλεσμα για ένα δοσμένο διάστημα το στοιχείο που μένει στο τέλος της διαδικασίας αν επικεντρωθούμε σε αυτό το διάστημα. Αυτό το στοιχείο θα είναι το μοναδικό υποψήφιο dominant στοιχείο που έχουμε για αυτό το διάστημα και αρκεί (όπως και πριν) να επαληθεύσουμε ότι εμφανίζεται περισσότερες από τις μισές φορές. Αν υπάρχει dominant στοιχείο τότε σίγουρα θα επιστραφεί από το segment tree οπότε θα το βρούμε και, αν δεν υπάρχει, θα το καταλάβουμε γιατί δεν θα εμφανίζεται αρκετές φορές στο διάστημα.
Η επαλήθευση μπορεί να γίνει εύκολα και στην περίπτωση των ερωτημάτων αν κρατάμε για κάθε διαφορετική τιμή ένα vector με τις θέσεις του πίνακα που έχουν αυτή την τιμή. Για να δούμε οπότε πόσες φορές εμφανίζεται μια τιμή σε ένα δοσμένο διάστημα μπορούμε να κάνουμε δύο binary search, μια για το πρώτο και μια για το τελευταίο στοιχείο του vector που περιέχονται σε αυτό.
Για την γενική μορφή του προβλήματος με τα updates μπορούμε να υλοποιήσουμε απλά point updates στο Segment Tree που αναβαθμίζουν ένα μονοπάτι από ένα φύλλο προς την ρίζα. Επίσης μπορούμε να αντικαταστήσουμε τα vector στην τελευταία δομή δεδομένων με
Τreap (ή κάτι άλλο που να υποστηρίζει insertions/deletions και binary search).
Η χρονική πολυπλοκότητα του κάθε query και update για το segment tree θα είναι O(log N) και η πολυπλοκότητα για την δομή δεδομένων επαλήθευσης θα είναι επίσης O(log N). Τελικά, λύνουμε το πρόβλημα σε χρόνο O((N + Q) log N).