Θέματα τελικής φάσης:
PDP-28_C
Θέμα 1ο: Εκδρομή για σκι
Έχουμε έναν μονοδιάστατο πίνακα μέχρι 2.000.000 φυσικών αριθμών Α (με θετικές τιμές μεταξύ 1 και 1.000.000.000). Να βρεθεί η μέγιστη απόσταση μεταξύ των θέσεων i και j, ώστε i<j και A[i]<=A[j].
Μια δυνατή λύση:
skitrip5
Βασική ιδέα για την παραπάνω λύση:
αποθηκεύουμε σε εναν τριγωνικό πίνακα τιμές.
Ο πίνακας θα μοιάζει με το γνωστο μας ισορροπημένο δυαδικό δέντρο.
Στην βάση A[Line][i] (line==0, 0<=i<N), έχουμε τα Ν στοιχεία εισόδου.
Στην επόμενη γραμμή/επίπεδο A[1][i] (line==1, 0<=i<N/2 ή 0<=i<N/2+1) έχουμε Ν/2 στοιχεία (αν Ν άρτιος) ή Ν/2+1 (αν Ν περιττός)
Συνεχιζουμε έως ότου να έχουμε μόνο 1 στοιχειο (το οποίο συμβαίνει στην γραμμη last_line).
Κάθε στοιχείο i της γραμμης line, με line>0, είναι αποθηκευμένο στη θεση A[line][i] και έχει το ελάχιστο και μεγιστο στοιχείο απο τα A[line-1][i*2] και (αν υπάρχει) του A[line-1][i*2+1].
Μνήμη που απαιτείται για τον τριγωνικό πίνακα: 32Mbytes για 2.000.000 "στάσεις" τρένου. Το όριο της άσκησης είναι 128Mbyte.
Η ταχύτερη λύση (πολυπλοκότητας Ο(Ν)) ακολουθεί:
skitrip6_linear
Για κάθε αριθμό (ύψος) από την αριστερή πλευρά του πίνακα, αγνοούμε αυτά που έχουν μικρότερο αριθμό αριστερότερα από αυτά (διότι η Κατερίνα θα επιβιβαζόταν στην αριστερότερη στάση).
Από την δεξιά πλευρά, αγνοούμε όσους σταθμούς έχουν ύψος μικρότερο από κάποιον δεξιότερο τους (γιατί η Κατερίνα θα κατέβαινε στον δεξιότερο για να ξεκινήσει να κάνει σκι).
Τα στοιχεία που απομένουν είναι ταξινομημένα (από την αριστερή πλευρά με αύξουσα σειρά) και από την δεξιά με φθίνουσα.
Αφού βρούμε τις αγνοημένες στάσεις, κάνουμε μία προσπέλαση στον πίνακα για κάθε μη αγνοημένο στοιχείο A[i] και βρίσκουμε το πρώτο (ή το επόμενο) δεξιότερο A[right] που είναι μεγαλύτερο ή ίσο με το A[i]