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

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

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

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

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

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

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

Στις 15 του μηνός θα προσπαθήσω να δώσω ένα 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/
bettypan
Δημοσιεύσεις: 14
Εγγραφή: Σάβ Ιούλ 25, 2020 12:44 pm

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

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

Μια υπενθύμιση για το hint...?!
Ευχαριστούμε Βαγγέλη..!!!
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

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

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

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

Καλή συνέχεια!
Λύσεις θεμάτων ΠΔΠ: 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/12, στις 15.00 ώρα Ελλάδας, και το λινκ για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09

Meeting ID: 675 8682 5824
Passcode: 988982

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

Τα λέμε σύντομα!
Λύσεις θεμάτων ΠΔΠ: 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 »

Σάββατο 5/12 μήπως ;
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 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/
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

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

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

Ένα ακόμα hint για όποιον θέλει λίγο ακόμα βοήθεια, με μορφή όμως ... ερωτήσεων:
  • πόσοι αριθμοί διαγωνίζονται για την πρώτη θέση;
  • πόσοι αριθμοί επιτρέπεται να καταλάβουν την πρώτη θέση;
  • πόσοι αριθμοί μπορεί να θέλουν να καταλάβουν την πρώτη θέση;
Όταν απαντηθούν αυτές οι ερωτήσεις, θα ρωτήσω για τη δεύτερη θέση :mrgreen:
Απάντηση