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

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευση από Κηπουρίδης »

Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Ιούλιο. Κάθε αρχή του μήνα θα ανεβαίνει στο 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.

Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευση από Κηπουρίδης »

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

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

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

Τα λέμε το Σάββατο!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευση από Κηπουρίδης »

Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/69294667536?p ... pGVjdhdz09

Passcode 582649

Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

Δημοσίευση από switch »

Μια παραλλαγή του προβλήματος με updates...
https://www.codechef.com/problems/CHEFLKJ
chpipis
Δημοσιεύσεις: 11
Εγγραφή: Σάβ Νοέμ 30, 2019 9:36 pm

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

Δημοσίευση από 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).
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

Δημοσίευση από switch »

Μια δυο ιδέες για την υλοποίηση στο πρόβλημα με τα updates συνεχίζοντας πάνω στην ανάλυση του Χάρη και του Βαγγέλη:
Σε πρώτο στάδιο (χωρίς τα updates), θα χρειαστούμε ένα segment tree που να έχει μόνο έναν ακέραιο (το dominant στοιχείο).
Το κάθε φύλλο του segment tree θα έχει την τιμή του A που φυσικά είναι dominant εφόσον είναι μόνο στοιχείο του region.

Ας σκεφτούμε αναδρομικά πως γίνονται τα combination των n regions του segment tree. Το πρώτο combine γίνεται όταν ενώνουμε δυο φύλλα του.
Αν κάνουμε combine δυο φύλλα με διαφορετικό domimant το καθένα, τότε δεν έχουμε dominant στο combined segment (προφανές, εφόσον κανένας
αριθμός δεν συναντάτε πάνω από μια φορά στο segment πλάτους δύο θέσεων).

Έστω ότι ενώσουμε 2 segments μεγέθους k το καθένα, όπου κανένα segment δεν έχει dominant. Τότε σύμφωνα με την παρατήρηση του Δ. Μπαλάτου,
όλοι οι αριθμοί που βρίσκονται στα συνδυαζόμενα regions, έχουν εξουδετερωθεί μεταξύ τους και δεν μπορούν να παράγουν μια συγκέντρωση
μεγαλύτερη του k.
Αν όμως ένα μόνο από τα regions είχε dominant, τότε το combined region ενδέχεται να έχει dominant αυτό (είναι υποψήφιο) και μόνο αυτό το νούμερο.
Για την τελική επιβεβαίωση αν πράγματι το υποψήφιο είναι dominant του region, θέλουμε κάποια άλλη (δεύτερη) δομή να μας επιβεβαιώσει πόσα
τέτοια νούμερα έχει το combined region (σε γραμμική ή λογαριθμική πολυπλοκότητα ανά query).
Αν στο combining έχουμε δύο υποψήφια dominant, πάλι ανατρέχουμε στη δεύτερη δομή μας για να μετρήσουμε ποιός από τους υποψήφιους νικά.

Μια λύση για τη δομή αυτή είναι φυσικά ένας πίνακας από vectors που σε κάθε θέση x του πίνακα, θα έχουμε ένα vector με τις θέσεις που συναντάτε
ο αριθμός x (οπότε με lower_bound,upper_bound θα μπορούμε να τα μετρήσουμε σε λογαριθμικό χρόνο).
Η λύση αυτή είναι άριστη όταν δεν έχουμε updates. Όταν έχουμε updates, είναι χρονοβόρο να τροποποιούμε το κάθε vector (θέλει γραμμικό χρόνο),
παρόλα αυτά, λόγω των χαλαρών test cases του προβλήματος, η λύση με τα vector updates, γίνεται accepted με χρόνο 0.54δευτ.

Μια ακόμα λύση θα ήταν να έχουμε ένα segment tree ανά αριθμό x, ώστε να βρίσκουμε τα sum queries του κάθε region. Αυτό όμως απαιτεί υπερβολικά πολλή μνήμη, σχεδόν 4*N^2.
Μπορούμε να ακολουθήσουμε τη συμπίεση που αναφέρεται εδώ: https://kallinikos.github.io/Segment-Trees#συμπίεση ή
μπορούμε όμως να κάνουμε implicit segment tree https://cp-algorithms.com/data_structur ... toc-tgt-13, ώστε να χρειαζόμαστε επέκταση των κλαδιών μόνο προς τα υπαρκτά φύλλα. Η λύση αυτή περνά με 0,61δευτ.

