Σελίδα 1 από 1

Μηνιαία Πρόκληση: Ιούλιος 2020

Δημοσιεύτηκε: Δευ Ιούλ 06, 2020 1:08 am
από Κηπουρίδης
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Ιούλιο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Το παρακάτω πρόβλημα μπορείτε να δοκιμάσετε εδώ: https://www.spoj.com/problems/PATULJCI/

Εν συντομία, σκεφτείτε ότι έχουμε τον εξής πίνακα:
1 4 4 1 1 1 2 3 3 2
Αν επικεντρωθούμε στον υποπίνακα μεταξύ των θέσεων 2-4 (4 4 1), τότε το νούμερο 4 εμφανίζεται πάνω από τις μισές φορές.
Αν επικεντρωθούμε στον υποπίνακα μεταξύ των θέσεων 6-8 (1 2 3), τότε κανένα νούμερο δεν εμφανίζεται πάνω από τις μισές φορές.

Στόχος μας είναι, δοθέντος ενός πίνακα με Ν θέσεις, να μπορούμε να απαντάμε γρήγορα σε ερωτήματα "Ποιο νούμερο (εάν υπάρχει) εμφανίζεται πάνω από μισές φορές στον υποπίνακα μεταξύ των θέσεων x-y;".

Το μέγεθος του πίνακα είναι το πολύ 300.000, οι αριθμοί που περιέχει είναι μεταξύ 1 και 100.000, και το πλήθος ερωτημάτων που πρέπει να απαντήσουμε είναι το πολύ 100.000.

Καλή επιτυχία!

Re: Μηνιαία Πρόκληση: Ιούλιος 2020

Δημοσιεύτηκε: Σάβ Ιούλ 25, 2020 10:22 pm
από Κηπουρίδης
Περίπου στις 17.00, το Σάββατο 1/8/2020, θα κάνουμε μία σύσκεψη στο zoom όπου θα συζητήσουμε σχετικά με τη μηνιαία πρόκληση Ιουλίου. Το λινκ και η ακριβής ώρα θα δοθεί σε προσεχή δημοσίευση, περίπου 2 μέρες πριν την κλήση.
Δεν πρόκειται να γίνει διάλεξη σχετικά με το πρόβλημα, αλλά ένα μοίρασμα σκέψεων. Επομένως απαιτείται όποιος συμμετέχει να έχει ανοιχτή κάμερα/μικρόφωνο.

Προς το τέλος της σύσκεψης θα συζητήσουμε και σχετικά με απορίες/προτάσεις σας σχετικά με τον ΠΔΠ. Καλό θα είναι, να γράψετε εδώ πέρα, πριν τη σύσκεψη, οποιεσδήποτε απορίες/προτάσεις έχετε, ώστε να προετοιμαστούμε όλοι κατάλληλα για τη συζήτηση.

Ξεκινώ εγώ καταθέτοντας δύο ερωτήσεις που με απασχολούν, ώστε να συζητηθούν το Σάββατο:
1) Επίλυση προβλημάτων: Σας βολεύει το Hellenico για προπόνηση για το διαγωνισμό; Ανεξάρτητα από την απάντησή σας, μπορείτε να αναφέρετε ένα-δυο πράγματα που βοηθάνε κι ένα-δυο που θα προτιμούσατε να βελτιωθούν;
2) Θεωρία: Σας είναι πάντα σαφές τι θεωρία χρειάζεται να διαβάζετε για το διαγωνισμό; Αν ναι, σας είναι σαφές και από πού θα την διαβάσετε;

Τα λέμε το Σάββατο!

Re: Μηνιαία Πρόκληση: Ιούλιος 2020

Δημοσιεύτηκε: Τετ Ιούλ 29, 2020 3:30 pm
από Κηπουρίδης
Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/69294667536?p ... pGVjdhdz09

Passcode 582649

Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.

Re: Μηνιαία Πρόκληση: Ιούλιος 2020

Δημοσιεύτηκε: Κυρ Αύγ 02, 2020 12:01 am
από switch
Μια παραλλαγή του προβλήματος με updates...
https://www.codechef.com/problems/CHEFLKJ

Re: Μηνιαία Πρόκληση: Ιούλιος 2020

Δημοσιεύτηκε: Δευ Αύγ 03, 2020 9:53 pm
από chpipis
Συζητήσαμε τις προηγούμενες μέρες με τον @Κηπουρίδη λίγο παραπάνω την παραλλαγή του προβλήματος με τα 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).