Μηνιαία Πρόκληση: Νοέμβριος 2020

[Κηπουρίδης]

Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Νοέμβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Στο πρόβλημα μας δίνεται ένας πίνακας με Ν στοιχεία, και θέλουμε να τον ταξινομήσουμε. Το μόνο που επιτρέπεται να κάνουμε είναι να αντιμεταθέτουμε δύο γειτονικά στοιχεία. Μετά την αντιμετάθεση, το στοιχείο που ήταν δεξιά (και τώρα πήγε αριστερά) αυξάνεται κατά 1, ενώ το άλλο στοιχείο μειώνεται κατά 1.
Ο στόχος είναι να ταξινομήσουμε τον πίνακα και να δώσουμε έναν πιθανό ταξινομημένο πίνακα, ή να διαπιστώσουμε ότι δεν υπάρχει λύση.

Ζητάμε πολυπλοκότητα O(NlogN).
Μπορείτε να το δοκιμάσετε εδώ:
https://www.hackerearth.com/practice/al ... ted-array/

Bonus ερώτηση: Μπορείτε σε Ο(Ν) να απαντήσετε YES ή NO στο παραπάνω πρόβλημα; Χωρίς δηλαδή να πρέπει να τυπωθεί κι ο πίνακας.

Στις 15 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου παρακαλώ αν το ξεχάσω.

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

[bettypan]

Μια υπενθύμιση για το hint...?!
Ευχαριστούμε Βαγγέλη..!!!

[Κηπουρίδης]

Κι εγώ ευχαριστώ, και για την υπενθύμιση που πάντα χρειάζομαι, και για την παρέα μια φορά το μήνα!

Αν γνωρίζω ότι το στοιχείο που βρισκόταν αρχικά στη θέση 1, καταλήγει στη θέση 3, τότε μπορώ να ξέρω την τελική του τιμή (ναι); Ή πρέπει να ξέρω πώς έφτασε εκεί, τι πράξεις συνέβησαν (όχι);
Προσπαθήστε να σκεφτείτε, αν γενικά στη θέση i σας δίνεται ο αριθμός A και θέλετε να τον πάτε στη θέση j, ποια θα είναι η τιμή του;

Καλή συνέχεια!

[Κηπουρίδης]

Η συνάντηση θα γίνει το επόμενο Σάββατο, 5/12, στις 15.00 ώρα Ελλάδας, και το λινκ για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09

Meeting ID: 675 8682 5824
Passcode: 988982

Θυμηθείτε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στο whiteboard (η έκδοση μέσω browser δε δίνει τέτοια δυνατότητα).

Τα λέμε σύντομα!

[Marilenatsiop]

Σάββατο 5/12 μήπως ;

[Κηπουρίδης]

Σωστή, ευχαριστώ!! Έκανα έντιτ τώρα για να μην μπερδευτεί κανείς (πράγμα που κάνει το ποστ σου να φαίνεται λίγο περίεργο, χιχι).

[switch]

Ένα ακόμα hint για όποιον θέλει λίγο ακόμα βοήθεια, με μορφή όμως ... ερωτήσεων:

• πόσοι αριθμοί διαγωνίζονται για την πρώτη θέση;
• πόσοι αριθμοί επιτρέπεται να καταλάβουν την πρώτη θέση;
• πόσοι αριθμοί μπορεί να θέλουν να καταλάβουν την πρώτη θέση;

Όταν απαντηθούν αυτές οι ερωτήσεις, θα ρωτήσω για τη δεύτερη θέση