Άλλη λύση είναι η χρήση ενός balanced binary search tree (σαν τα set/map) ή treap που να μπορεί να μας δώσει τη θέση κάθε στοιχείου στο δέντρο,
οπότε κάνοντας αναζήτηση με τα όρια του region να βρίσκουμε τον αριθμό των στοιχείων στο range.
Δυστυχώς τα set/map κρατάνε κρυφά αυτά τα στοιχεία και δεν μπορούμε να τα χρησιμοποιήσουμε. Θα πρέπει να γράψουμε δικό μας κώδικα, οπότε μια treap είναι καλή επιλογή.

Μια μη αποδοτική λύση για τη δεύτερη δομή μας με vector updates που περνά λόγω των χαλαρών test cases:
Spoiler: show

Κώδικας: Επιλογή όλων

struct positions {//keep a vector of numbers sorted with inserton/deletion methods
	vector<int> pos;//always sorted
	void remove(int apos){//αφαίρεσε μια θέση (ο αριθμός στη θέση αυτή άλλαξε - αφαίρεσε τον παλιό αριθμό)
		auto itr = lower_bound(pos.begin(),pos.end(),apos);
		assert(itr!=pos.end() && *itr==apos);
		pos.erase(itr);
	}
	void insert(int apos){//πρόσθεσε μια θέση στον καινούργιο αριθμό
		auto itr = lower_bound(pos.begin(), pos.end(), apos+1);
		pos.insert(itr,apos);
	}
	int count(int left,int right){
		auto itr1 = lower_bound(pos.begin(), pos.end(), left);
		auto itr2 = upper_bound(pos.begin(), pos.end(), right);
		return itr2-itr1;
	}
};
map<int,_positions> Pos;
Μια λύση με implicit segment tree για τα range sum queries:
Spoiler: show

Κώδικας: Επιλογή όλων

class snode {//range sum implicit segment tree node
	int left,right; //range limits
	int sum;
	snode *leftptr, *rightptr;

	void expand(){
		if(!leftptr && left<right){
			int mid = (left + right)/2;
			leftptr = new snode(left,mid);
			rightptr= new snode(mid+1,right);
		}
	}
public:
	snode(int le=1,int ri=-1){
		leftptr = rightptr = NULL;
		sum = 0, left = le, right = (ri==-1) ? N : ri;
	}
	int querysum(int qleft,int qright){
		if(qright<left || right<qleft)//not included
			return 0;
		if(qleft<=left && right<=qright)//fully included
			return sum;
		//partialy included
		if(!leftptr)//not expanded, not affecting sum
			return 0;
		return leftptr->querysum(qleft,qright) + rightptr->querysum(qleft,qright);
	}
	void updatesum(int pos,int value){
		if(left==right){
			assert(pos == left);
			sum = value;
		} else {
			expand();
			if(pos<=leftptr->right)
				leftptr->updatesum(pos,value);
			else
				rightptr->updatesum(pos,value);
			sum = leftptr->sum + rightptr->sum;
		}
	}
};

map<int,snode> Sum;
	//assigns the implicit segment tree root node to every unique number Ai
ή

Κώδικας: Επιλογή όλων

class snode {//range sum implicit segment tree node
	int sum;
	snode *leftptr, *rightptr;

	void expand(int left,int right){
		if(!leftptr && left<right){
			leftptr = new snode();
			rightptr= new snode();
		}
	}
public:
	snode(){
		leftptr = rightptr = NULL; sum = 0;
	}
	int querysum(int left,int right,int qleft,int qright){
		if(qright<left || right<qleft)//not included
			return 0;
		if(qleft<=left && right<=qright)//fully included
			return sum;
		//partialy included
		if(!leftptr)//not expanded, not affecting sum
			return 0;
		int mid = (left+right)/2;
		return leftptr->querysum(left,mid,qleft,qright) + rightptr->querysum(mid+1,right,qleft,qright);
	}
	void updatesum(int left,int right,int pos,int value){
		if(left==right){
			assert(pos == left);
			sum = value;
		} else {
			expand(left,right);
			int mid = (left+right)/2;
			if(pos<=mid)
				leftptr->updatesum(left,mid,pos,value);
			else
				rightptr->updatesum(mid+1,right,pos,value);
			sum = leftptr->sum + rightptr->sum;
		}
	}
};

map<int,snode> S;//<number,root of implicit segment tree>
	//assigns the implicit segment tree root node to every unique number Ai

Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

Δημοσίευση από switch »

Ενδεικτικές λύσεις στο αντίστοιχο πρόβλημα που περιέχει updates https://www.codechef.com/problems/CHEFLKJ με:
Απάντηση