problem challenge #3

Το πρόβλημα μας ζητάει τον μεγαλύτερο αριθμό από γέφυρες που δεν αλληλοτέμνονται. Προφανώς μπορούμε να σορτάρουμε ως προς την 1 συντεταγμένη, δεν έχει σημασία η σειρά με την οποία μας δίνεται το input. Αφου σορτάρουμε ως προς Χ ( Α[ i ].X >= A[ i - 1 ].X για κάθε i ), μένει να βρούμε την μεγαλύτερη υποακολουθία "ασύμβατων" γεφυρών.

Εστω πως έχω πάρει μια γέφυρα ( την i-οστή ας πούμε ), με συντεταγμένες ( Α[ i ].X, A[ i ].Y ) και έστω πως επιλέγω και μια άλλη j, με j > i, προφανώς Α[ j ].X >= A[ i ].X, τι πρέπει να ισχύει για τις Y συντεταγμένες; Προφανώς ( κάντε ένα σχήμα και θα φανεί ), πρέπει να ισχύει A[ j ].Y >= A[ i ].Y, πρέπει δηλαδή οι Υ συντεταγμένες να σχηματίζουν μιας αύξουσα ακολουθία. Εφ' όσον θέλουμε να πάρουμε όσο το δυνατόν περισσότερες αρκεί να βρούμε την μέγιστη αύξουσα υποακολουθία των Y συντεταγμένων, αφού έχουμε σορτάρει ως προς Χ. Υπάρχουν διάφοροι τρόποι να το κάνουμε αυτό ( με dp ), ο πιο κλασσικός Ο( n^2 ) είναι στανταρντ παράδειγμα dp, υπάρχει και στο αρχείο που σας έστειλα, αλλά για να πάρουμε full-score πρέπει να ρίξουμε την πολυπλοκότητα σε O( nlogn ). Αυτό μπορούμε να το κάνουμε είτε με μια δομή δεδομένων ( BIT/segment tree ), είτε με τον πιο παραδοσιακό τρόπο που παρουσιάζεται στο παρακάτω άρθρο.

https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms