Μηνιαία Πρόκληση: Αύγουστος 2020
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Μηνιαία Πρόκληση: Αύγουστος 2020
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Αύγουστο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας πίνακας με Ν θέσεις, έστω ο:
1 1 8 4 9
κι εμείς φτιάξουμε ένα δεύτερο πίνακα με Ν θέσεις που να μοιάζει κάπως έτσι:
1 2 3 2 1
ή έτσι:
2 3 4 3 2
κλπ
Θέλουμε δηλαδή να κάνουμε παλίνδρομο τον πίνακα, με το πρώτο του μισό να είναι μια αριθμητική πρόοδος, όπου κάθε αριθμός θα είναι κατά ένα μεγαλύτερος απ' τον προηγούμενο.
Στόχος μας είναι η απόσταση του αρχικού πίνακα από τον τελικό να είναι όσο το δυνατόν μικρότερη. Λέγοντας απόσταση εννοούμε το άθροισμα των διαφορών σε κάθε θέση. Για παράδειγμα, ο (1,2,3,2,1) έχει απόσταση
|1-1| + |1-2| + |8-3| + |4-2| + |9-1| = 0+1+5+2+8 = 16
ενώ ο (2,3,4,3,2) έχει απόσταση:
|1-2| + |1-3| + |8-4| + |4-3| + |9-2| = 1+2+4+1+7 = 15
Το μέγεθος του πίνακα είναι το πολύ 100.000, και οι αριθμοί που περιέχει είναι μεταξύ 1 και 100.000.
Οι λύσεις που περιμένουμε είναι Ο(Ν^2), Ο(ΝlogN) και O(N).
Στις 15 και στις 25 του μηνός θα δώσω και από ένα hint.
Καλή επιτυχία!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας πίνακας με Ν θέσεις, έστω ο:
1 1 8 4 9
κι εμείς φτιάξουμε ένα δεύτερο πίνακα με Ν θέσεις που να μοιάζει κάπως έτσι:
1 2 3 2 1
ή έτσι:
2 3 4 3 2
κλπ
Θέλουμε δηλαδή να κάνουμε παλίνδρομο τον πίνακα, με το πρώτο του μισό να είναι μια αριθμητική πρόοδος, όπου κάθε αριθμός θα είναι κατά ένα μεγαλύτερος απ' τον προηγούμενο.
Στόχος μας είναι η απόσταση του αρχικού πίνακα από τον τελικό να είναι όσο το δυνατόν μικρότερη. Λέγοντας απόσταση εννοούμε το άθροισμα των διαφορών σε κάθε θέση. Για παράδειγμα, ο (1,2,3,2,1) έχει απόσταση
|1-1| + |1-2| + |8-3| + |4-2| + |9-1| = 0+1+5+2+8 = 16
ενώ ο (2,3,4,3,2) έχει απόσταση:
|1-2| + |1-3| + |8-4| + |4-3| + |9-2| = 1+2+4+1+7 = 15
Το μέγεθος του πίνακα είναι το πολύ 100.000, και οι αριθμοί που περιέχει είναι μεταξύ 1 και 100.000.
Οι λύσεις που περιμένουμε είναι Ο(Ν^2), Ο(ΝlogN) και O(N).
Στις 15 και στις 25 του μηνός θα δώσω και από ένα 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ος πίνακας θα είναι της μορφής [1, 2, 3, 3, 2, 1] (για Ν=6 π.χ.) ?
Έχω μία ερώτηση για το πρόβλημα :
Αν το Ν είναι άρτιο, τότε ο 2ος πίνακας θα είναι της μορφής [1, 2, 3, 3, 2, 1] (για Ν=6 π.χ.) ?
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Ακριβώς Δημήτρη.
Λύσεις θεμάτων ΠΔΠ: 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/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Ζητώ συγγνώμη που άργησα να δώσω το πρώτο hint. Λόγω της καθυστέρησης, τα δίνω όλα μαζεμένα τώρα:
Hint 1:
Hint 1:
- Spoiler: show
- Spoiler: show
- Spoiler: show
Λύσεις θεμάτων ΠΔΠ: 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/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Λόγω πολλών υποχρεώσεών μου αυτή την περίοδο, θα κάνουμε την κλήση το επόμενο Σάββατο, 5 Σεπτεμβρίου, στις 18.00 το απόγευμα (ώρα Ελλάδας). Στο μεταξύ βεβαίως θα ανέβει η μηνιαία πρόκληση Σεπτεμβρίου.
Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/64208215479?p ... FmSmxGQT09
Passcode 048093
Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.
Υ.Γ.: Προς το τέλος της σύσκεψης θα συζητήσουμε και σχετικά με απορίες/προτάσεις σας σχετικά με τον ΠΔΠ. Καλό θα είναι, να γράψετε εδώ πέρα, πριν τη σύσκεψη, οποιεσδήποτε απορίες/προτάσεις έχετε, ώστε να προετοιμαστούμε όλοι κατάλληλα για τη συζήτηση.
Ξεκινώ εγώ καταθέτοντας δύο ερωτήσεις που με απασχολούν, ώστε να συζητηθούν:
1) Επίλυση προβλημάτων: Σας βολεύει το Hellenico για προπόνηση για το διαγωνισμό; Ανεξάρτητα από την απάντησή σας, μπορείτε να αναφέρετε ένα-δυο πράγματα που βοηθάνε κι ένα-δυο που θα προτιμούσατε να βελτιωθούν;
2) Θεωρία: Σας είναι πάντα σαφές τι θεωρία χρειάζεται να διαβάζετε για το διαγωνισμό; Αν ναι, σας είναι σαφές και από πού θα την διαβάσετε;
Τα λέμε το Σάββατο 5 Σεπτεμβρίου!
Το λινκ της κλήσης: https://ucph-ku.zoom.us/j/64208215479?p ... FmSmxGQT09
Passcode 048093
Κατεβάστε την εφαρμογή γιατί από την online έκδοση υπάρχουν προβλήματα με την προβολή του ασπροπίνακα.
Υ.Γ.: Προς το τέλος της σύσκεψης θα συζητήσουμε και σχετικά με απορίες/προτάσεις σας σχετικά με τον ΠΔΠ. Καλό θα είναι, να γράψετε εδώ πέρα, πριν τη σύσκεψη, οποιεσδήποτε απορίες/προτάσεις έχετε, ώστε να προετοιμαστούμε όλοι κατάλληλα για τη συζήτηση.
Ξεκινώ εγώ καταθέτοντας δύο ερωτήσεις που με απασχολούν, ώστε να συζητηθούν:
1) Επίλυση προβλημάτων: Σας βολεύει το Hellenico για προπόνηση για το διαγωνισμό; Ανεξάρτητα από την απάντησή σας, μπορείτε να αναφέρετε ένα-δυο πράγματα που βοηθάνε κι ένα-δυο που θα προτιμούσατε να βελτιωθούν;
2) Θεωρία: Σας είναι πάντα σαφές τι θεωρία χρειάζεται να διαβάζετε για το διαγωνισμό; Αν ναι, σας είναι σαφές και από πού θα την διαβάσετε;
Τα λέμε το Σάββατο 5 Σεπτεμβρίου!
Λύσεις θεμάτων ΠΔΠ: 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/
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Είχα γράψει άλλη ώρα για την κλήση, διορθώνω τώρα σε 18.00 (ώρα Ελλάδας) στις 5 Σεπτεμβρίου.
Λύσεις θεμάτων ΠΔΠ: 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/
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Spoiler: hide
Αν σας έλεγα ότι η σωστή λύση είναι το πρώτο στοιχείο να έχει την τιμή Χ (κι άρα το δεύτερο την τιμή Χ+1, το τρίτο την Χ+2... κλπ κλπ) μπορείτε να βρείτε πόσο θα κόστιζε η μετατροπή της πρώτης ακολουθίας στη δεύτερη;
Δλδ από την ακολουθία 1 2 3 2 1 στην ακολουθία 2 3 4 3 2 , για το συγκεκριμένο παράδειγμα;;;
Αν σας έλεγα ότι η σωστή λύση είναι το πρώτο στοιχείο να έχει την τιμή Χ (κι άρα το δεύτερο την τιμή Χ+1, το τρίτο την Χ+2... κλπ κλπ) μπορείτε να βρείτε πόσο θα κόστιζε η μετατροπή της πρώτης ακολουθίας στη δεύτερη;
Δλδ από την ακολουθία 1 2 3 2 1 στην ακολουθία 2 3 4 3 2 , για το συγκεκριμένο παράδειγμα;;;
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Παιδιά συγγνώμη, μπαίνω σε πολύ λίγο, πρόβλημα με το ίντερνετ.
Λύσεις θεμάτων ΠΔΠ: 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/
-
- Δημοσιεύσεις: 27
- Εγγραφή: Παρ Ιουν 12, 2020 10:04 am
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Άρα στο spoiler 2 βρίσκουμε την διάμεση τιμή του αρχικού πίνακα
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Μηνιαία Πρόκληση: Αύγουστος 2020
Ακριβώς!Marilenatsiop έγραψε: ↑Σάβ Σεπ 05, 2020 7:38 pm Άρα στο spoiler 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/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/