Μηνιαία Πρόκληση: Νοέμβριος 2020
Δημοσιεύτηκε: Κυρ Νοέμ 01, 2020 8:43 pm
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Νοέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας πίνακας με Ν στοιχεία, και θέλουμε να τον ταξινομήσουμε. Το μόνο που επιτρέπεται να κάνουμε είναι να αντιμεταθέτουμε δύο γειτονικά στοιχεία. Μετά την αντιμετάθεση, το στοιχείο που ήταν δεξιά (και τώρα πήγε αριστερά) αυξάνεται κατά 1, ενώ το άλλο στοιχείο μειώνεται κατά 1.
Ο στόχος είναι να ταξινομήσουμε τον πίνακα και να δώσουμε έναν πιθανό ταξινομημένο πίνακα, ή να διαπιστώσουμε ότι δεν υπάρχει λύση.
Ζητάμε πολυπλοκότητα O(NlogN).
Μπορείτε να το δοκιμάσετε εδώ:
https://www.hackerearth.com/practice/al ... ted-array/
Bonus ερώτηση: Μπορείτε σε Ο(Ν) να απαντήσετε YES ή NO στο παραπάνω πρόβλημα; Χωρίς δηλαδή να πρέπει να τυπωθεί κι ο πίνακας.
Στις 15 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου παρακαλώ αν το ξεχάσω.
Καλή επιτυχία!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Στο πρόβλημα μας δίνεται ένας πίνακας με Ν στοιχεία, και θέλουμε να τον ταξινομήσουμε. Το μόνο που επιτρέπεται να κάνουμε είναι να αντιμεταθέτουμε δύο γειτονικά στοιχεία. Μετά την αντιμετάθεση, το στοιχείο που ήταν δεξιά (και τώρα πήγε αριστερά) αυξάνεται κατά 1, ενώ το άλλο στοιχείο μειώνεται κατά 1.
Ο στόχος είναι να ταξινομήσουμε τον πίνακα και να δώσουμε έναν πιθανό ταξινομημένο πίνακα, ή να διαπιστώσουμε ότι δεν υπάρχει λύση.
Ζητάμε πολυπλοκότητα O(NlogN).
Μπορείτε να το δοκιμάσετε εδώ:
https://www.hackerearth.com/practice/al ... ted-array/
Bonus ερώτηση: Μπορείτε σε Ο(Ν) να απαντήσετε YES ή NO στο παραπάνω πρόβλημα; Χωρίς δηλαδή να πρέπει να τυπωθεί κι ο πίνακας.
Στις 15 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου παρακαλώ αν το ξεχάσω.
Καλή επιτυχία!