Μηνιαία Πρόκληση: Οκτώβριος 2020
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Μηνιαία Πρόκληση: Οκτώβριος 2020
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Οκτώβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας δισδιάστατος πίνακας, που σε κάθε κελί του περιέχει είτε τον χαρακτήρα Χ (χωράφι), είτε τον χαρακτήρα Τ (τσιμέντο). Ο στόχος είναι να βρούμε τον μέγιστου εμβαδού (συνεχόμενο) υποπίνακα που όλα του τα κελιά είναι Χ.
Για παράδειγμα αν δοθεί ο πίνακας
\\ 1 2 3 4 5 6
1 Τ Τ Τ Τ Τ Τ
2 Τ Τ Τ Χ Τ Τ
3 Τ Τ Χ Χ Χ Τ
4 Τ Χ Χ Χ Χ Χ
5 Τ Τ Χ Χ Χ Τ
6 Τ Τ Τ Χ Τ Τ
τότε το μέγιστο χωράφι που μπορούμε να εντοπίσουμε έχει εμβαδό 9. Πρόκειται για το χωράφι από x=3 ως x=5, κι από y=3 ως y=5.
Προσέξτε ότι ο ρόμβος με κέντρο το (4,4) και ακτίνα 2 περιλαμβάνει όλα τα Χ (και κανένα Τ). Παρότι έχει μεγαλύτερο εμβαδό (13) δε μας ενδιαφέρει γιατί οι πλευρές του δεν είναι παράλληλες με τους άξονες, όπως με το προαναφερθέν χωράφι εμβαδού 9.
Αν ο πίνακας έχει μέγεθος Ν*Ν, τότε μας ενδιαφέρουν οι πολυπλοκότητες Ο(Ν^6), Ο(Ν^5), Ο(Ν^4), Ο(Ν^3), Ο(Ν^2). Προτείνω να σκεφτείτε το πρόβλημα 10 λεπτά και να δείτε ποια από τις παραπάνω λύσεις μπορείτε να βρείτε. Μετά, για τον υπόλοιπο μήνα, να προσπαθήσετε να βρείτε την αμέσως καλύτερη από την πρώτη που σκεφτήκατε.
Σημειώνω ότι ο Ο(Ν^2) είναι βέλτιστος, αφού τόσο είναι το μέγεθος του πίνακα!
Στις 20 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου όμως αν το ξεχάσω.
Καλή επιτυχία!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας δισδιάστατος πίνακας, που σε κάθε κελί του περιέχει είτε τον χαρακτήρα Χ (χωράφι), είτε τον χαρακτήρα Τ (τσιμέντο). Ο στόχος είναι να βρούμε τον μέγιστου εμβαδού (συνεχόμενο) υποπίνακα που όλα του τα κελιά είναι Χ.
Για παράδειγμα αν δοθεί ο πίνακας
\\ 1 2 3 4 5 6
1 Τ Τ Τ Τ Τ Τ
2 Τ Τ Τ Χ Τ Τ
3 Τ Τ Χ Χ Χ Τ
4 Τ Χ Χ Χ Χ Χ
5 Τ Τ Χ Χ Χ Τ
6 Τ Τ Τ Χ Τ Τ
τότε το μέγιστο χωράφι που μπορούμε να εντοπίσουμε έχει εμβαδό 9. Πρόκειται για το χωράφι από x=3 ως x=5, κι από y=3 ως y=5.
Προσέξτε ότι ο ρόμβος με κέντρο το (4,4) και ακτίνα 2 περιλαμβάνει όλα τα Χ (και κανένα Τ). Παρότι έχει μεγαλύτερο εμβαδό (13) δε μας ενδιαφέρει γιατί οι πλευρές του δεν είναι παράλληλες με τους άξονες, όπως με το προαναφερθέν χωράφι εμβαδού 9.
Αν ο πίνακας έχει μέγεθος Ν*Ν, τότε μας ενδιαφέρουν οι πολυπλοκότητες Ο(Ν^6), Ο(Ν^5), Ο(Ν^4), Ο(Ν^3), Ο(Ν^2). Προτείνω να σκεφτείτε το πρόβλημα 10 λεπτά και να δείτε ποια από τις παραπάνω λύσεις μπορείτε να βρείτε. Μετά, για τον υπόλοιπο μήνα, να προσπαθήσετε να βρείτε την αμέσως καλύτερη από την πρώτη που σκεφτήκατε.
Σημειώνω ότι ο Ο(Ν^2) είναι βέλτιστος, αφού τόσο είναι το μέγεθος του πίνακα!
Στις 20 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου όμως αν το ξεχάσω.
Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Καλημέρα! Υπάρχει κατώτατο όριο στο τί θεωρείται χωράφι; Θα μπορούσε να είναι χωράφι μόνο μια ευθεία γραμμη από Χ ; ( διαφορετικά οι ελάχιστες διαστάσεις του χωραφιού θα πρέπει να είναι 2*2...)
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Πιθανώς δεν κατάλαβα καλά την ερώτηση, οπότε ξαναρώτα αν δε σε καλύψω.
Το κάθε Χ είναι ένα χωραφάκι ενός στρέμματος. Μία ευθεία γραμμή από Χ (με μήκος πχ 5) θα ήταν ένα μεγάλο χωράφι εμβαδού 5 στρεμμάτων, που είναι πράγματι έγκυρο. Ακόμα και ένα Χ μόνο του είναι έγκυρο χωράφι.
Στο παραπάνω παράδειγμα, υπάρχουν δύο ευθύγραμμα τμήματα, μήκους 5 το καθένα. Θα ήταν έγκυρα, απλώς έτυχε να βρούμε ένα ορθογώνιο που περιλαμβάνει περισσότερα Χ (9), οπότε προτιμήσαμε εκείνο.
Το κάθε Χ είναι ένα χωραφάκι ενός στρέμματος. Μία ευθεία γραμμή από Χ (με μήκος πχ 5) θα ήταν ένα μεγάλο χωράφι εμβαδού 5 στρεμμάτων, που είναι πράγματι έγκυρο. Ακόμα και ένα Χ μόνο του είναι έγκυρο χωράφι.
Στο παραπάνω παράδειγμα, υπάρχουν δύο ευθύγραμμα τμήματα, μήκους 5 το καθένα. Θα ήταν έγκυρα, απλώς έτυχε να βρούμε ένα ορθογώνιο που περιλαμβάνει περισσότερα Χ (9), οπότε προτιμήσαμε εκείνο.
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Καλησπέρα σε όλους!!!
Βαγγέλη, το hint???![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Ευχαριστώ!!!
Βαγγέλη, το hint???
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Ευχαριστώ!!!
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Ωπ, ευχαριστώ για την υπενθύμιση!
Ο(Ν^6): Δε σχολιάζω τίποτα.
Ο(Ν^5): Αν θέλουμε να ελέγξουμε αν συγκεκριμένο ορθογώνιο έχει μόνο χωράφια, αντί να ξοδέψουμε χρόνο Ο(Ν^2) για να ελέγξουμε ένα ένα όλα τα κελιά του, μπορούμε να χρησιμοποιήσουμε την ιδέα των μερικών αθροισμάτων (prefix sums ή cumulative sums) σε κάθε γραμμή, για να επιταχύνουμε σε Ο(Ν) τον έλεγχο.
Ο(Ν^4): Η ιδέα των μερικών αθροισμάτων μπορεί να επεκταθεί και για 2 διαστάσεις, κι έτσι ο έλεγχος να γίνει σε Ο(1) χρόνο! Θέλει λίγο περισσότερη δουλειά.
Ο(Ν^3): Αν έχουμε υποθέσει το άνω και κάτω άκρο του ορθογωνίου (χρόνος Ο(Ν^2)), το πρόβλημα στην ουσία γίνεται μονοδιάστατο και λύνεται σε Ο(Ν) χρόνο.
Ο(Ν^2): Αν υποθέσουμε μόνο το κάτω άκρο του ορθογωνίου, το πρόβλημα λύνεται πάλι σε Ο(Ν) χρόνο. Πρόκειται μάλιστα για ένα πρόβλημα που μπορεί να είναι γνωστό σε αρκετούς από εσάς που μπορέσατε να βρείτε την Ο(Ν^3) λύση (όχι απαραίτητα σε όλους βέβαια).
Καλή συνέχεια!
Ο(Ν^6): Δε σχολιάζω τίποτα.
Ο(Ν^5): Αν θέλουμε να ελέγξουμε αν συγκεκριμένο ορθογώνιο έχει μόνο χωράφια, αντί να ξοδέψουμε χρόνο Ο(Ν^2) για να ελέγξουμε ένα ένα όλα τα κελιά του, μπορούμε να χρησιμοποιήσουμε την ιδέα των μερικών αθροισμάτων (prefix sums ή cumulative sums) σε κάθε γραμμή, για να επιταχύνουμε σε Ο(Ν) τον έλεγχο.
Ο(Ν^4): Η ιδέα των μερικών αθροισμάτων μπορεί να επεκταθεί και για 2 διαστάσεις, κι έτσι ο έλεγχος να γίνει σε Ο(1) χρόνο! Θέλει λίγο περισσότερη δουλειά.
Ο(Ν^3): Αν έχουμε υποθέσει το άνω και κάτω άκρο του ορθογωνίου (χρόνος Ο(Ν^2)), το πρόβλημα στην ουσία γίνεται μονοδιάστατο και λύνεται σε Ο(Ν) χρόνο.
Ο(Ν^2): Αν υποθέσουμε μόνο το κάτω άκρο του ορθογωνίου, το πρόβλημα λύνεται πάλι σε Ο(Ν) χρόνο. Πρόκειται μάλιστα για ένα πρόβλημα που μπορεί να είναι γνωστό σε αρκετούς από εσάς που μπορέσατε να βρείτε την Ο(Ν^3) λύση (όχι απαραίτητα σε όλους βέβαια).
Καλή συνέχεια!
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Πρόταση λύσης;
Πώς στέλνω μια πρόταση λύσης;
Ας δοκιμάσουμε το tag <spoiler> :-)
---
---
- Spoiler: show
---
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Συγγνώμη για την ενημέρωση τελευταίας στιγμής. Η συνάντηση θα γίνει αύριο 31/10, στις 15.00 ώρα Ελλάδας, και το λινκ για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09
Meeting ID: 675 8682 5824
Passcode: 988982
Θυμηθείτε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στο whiteboard (η έκδοση μέσω browser δε δίνει τέτοια δυνατότητα).
Τα λέμε αύριο!
Meeting ID: 675 8682 5824
Passcode: 988982
Θυμηθείτε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στο whiteboard (η έκδοση μέσω browser δε δίνει τέτοια δυνατότητα).
Τα λέμε αύριο!
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Η O(n^2) λύση μου για όποιον ενδιαφέρεται
- Spoiler: show
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Ερώτηση: στην συνάντηση που κάναμε είχαμε πει ότι η βέλτιστη λύση είναι αυτή με το histogra που έκανα πάνω και συμπεραίναμε ότι είναι περιπλοκότητας O(n^2) αλλά αφού για κάθε σειρά τρέχω το historgra (που κοστίζει O(n)) δεν πρέπει η λύση αυτή να είναι περιπλοκότητας O(n^3)?
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Τρέχεις ένα for για καθε σειρα και εκει κάνεις δυο ανεξάρτητα loop, το ένα ενημερώνει τον πίνακα histogram και αφου τελειωσε αυτο καλείς την histogra() συνάρτηση. Αυτά τα loop δεν είναι φωλιασμένα.
Αρα O(N^2) ή κάτι σαν N*(N+N) που είναι O(N^2)
Χάνω κάτι;
Αρα O(N^2) ή κάτι σαν N*(N+N) που είναι O(N^2)
Χάνω κάτι;
-
- Δημοσιεύσεις: 33
- Εγγραφή: Σάβ Φεβ 08, 2020 5:39 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Σωστά, δίκαιο έχεις απλά μπερδεύτηκα με τα 3 N
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Συνοψίζω πολύ γρήγορα τις λύσεις που συζητήθηκαν:
Καταρχάς δεν υπάρχει λόγος να σκεφτόμαστε με όρους Χ και Τ. Θα λέμε ότι έχουμε 0 και 1 (τα Χ είναι 0, τα Τ είναι 1).
- O(N^6): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε O(N^2) χρόνο για να ελέγξουμε ένα-ένα όλα τα κελιά του, και να δούμε αν είναι όλα ίσα με 0.
- O(N^5): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε Ο(Ν) χρόνο για να ελέγξουμε μία-μία όλες τις γραμμές του, και να δούμε αν όλες περιέχουν μόνο μηδενικά.
Για να απαντάμε σε Ο(1) ανά γραμμή, παρατηρούμε ότι μία γραμμή έχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων της τα οποία μας ενδιαφέρουν είναι ακριβώς 0.
Αυτό μπορούμε να το πετύχουμε με χρήση της τεχνικής prefix sums. Δηλαδή για κάθε γραμμή, χτίζουμε, κατά την προεργασία, τον αντίστοιχα πίνακα των prefix sums.
- O(N^4): Για κάθε ένα από τα Ο(Ν^4) ορθογώνια, ξοδεύουμε Ο(1) χρόνο για να το ελέγξουμε.
Για να το πετύχουμε αυτό, παρατηρούμε ότι ένα ορθογώνιο περιέχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων του είναι 0.
Απαντάμε το άθροισμα ορθογωνίου με 2d prefix sum!
- O(N^3): Σε Ο(Ν^2) χρόνο δοκιμάζουμε κάθε συνδυασμό για την άνω και κάτω πλευρά των ορθογωνίων που μας νοιάζουν. Έπειτα, το πρόβλημα γίνεται 'μονοδιάστατο', δηλαδή σε κάθε θέση i έχουμε ως τιμή το άθροισμα των στοιχείων της στήλης i που βρίσκονται ανάμεσα στις 2 κατακόρυφες γραμμές. Αρκεί να εντοπίσουμε το μέγιστο συνεχόμενο διάστημα (στον νέο μονοδιάστατο πίνακα) που έχει μόνο μηδενικά. Αυτό λύνεται σε Ο(Ν), το πώς αφήνεται ως άσκηση για τον αναγνώστη.
- Ο(Ν^2): Χρειάζεται να λύσουμε πρώτα γραμμικά το πρόβλημα https://www.spoj.com/problems/HISTOGRA/ Θεωρώντας ότι μπορούμε να το λύσουμε, τότε για κάθε οριζόντια γραμμή (τις διατρέχουμε από πάνω προς τα κάτω), η οποία ορίζει την κάτω πλευρά των ορθογωνίων μας, αρκεί να εφαρμόσουμε τη λύση του προβλήματος histogra σε έναν νέο πίνακα.
Ο νέος πίνακας προκύπτει αν σε κάθε θέση του γράψουμε το πλήθος των συνεχόμενων μηδενικών κελιών στη συγκεκριμένη στήλη, από την οριζόντια γραμμή που θεωρήσαμε, και πάνω.
Κατόπιν δοκιμάζουμε την επόμενη (αμέσως από κάτω) οριζόντια γραμμή. Αφήνεται ως άσκηση στον αναγνώστη πώς ανανεώνουμε γρήγορα τον βοηθητικό πίνακα, πάνω στον οποίο εφαρμόζουμε τη λύση του histogra.
Εννοείται μπορείτε να ρωτήσετε εδώ πέρα ό,τι δεν έχετε καταλάβει.
Καταρχάς δεν υπάρχει λόγος να σκεφτόμαστε με όρους Χ και Τ. Θα λέμε ότι έχουμε 0 και 1 (τα Χ είναι 0, τα Τ είναι 1).
- O(N^6): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε O(N^2) χρόνο για να ελέγξουμε ένα-ένα όλα τα κελιά του, και να δούμε αν είναι όλα ίσα με 0.
- O(N^5): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε Ο(Ν) χρόνο για να ελέγξουμε μία-μία όλες τις γραμμές του, και να δούμε αν όλες περιέχουν μόνο μηδενικά.
Για να απαντάμε σε Ο(1) ανά γραμμή, παρατηρούμε ότι μία γραμμή έχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων της τα οποία μας ενδιαφέρουν είναι ακριβώς 0.
Αυτό μπορούμε να το πετύχουμε με χρήση της τεχνικής prefix sums. Δηλαδή για κάθε γραμμή, χτίζουμε, κατά την προεργασία, τον αντίστοιχα πίνακα των prefix sums.
- O(N^4): Για κάθε ένα από τα Ο(Ν^4) ορθογώνια, ξοδεύουμε Ο(1) χρόνο για να το ελέγξουμε.
Για να το πετύχουμε αυτό, παρατηρούμε ότι ένα ορθογώνιο περιέχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων του είναι 0.
Απαντάμε το άθροισμα ορθογωνίου με 2d prefix sum!
- O(N^3): Σε Ο(Ν^2) χρόνο δοκιμάζουμε κάθε συνδυασμό για την άνω και κάτω πλευρά των ορθογωνίων που μας νοιάζουν. Έπειτα, το πρόβλημα γίνεται 'μονοδιάστατο', δηλαδή σε κάθε θέση i έχουμε ως τιμή το άθροισμα των στοιχείων της στήλης i που βρίσκονται ανάμεσα στις 2 κατακόρυφες γραμμές. Αρκεί να εντοπίσουμε το μέγιστο συνεχόμενο διάστημα (στον νέο μονοδιάστατο πίνακα) που έχει μόνο μηδενικά. Αυτό λύνεται σε Ο(Ν), το πώς αφήνεται ως άσκηση για τον αναγνώστη.
- Ο(Ν^2): Χρειάζεται να λύσουμε πρώτα γραμμικά το πρόβλημα https://www.spoj.com/problems/HISTOGRA/ Θεωρώντας ότι μπορούμε να το λύσουμε, τότε για κάθε οριζόντια γραμμή (τις διατρέχουμε από πάνω προς τα κάτω), η οποία ορίζει την κάτω πλευρά των ορθογωνίων μας, αρκεί να εφαρμόσουμε τη λύση του προβλήματος histogra σε έναν νέο πίνακα.
Ο νέος πίνακας προκύπτει αν σε κάθε θέση του γράψουμε το πλήθος των συνεχόμενων μηδενικών κελιών στη συγκεκριμένη στήλη, από την οριζόντια γραμμή που θεωρήσαμε, και πάνω.
Κατόπιν δοκιμάζουμε την επόμενη (αμέσως από κάτω) οριζόντια γραμμή. Αφήνεται ως άσκηση στον αναγνώστη πώς ανανεώνουμε γρήγορα τον βοηθητικό πίνακα, πάνω στον οποίο εφαρμόζουμε τη λύση του histogra.
Εννοείται μπορείτε να ρωτήσετε εδώ πέρα ό,τι δεν έχετε καταλάβει.
Λύσεις θεμάτων ΠΔΠ: 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Re: Μηνιαία Πρόκληση: Οκτώβριος 2020
Μια ακόμα παραλλαγή του προβλήματος
https://hsin.hr/coci/contest1_tasks.pdf
πρόβλημα 3d histogram
Οι περιορισμοί που δίνονται (N<=200000) σημαίνει ότι είναι αποδεκτές λύσεις γραμμικές (φυσικά), λογαριθμικές και τετράγωνο λογαριθμικής λύσης το πολύ. Τετράγωνα και μετά... δεν....
hint
![Mr. Green :mrgreen:](./images/smilies/icon_mrgreen.gif)
https://hsin.hr/coci/contest1_tasks.pdf
πρόβλημα 3d histogram
Οι περιορισμοί που δίνονται (N<=200000) σημαίνει ότι είναι αποδεκτές λύσεις γραμμικές (φυσικά), λογαριθμικές και τετράγωνο λογαριθμικής λύσης το πολύ. Τετράγωνα και μετά... δεν....
hint
- Spoiler: show