pdp forum

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

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

Καλημέρα!
Έχω μία ερώτηση για το πρόβλημα :
Αν το Ν είναι άρτιο, τότε ο 2ος πίνακας θα είναι της μορφής [1, 2, 3, 3, 2, 1] (για Ν=6 π.χ.) ?

Ακριβώς Δημήτρη.

Ζητώ συγγνώμη που άργησα να δώσω το πρώτο 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)

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

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

Passcode 048093

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

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

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

Τα λέμε το Σάββατο 5 Σεπτεμβρίου!

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

Spoiler: hide
Αν σας έλεγα ότι η σωστή λύση είναι το πρώτο στοιχείο να έχει την τιμή Χ (κι άρα το δεύτερο την τιμή Χ+1, το τρίτο την Χ+2... κλπ κλπ) μπορείτε να βρείτε πόσο θα κόστιζε η μετατροπή της πρώτης ακολουθίας στη δεύτερη;

Δλδ από την ακολουθία 1 2 3 2 1 στην ακολουθία 2 3 4 3 2 , για το συγκεκριμένο παράδειγμα;;;

Παιδιά συγγνώμη, μπαίνω σε πολύ λίγο, πρόβλημα με το ίντερνετ.

Άρα στο spoiler 2 βρίσκουμε την διάμεση τιμή του αρχικού πίνακα

Marilenatsiop έγραψε: ↑Σάβ Σεπ 05, 2020 7:38 pm Άρα στο spoiler 2 βρίσκουμε την διάμεση τιμή του αρχικού πίνακα

Ακριβώς!