Μηνιαία Πρόκληση: Αύγουστος 2020

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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.

Καλή επιτυχία!
Λύσεις θεμάτων ΠΔΠ: 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/
jbalatos
Δημοσιεύσεις: 4
Εγγραφή: Κυρ Αύγ 09, 2020 2:22 pm

Re: Μηνιαία Πρόκληση: Αύγουστος 2020

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

Καλημέρα!
Έχω μία ερώτηση για το πρόβλημα :
Αν το Ν είναι άρτιο, τότε ο 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Αύγουστος 2020

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

Ζητώ συγγνώμη που άργησα να δώσω το πρώτο hint. Λόγω της καθυστέρησης, τα δίνω όλα μαζεμένα τώρα:

Hint 1:
Spoiler: show
Αν σας έλεγα ότι η σωστή λύση είναι το πρώτο στοιχείο να έχει την τιμή Χ (κι άρα το δεύτερο την τιμή Χ+1, το τρίτο την Χ+2... κλπ κλπ) μπορείτε να βρείτε πόσο θα κόστιζε η μετατροπή της πρώτης ακολουθίας στη δεύτερη;
Hint 2:
Spoiler: show
Σκεφτείτε ένα άλλο (σχετικό) πρόβλημα. Αντί να θέλετε να δημιουργήσετε παλίνδρομο με τους περιορισμούς του αρχικού μας προβλήματος, τώρα θέλετε να κάνετε όλα τα στοιχεία ίσα. Για παράδειγμα αν έχεις τον πίνακα "5 1 3" τότε μπορείς να τα κάνεις όλα ίσα με 3, με κόστος 2+2+0=4, ή να τα κάνεις όλα ίσα με 7, με κόστος 2+6+4=12. Μπορείτε να λύσετε αυτό το (πιο εύκολο) πρόβλημα;
Hint 3:
Spoiler: show
Χρησιμοποιώντας τα παραπάνω Hints, υπάρχει τρόπος να πάρεις τον πίνακα Α του αρχικού προβλήματος, και να δημιουργήσεις έναν πίνακα B που η λύση του στο πρόβλημα του Hint-2 να είναι ίση με τη λύση του προβλήματός μας. Δηλαδή Solution_Original_Problem(A) = Solution_Hint2_Problem(B)
Λύσεις θεμάτων ΠΔΠ: 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

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

Λόγω πολλών υποχρεώσεών μου αυτή την περίοδο, θα κάνουμε την κλήση το επόμενο Σάββατο, 5 Σεπτεμβρίου, στις 18.00 το απόγευμα (ώρα Ελλάδας). Στο μεταξύ βεβαίως θα ανέβει η μηνιαία πρόκληση Σεπτεμβρίου.

Το λινκ της κλήσης: 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/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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/
Marilenatsiop
Δημοσιεύσεις: 27
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

Re: Μηνιαία Πρόκληση: Αύγουστος 2020

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

Spoiler: hide
Αν σας έλεγα ότι η σωστή λύση είναι το πρώτο στοιχείο να έχει την τιμή Χ (κι άρα το δεύτερο την τιμή Χ+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/
Marilenatsiop
Δημοσιεύσεις: 27
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

Re: Μηνιαία Πρόκληση: Αύγουστος 2020

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

Άρα στο 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/
Απάντηση