Αρχική > 35ος ΠΔΠ > roadfix (εκφώνηση)

35ος ΠΔΠ B' Φάση: Επισκευή δρόμου (roadfix) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

Επεξήγηση εκφώνησης

Μας δίνονται \(N\) ευθύγραμμα τμήματα πάνω σε μία ευθεία, κι ένα κόστος για το κάθε ευθύγραμμο τμήμα. Κατόπιν μας δίνονται \(M\) ερωτήματα. Το κάθε ερώτημα είναι ένα νέο ευθύγραμμο τμήμα. Καλούμαστε να βρούμε ένα υποσύνολο των \(N\) ευθυγράμμων τμημάτων που να καλύπτει πλήρως το υπό ερώτηση ευθύγραμμο τμήμα, και ταυτόχρονα να ελαχιστοποιεί το άθροισμα των κοστών.

Το \(i\)-οστό από τα \(N\) ευθύγραμμα τμήματα έχει το αριστερό του άκρο στη θέση \(X_i\), μήκος \(L_i\) (άρα το δεξί του άκρο βρίσκεται στη θέση \(Y_i=X_i+L_i\)), και κόστος \(C_i\). Για χάρην ευκολίας στην παρουσίαση θα θεωρήσουμε ότι έχουμε μόνο ένα ερώτημα: το αριστερό άκρο του υπό ερώτηση ευθύγραμμου τμήματος βρίσκεται στη θέση \(q_x\), και έχει μήκος \(K\) (άρα το δεξί του άκρο βρίσκεται στη θέση \(q_y=q_x+K\)).

Από εδώ και πέρα, όταν γράφουμε “ευθύγραμμο τμήμα [5,11]” θα εννοούμε το ευθύγραμμο τμήμα που ξεκινάει από τη θέση 5 και έχει μήκος 6. Ο λόγος είναι ότι το δεξί άκρο είναι εν προκειμένω πιο ενδιαφέρουσα πληροφορία από το μήκος.

Στην συνέχεια θα εξηγήσουμε:

  • Γιατί οι άπληστες λύσεις δεν λειτουργούν.
  • Δύο λύσεις βασισμένες σε δυναμικό προγραμματισμό, και οι δύο πολυπλοκότητας \(\mathcal{O}(MN^2)\). Η μία λύση δεν φαίνεται να βελτιώνεται περαιτέρω, αλλά στην άλλη στηρίζονται όλες οι μετέπειτα βελτιώσεις μας.
  • Δύο λύσεις πολυπλοκότητας \(\mathcal{O}(MN\log{N})\).
  • Μία λύση πολυπλοκότητας \(\mathcal{O}(MN\frac{\log{N}}{\log{\log{N}}})\).
  • Μία λύση πολυπλοκότητας \(\mathcal{O}(MN\alpha(N))\).

Η κάθε μία από τις λύσεις που περιγράφουμε χτίζει πάνω στην κατανόηση των προηγούμενων. Καλό διάβασμα!

Άπληστες λύσεις που δεν λειτουργούν (και μία γενικότερη συμβουλή)

Ας ξεκινήσουμε με μία παρατήρηση/συμβουλή. Στο συγκεκριμένο πρόβλημα η σειρά με την οποία μας δίνουν τα ευθύγραμμα τμήματα στην είσοδο δεν επηρεάζει το πρόβλημα. Φανταστείτε, για παράδειγμα, δύο διαφορετικές εισόδους. Στην μία μας δίνονται \(2\) ευθύγραμμα τμήματα, το \([5,10]\) με κόστος \(20\), και το \([15,25]\) με κόστος \(50\). Στην άλλη μας δίνονται \(2\) ευθύγραμμα τμήματα, το \([15,25]\) με κόστος \(50\), και το \([5,10]\) με κόστος \(20\). Καταλαβαίνουμε εύκολα ότι στην ουσία πρόκειται για την ίδια είσοδο με αλλαγμένη σειρά. Η απάντηση σε οποιοδήποτε ερώτημα θα είναι ακριβώς η ίδια και στις δύο περιπτώσεις.

Σε προβλήματα με αυτή την ιδιότητα το πρώτο πράγμα που σκεφτόμαστε είναι πάντα ταξινόμηση. Ως προς τι όμως; Αριστερό άκρο, δεξί άκρο, μήκος, κόστος; Θα το δούμε σύντομα. Στη συνέχεια η πρώτη μας σκέψη είναι οι άπληστοι αλγόριθμοι. Εδώ πέρα δεν λειτουργούν, κι επομένως θα στρέψουμε την προσοχή μας σε αλγορίθμους δυναμικού προγραμματισμού (dynamic programming ή, όπως γράφουμε συνήθως, dp). Πριν περάσουμε στην λύση με δυναμικό προγραμματισμό, ας δώσουμε πρώτα μία διαίσθηση σχετικά με το γιατί οι άπληστοι αλγόριθμοι δε βοηθάνε. Η ίδια συζήτηση θα μας καθοδηγήσει σχετικά με τον τρόπο που θέλουμε να ταξινομήσουμε.

Ένας απλός άπληστος αλγόριθμος είναι να παίρνουμε κάθε φορά το φθηνότερο τμήμα που καλύπτει κάτι ακάλυπτο από το ερώτημα. Για να υλοποιήσουμε αυτό τον αλγόριθμο, θα ταξινομούσαμε κατά κόστος. Όμως αυτός ο αλγόριθμος δε δίνει πάντα τη βέλτιστη λύση. Σκεφτείτε το πολύ απλό παράδειγμα όπου στην είσοδο μας δίνονται τα τμήματα \([0,10]\) με κόστος \(5\), \([10,21]\) με κόστος \(6\), και \([6,12]\) με κόστος \(1\). Ζητάμε να καλύψουμε το τμήμα \([0,20]\).

Οπτική αναπαράσταση προβλήματος

Ο παραπάνω άπληστος αλγόριθμος αυτός ξεκινάει παίρνοντας το τμήμα \([6,12]\), μετά με το \([0,10]\), και τέλος με το \([10,21]\): συνολικό κόστος \(1+5+6=12\). Όμως αν παραλείπαμε το τμήμα \([6,12]\) θα παίρναμε έγκυρη λύση συνολικού κόστους \(5+6=11\).

Ας φανταστούμε έναν άλλο άπληστο αλγόριθμο: αυτόν που διαλέγει το ευθύγραμμο τμήμα που ελαχιστοποιεί τον λόγο μεταξύ του κόστους και του μήκους που ήταν ακάλυπτο και πλέον θα καλυφθεί. Το παραπάνω παράδειγμα δείχνει ότι και αυτός ο αλγόριθμος είναι λάθος: αρχικά διαλέγει το \([6,12]\) γιατί ο λόγος κόστους ανά κάλυψη είναι \(1/6\), ενώ του \([0,10]\) είναι \(5/10\) και του \([10,21]\) είναι \(6/10\) (προσέξτε ότι δε διαιρούμε με 11, που είναι το μήκος του τμήματος \([10,21]\), αλλά με \(10\), που είναι το μήκος που θα καλύψει (ενώ ήταν ακάλυπτο) από το \([0,20]\)). Κατόπιν επιλέγει το \([10,21]\), που έχει λόγο \(6/8\) (το τμήμα \([10,12]\) είναι ήδη καλυμμένο, άρα θα καλύψει μήκος \(8\)), αντί του \([0,10]\) που έχει λόγο \(5/6\). Τέλος, αφού δεν έχει καλυφθεί ολόκληρο το \([0,20]\) θα επιλέξει και το \([0,10]\). Όπως προηγουμένως, η λύση αυτή έχει κόστος \(12\), ενώ η βέλτιστη έχει κόστος \(11\).

Ένας άλλος άπληστος αλγόριθμος είναι αυτός που επιλέγει κάθε φορά το τμήμα που καλύπτει όσο το δυνατόν περισσότερο ακάλυπτο κομμάτι του ερωτήματος. Κι αυτός ο αλγόριθμος είναι λάθος: Αν στο παραπάνω παράδειγμα υπήρχε κι ένα τμήμα [0,20] με κόστος 100, θα το επιλέγαμε πρώτο, και θα πληρώναμε πάρα πολύ.

Λύση 1Α - Δυναμικός προγραμματισμός - \(\mathcal{O}(MN^2)\)

Αφού οι άπληστες λύσεις δεν λειτούργησαν, μπορούμε να σκεφτούμε λύσεις δυναμικού προγραμματισμού. Επιπλέον είδαμε ότι η ταξινόμηση ως προς μήκος ή/και κόστος δεν φαίνεται να μας βοηθάνε. Δοκιμάζουμε λοιπόν να ταξινομήσουμε με βάση το δεξί άκρο. Θα μπορούσαμε να ταξινομήσουμε και με βάση το αριστερό άκρο, αφού το πρόβλημα είναι συμμετρικό. Επιλέξαμε το δεξί άκρο επειδή θεωρούμε ότι κάνει κατανοητότερη την παρουσίαση.

Θα δοκιμάσουμε μία κλασική προσέγγιση δυναμικού προγραμματισμού, να λύσουμε προθέματα του προβλήματός μας. Για παράδειγμα να περιοριστούμε στα πρώτα \(i\) ευθύγραμμα τμήματα (αντί για όλα τα \(N\)), ή να προσποιηθούμε ότι το ερώτημα είναι το \([q_x,Y']\) αντί για \([q_x,q_y]\), όπου \(Y'\le q_y\). Σε αυτή τη λύση, δοκιμάζουμε ταυτόχρονα και τις δύο προσεγγίσεις.

Εδώ θα κάνουμε μια παύση, γιατί βρισκόμαστε ακριβώς στο σημείο που μπερδεύει τον περισσότερο κόσμο που δεν είναι εξοικειωμένος με το δυναμικό προγραμματισμό. Κι ο λόγος που δημιουργείται μπέρδεμα είναι επειδή ακούγεται τόσο χαζή η προσέγγιση, που όλοι θεωρούν ότι κάτι δεν κατάλαβαν. Κι όμως…

Ας σκεφτούμε λοιπόν ότι το πρόβλημά μας είναι το εξής.

Οπτική αναπαράσταση προβλήματος

Για συντομία, θα ονομάσουμε αυτό το πρόβλημα \((3,20)\). Εννοούμε ότι μας ενδιαφέρουν τα πρώτα \(3\) (δηλαδή όλα!) τα ευθύγραμμα τμήματα, και το ερώτημά μας τελειώνει στο σημείο \(20\). Αντίστοιχα μπορούμε να ορίσουμε το υποπρόβλημα \((2,10)\), όπου μας δίνονται μόνο τα πρώτα \(2\) ευθύγραμμα τμήματα, και το ερώτημά μας τελειώνει στο σημείο \(10\). Λέγοντας δηλαδή \((2,10)\) αναφερόμαστε στο εξής υποπρόβλημα:

Οπτική αναπαράσταση υποπροβλήματος

Ο δυναμικός προγραμματισμός λέει κάτι που αρχικά ακούγεται εντελώς ανόητο. Αντί να λύσουμε απευθείας μόνο το \((3,20)\) (που ήδη δεν ξέρουμε πώς να το λύσουμε), ας λύσουμε όλα τα εξής υποπροβλήματα:

(0,0) (1,0) (2,0) (3,0)
(0,6) (1,6) (2,6) (3,6)
(0,10) (1,10) (2,10) (3,10)
(0,12) (1,12) (2,12) (3,12)
(0,20) (1,20) (2,20) (3,20)

(πατώντας πάνω σε κάθε υποπρόβλημα μπορείτε να δείτε και μία οπτική αναπαράστασή του)

Παρότι αυτό φαίνεται εντελώς χαζό, υπάρχει μια λογική από πίσω. Σκεφτείτε να αναθέσετε σε ένα μαθητή δευτέρας δημοτικού να αθροίσει μία λίστα με \(100\) αριθμούς. Σίγουρα θα τρομάξει και θα φύγει. Αν όμως του πείτε ποιο είναι το άθροισμα των πρώτων \(99\), τότε του μένει μόνο μία πρόσθεση: αυτή του \(100\)ου αριθμού με το άθροισμα των υπόλοιπων \(99\). Η λύση δηλαδή ενός πιο εύκολου σχετικού υποπροβλήματος (αυτό των \(99\) αριθμών) βοήθησε στη λύση του αρχικού προβλήματος.

Ας γυρίσουμε στο δικό μας πρόβλημα, κι ας προσπαθήσουμε να καταλάβουμε πώς λειτουργεί ο δυναμικός προγραμματισμός.

Προσπαθούμε να βρούμε το βέλτιστο κόστος \(\texttt{ans}(i,Y')\) για να καλύψουμε με τα πρώτα \(i\) τμήματα το τμήμα \([q_x,Y']\), για κάθε \(i\le N\) και κάθε \(Y'\in [q_x,q_y]\). Εν τέλει η απάντησή μας θα είναι απλώς το \(\texttt{ans}(N,q_y)\).

Έχουμε το αρχικό μας πρόβλημα, δηλαδή το \((3,20)\).

Οπτική αναπαράσταση προβλήματος

Υποθέτουμε ότι το τελευταίο μας τμήμα (εν προκειμένω το τρίτο) τέμνει το \([0,20]\) (αλλιώς απλώς θα το αγνοούσαμε) και μάλιστα περιλαμβάνει το \(20\) (αλλιώς λόγω της ταξινόμησης κανένα τμήμα δεν θα κάλυπτε το \(20\), κι επομένως δεν θα υπήρχε τρόπος να καλύψουμε το \([0,20]\)). Αν αποφασίσουμε να χρησιμοποιήσουμε αυτό το τμήμα, τότε αρκεί με τα υπόλοιπα \(2\) τμήματα να καλύψουμε ό,τι έχει μείνει ακάλυπτο (δηλαδή το \([0,10]\)). Έτσι πληρώνουμε για το τμήμα που χρησιμοποιήσαμε (κόστος \(6\)), και αρκεί με τα υπόλοιπα \(2\) τμήματα να καλύψουμε το \([0,10]\).

Πώς καλύπτουμε το \([0,10]\) με δύο τμήματα; Λύνοντας το εξής υποπρόβλημα:

Οπτική αναπαράσταση υποπροβλήματος

Υπάρχει βέβαια και η επιλογή να μη χρησιμοποιήσουμε καθόλου το \(3\)ο τμήμα (πχ επειδή είναι πολύ ακριβό) κι έτσι να πρέπει με τα \(2\) τμήματα να καλύψουμε όλο το \([0,20]\). Η μία περίπτωση δηλαδή πληρώνει για το \(3\)ο τμήμα αλλά τουλάχιστον καλύπτει και λίγο από το ερώτημα, ενώ η άλλη δεν πληρώνει αλλά δεν καλύπτει και τίποτα. Επειδή δεν είμαστε σίγουροι ποια είναι η καλύτερη, δοκιμάζουμε και τις δύο. Καταλήγουμε, δεδομένων των υποθέσεων που κάναμε στην αρχή της παραγράφου, ότι

\[\texttt{ans}(N,q_y) = \min\{C_N+\texttt{ans}(N-1,X_N), \texttt{ans}(N-1,q_y)\}\]

και γενικότερα για οποιοδήποτε \(i,Y'\):

\[\texttt{ans}(i,Y') = \min\{C_i+\texttt{ans}(i-1,X_i), \texttt{ans}(i-1,Y')\}\]

Η παραπάνω λύση θα ήταν δραματικά αργή, γιατί το πλήθος των πιθανών \(Y'\) που καλούμαστε να υπολογίσουμε είναι τεράστιο. Όμως προσέξτε ότι τα \(Y'\) που πραγματικά μας ενδιαφέρουν είναι πάντα είτε τα αριστερά άκρα κάποιου τμήματος, είτε το \(q_y\). Επομένως υπάρχουν \(\mathcal{O}(N)\) επιλογές για το \(Y'\), και \(N\) επιλογές για το \(i\). Συμπεραίνουμε ότι υπάρχουν \(\mathcal{O}(N^2)\) πιθανές καταστάσεις του \(\texttt{ans}(i,Y')\) που μας ενδιαφέρουν ανά ερώτημα, και για κάθε μία χρειάζεται να ξοδέψουμε \(\mathcal{O}(1)\) χρόνο. Συνεπώς η πολυπλοκότητα είναι \(\mathcal{O}(MN^2)\).

Ενδεικτικά δίνουμε τους παρακάτω κώδικες για το πρόβλημα. Χρησιμοποιούν ακριβώς την παραπάνω σχέση, και κάνουν τους σχετικούς ελέγχους που αναφέραμε (πχ ότι το \(i\)-οστό τμήμα έχει τομή με το \([q_x,Y']\)). Δίνουμε τόσο την αναδρομική όσο και την επαναληπτική υλοποίηση. Δεν έχουν κάποια αξιοσημείωτη διαφορά στην ταχύτητα, επιλέξτε όποια προτιμάτε. Προσέξτε ότι ο κώδικας είναι ιδιαίτερα όμοιος. Η μόνη ουσιαστική αλλαγή είναι ότι ο κώδικας της αναδρομικής συνάρτησης έχει μπει μέσα στην επανάληψη, με ελάχιστες (τυπικές) αλλαγές.

Βασικές σημειώσεις για τον κώδικα (ισχύουν γενικά για τον δυναμικό προγραμματισμό):

  • Στην αναδρομική υλοποίηση, φροντίζουμε να μην ξαναϋπολογίζουμε πράγματα που ήδη έχουμε υπολογίσει. Απλώς αποθηκεύουμε την απάντησή τους την πρώτη φορά που την υπολογίζουμε, ώστε να την επιστρέψουμε απευθείας όταν μας ξαναζητηθεί.
  • Στην επαναληπτική υλοποίηση, αρκεί να υπολογίζουμε τα υποπροβλήματα με κάποια λογική σειρά. Δηλαδή όταν υπολογίζουμε κάποιο υποπρόβλημα \(\texttt{ans}(i,Y')\), θα πρέπει ήδη να έχουμε υπολογίσει τόσο το \(\texttt{ans}(i-1,Y')\) όσο και το \(\texttt{ans}(i,Y'-1)\). Στα περισσότερα προβλήματα (τουλάχιστον στο \(90\%\) των περιπτώσεων), αυτή η λογική σειρά προκύπτει από μόνη της, χωρίς να χρειάζεται σκέψη. Στο συγκεκριμένο βλέπουμε ότι η επαναληπτική υλοποίηση χρειάζεται μία επιπρόσθετη προεργασία σε σχέση με την αναδρομική, ώστε να ταξινομήσει όλα τα πιθανά \(Y'\).

Μία ακόμα συμβουλή σχετικά με την επιλογή αναδρομικής/επαναληπτικής υλοποίησης: Η αναδρομική υλοποίηση είναι συνήθως πιο απλή (πχ σε αυτή τη λύση δεν χρειαζόταν να ταξινομήσουμε τα πιθανά \(Y'\), η ίδια η αναδρομή φρόντιζε να τα επεξεργαστεί με τη σωστή σειρά). Η επαναληπτική υλοποίηση είναι ελαφρώς πιο δύσκολη, αλλά συνήθως είναι και πιο δεκτική σε βελτιστοποιήσεις (όπως πχ στη λύση 1Γ). Η συμβουλή μας προς τους αρχάριους είναι να γράφουν αρχικά την αναδρομική υλοποίηση. Αν σιγουρευτούν ότι είναι σωστή, τότε αξίζει να ξαναλύσουν το ίδιο πρόβλημα και με την επαναληπτική. Η εξοικείωση και με τις δύο είναι πολύτιμη για τα μετέπειτα βήματα.

Ακολουθεί η υλοποίηση της αναδρομικής λύσης, με κύρια συνάρτηση την \(\texttt{Ans}\).

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const size_t MAXN = 10000;
const long INF = 0x3f3f3f3f;

long N, M, qX, qY, ans[MAXN+2][MAXN+2];
bool computed[MAXN+2][MAXN+2];
struct segment{
  long X, Y, C;
} seg[MAXN+1];

bool comp(segment A, segment B) {
  return A.Y < B.Y;
}

long Ans(long last, long YtIndex) {
  long Yt;
  if (YtIndex!=N+1) Yt = seg[YtIndex].X;
  else Yt = qY;
  
  if (qX >= Yt) return 0; //nothing left to cover
  if (last==0) return INF; //impossible to cover [qX, Yt] without any segments left
  if (!computed[last][YtIndex]) {
    computed[last][YtIndex] = 1;
    if (seg[last].X > Yt) ans[last][YtIndex] = Ans(last-1, YtIndex); //last is irrelevant, ignore it
    else if (seg[last].Y < Yt) ans[last][YtIndex] = INF; //no-one can cover Yt
    else { //Recursive relation
      ans[last][YtIndex] = min( seg[last].C + Ans(last-1, last), Ans(last-1, YtIndex) );
    }
  }
  return ans[last][YtIndex];
}

int main() {
   FILE *fi = fopen("roadfix.in", "r");
   fscanf(fi, "%ld %ld", &N, &M);
   for (long i = 1; i <= N; ++i) {
     fscanf(fi, "%ld %ld %ld", &seg[i].X, &seg[i].Y, &seg[i].C);
     seg[i].Y += seg[i].X; //convert length to right-end-point
   }

   sort(seg+1, seg+N+1, comp);

   FILE *fo = fopen("roadfix.out", "w");
   for(long q = 1; q <= M; ++q) {
     fscanf(fi, "%ld %ld", &qX, &qY);
     qY += qX; //convert length to right-end-point
     if (Ans(N,N+1) < INF) fprintf(fo, "%ld\n", Ans(N,N+1));
     else fprintf(fo, "-1\n");
     memset(computed, 0, sizeof(computed));
   }
   fclose(fi), fclose(fo);
   return 0;
}

Ακολουθεί ο κώδικας για την επαναληπτική υλοποίηση.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const size_t MAXN = 10000;
const long INF = 0x3f3f3f3f;

long N, M, qX, qY, ans[MAXN+1][MAXN+1], order[MAXN+1];
vector< pair<long, long> > begins;
struct segment{
  long X, Y, C;
} seg[MAXN+1];

bool compSeg(segment A, segment B) {
  return A.Y < B.Y;
}

int main() {
   FILE *fi = fopen("roadfix.in", "r");
   fscanf(fi, "%ld %ld", &N, &M);
   for (long i = 1; i <= N; ++i) {
     fscanf(fi, "%ld %ld %ld", &seg[i].X, &seg[i].Y, &seg[i].C);
     seg[i].Y += seg[i].X; //convert length to right-end-point
   }

   sort(seg+1, seg+N+1, compSeg);
   for(long i=1; i<=N; ++i) begins.push_back({seg[i].X, i});
   sort(begins.begin(), begins.end());

   FILE *fo = fopen("roadfix.out", "w");
   long sol;
   for(long q = 1; q <= M; ++q) {
     fscanf(fi, "%ld %ld", &qX, &qY);
     qY += qX; //convert length to right-end-point

     //insert {qY,N+1} in sorted order
     begins.insert( upper_bound( begins.begin(), begins.end(), make_pair(qY,N+1) ), make_pair(qY,N+1) );
     for(long i=0; i<=N; ++i) order[ begins[i].second ] = i;

     for(long YtIndex=0; YtIndex<=N; ++YtIndex) {
       long Yt = begins[YtIndex].first;       
       ans[0][YtIndex] = ((qX >= Yt) ? 0 : INF); //if qX>=Yt there is nothing to cover
	 
       for(long last=1; last<=N; ++last) {       
	 if (qX >= Yt) ans[last][YtIndex] = 0; //nothing left to cover
	 else if (seg[last].X > Yt) ans[last][YtIndex] = ans[last-1][YtIndex]; //last is irrelevant, ignore it
	 else if (seg[last].Y < Yt) ans[last][YtIndex] = INF; //no-one can cover Yt
	 else { //Recursive relation
	   ans[last][YtIndex] = min( seg[last].C + ans[last-1][order[last]], ans[last-1][YtIndex] );
	 }
	 if (Yt == qY) sol = ans[last][YtIndex];
       }
     }
     
     if (sol < INF) fprintf(fo, "%ld\n", sol);
     else fprintf(fo, "-1\n");
     begins.erase( find(begins.begin(), begins.end(), make_pair(qY,N+1) ) );
   }
   
   fclose(fi), fclose(fo);
   return 0;
}

Λύση 1Β - Δυναμικός προγραμματισμός - \(\mathcal{O}(MN^2)\)

Εδώ παρουσιάζουμε μία ακόμα λύση πολυπλοκότητας \(\mathcal{O}(MN^2)\). Ο βασικός λόγος είναι ότι η παρούσα λύση μπορεί να βελτιωθεί περαιτέρω, αρκεί να χρησιμοποιήσουμε κάποιες έξυπνες δομές δεδομένων. Επιπλέον, η εμπειρία μας μας έχει διδάξει ότι άλλοι μαθητές κατανοούν καλύτερα την 1Α κι άλλοι την 1Β, οπότε αποφασίσαμε να παραθέσουμε και τις δύο.

Ας προσπαθήσουμε να κατανοήσουμε γιατί η προηγούμενη λύση είναι αργή. Για κάθε πιθανό τμήμα \(i\), δοκιμάζουμε πολλές διαφορετικές τιμές για το \(Y'\). Θα περίμενε κανείς ότι θα μας ενδιέφερε μόνο η \(Y'=Y_i\), επειδή αν πάρουμε το τμήμα \(i\) τότε θα φτάσουμε ως τη θέση \(Y_i\). Το πρόβλημα είναι ότι ορίσαμε την \(\texttt{ans}(Y',i)\) ως τον βέλτιστο τρόπο να καλύψουμε το \([q_x, Y']\) χρησιμοποιώντας οποιαδήποτε από τα πρώτα \(i\) τμήματα. Επειδή όμως δεν έχουμε την εγγύηση ότι το \(i\)-οστό τμήμα θα χρησιμοποιηθεί απαραίτητα, πρέπει να δοκιμάσουμε και άλλες τιμές του \(Y'\) πέρα από την \(Y_i\).

Για να αποφύγουμε αυτό το πρόβλημα, τώρα θα ορίσουμε \(\texttt{ans'}(i)\) ως το βέλτιστο κόστος να καλύψουμε το \([q_x, Y_i]\) παίρνοντας οπωσδήποτε το \(i\)-οστο τμήμα, και ίσως και κάποια από τα προηγούμενα τμήματα. Έτσι για κάθε \(i\) έχουμε μόνο ένα \(Y'\) που μας ενδιαφέρει (το \(Y_i\), όπως θα περιμέναμε). Αρκεί αυτή η πληροφορία; Αν μαγικά μας δινόντουσαν όλα τα \(\texttt{ans'}(i)\), πώς θα υπολογίζαμε την τελική απάντηση;

Είναι απλό. Η τελική απάντηση σίγουρα θα περιλαμβάνει ένα τμήμα (και μάλιστα μοναδικό) το οποίο καλύπτει το \(q_y\). Αν μαντέψω ποιο είναι αυτό το τμήμα, τότε η \(\texttt{ans'}\) αυτού θα είναι η σωστή απάντηση. Μαντεύουμε απλώς δοκιμάζοντας όλα τα πιθανά τμήματα που καλύπτουν το \(q_y\) και κρατώντας το καλύτερο. Καλό είναι να προσπαθήσετε τουλάχιστον πέντε λεπτά να καταλάβετε γιατί ισχύουν οι ισχυρισμοί αυτής της παραγράφου, πριν προχωρήσετε παρακάτω.

Προσπαθούμε λοιπόν πλέον να υπολογίσουμε όλες τις \(\texttt{ans'}\) τιμές. Ας φανταστούμε ότι θέλουμε να χρησιμοποιήσουμε το \(i\)-οστό τμήμα. Τότε θα καλύψουμε το \([X_i,Y_i]\). Επιτρέπεται με τα υπόλοιπα τμήματα να καλύψουμε ξανά κάτι από το \([X_i,Y_i]\), αλλά δεν είναι απαραίτητο. Αυτό που επιβάλλεται είναι να καλύψουμε το διάστημα \([q_x,X_i]\). Αν μπορούσαμε να μαντέψουμε ακριβώς μέχρι ποιο σημείο \(J\) του (προαιρετικού) διαστήματος \([X_i,Y_i]\) θα καλύψουμε, τότε θα ζητούσαμε μία λύση που καλύπτει το \([q_x,J]\) και τίποτα πέρα από το \(J\). Επειδή δεν μπορούμε να μαντέψουμε το \(J\), δοκιμάζουμε όλες τις πιθανές εκδοχές, και κρατάμε την καλύτερη. Δηλαδή:

\[\texttt{ans'}(i) = C_i + \min_{j: Y_j\ge X_i} \texttt{ans'}(j)\]

Τι κερδίσαμε; Χρειάζεται να υπολογίσουμε \(\mathcal{O}(N)\) αντί για \(\mathcal{O}(N^2)\) καταστάσεις. Τι χάσαμε; Η μαντεψιά για το \(j\) είναι πολύ ακριβή, και παίρνει \(\mathcal{O}(N)\) χρόνο. Εν τέλει η πολυπλοκότητα είναι ακριβώς η ίδια.

Παρακάτω θα δούμε τα θετικά αυτής της λύσης, και συγκεκριμένα ότι μπορεί να βελτιωθεί περαιτέρω. Μπορείτε να βρείτε τον κώδικα για την παρούσα λύση εδώ.

Λύση 2 - Βελτιωμένος δυναμικός προγραμματισμός - \(\mathcal{O}(MN\log{N})\)

Μήπως μπορούμε να βελτιώσουμε τον χρόνο που μας παίρνει η μαντεψιά του \(j\) στην προηγούμενη λύση; Ψάχνουμε το

\[\min_{j: Y_j\ge X_i} \texttt{ans'}(j)\]

Η κρίσιμη (και όχι τόσο προφανής) ιδέα εδώ πέρα είναι η εξής: αν φανταστούμε έναν πίνακα που στη θέση \(Y_j\) περιέχει την τιμή \(\texttt{ans'}(j)\), τότε ζητάμε την ελάχιστη τιμή του πίνακα στο διάστημα που ξεκινάει από το \(X_i\) και εκτείνεται μέχρι το τέλος. Το πρόβλημα αυτό είναι γνωστό: λέγεται Range Minimum Query (RMQ, δείτε εδώ για προτάσεις σχετικά με το πώς λύνεται).

Λύση 2Α - Δυαδικά δέντρα

Χρησιμοποιώντας μια καλή λύση για το RMQ πρόβλημα (πχ με δυαδικά δέντρα) μπορούμε να πάρουμε απάντηση σε \(\mathcal{O}(\log{N})\) χρόνο, αντί για \(\mathcal{O}(N)\).

Καταλήγουμε ότι υπάρχουν \(N\) καταστάσεις να υπολογίσουμε ανά ερώτημα, και για την κάθε μία χρειαζόμαστε \(\mathcal{O}(\log{N})\) χρόνο. Η τελική πολυπλοκότητα είναι \(\mathcal{O}(MN\log{N})\). Μπορείτε να βρείτε τον κώδικα για την παρούσα λύση εδώ. Χάριν απλότητας, υλοποιούμε τα δέντρα με βάθος \(\mathcal{O}(\log{\texttt{MAX\_VALUE}})\) αντί για \(\mathcal{O}(\log{N})\).

Λύση 2Β

Μια άλλη προσέγγιση χρησιμοποιεί Priority Queue with Attrition (στον κόσμο του competitive programming συχνά αυτή η δομή ονομάζεται Monotonic Stack). Ο λόγος που την προτείνουμε είναι ότι μπορεί να βελτιωθεί ακόμα περισσότερο.

Υπενθυμίζουμε ότι θέλουμε να απαντήσουμε σε ερωτήματα της μορφής

\[\min_{j: Y_j\ge X_i} \texttt{ans'}(j)\]

Δηλαδή για κάθε \(X_i\) υπάρχουν κάποια έγκυρα \(j\) (αυτά για τα οποία \(Y_j\ge X_i\)) κι από αυτά τα \(j\) ζητάμε το βέλτιστο \(\texttt{ans'}(j)\). Παρατηρούμε ότι αν έχουμε δύο διαφορετικά \(j,j'\) για τα οποία ισχύει \(Y_j\le Y_{j'}\), τότε δεν υπάρχει κανένα \(X_i\) για το οποίο να είναι έγκυρο το \(j\) αλλά όχι το \(j'\). Υπό αυτή την έννοια, το \(j'\) είναι ισχυρότερο ως προς την \(Y\) συντεταγμένη του.

Επιπλέον, ας φανταστούμε ότι \(\texttt{ans'}(j) \ge \texttt{ans'}(j')\). Τότε το \(j'\) είναι ισχυρότερο και ως προς την \(\texttt{ans'}\). Σε αυτή την περίπτωση, το \(j\) είναι πλέον παντελώς άχρηστο, και μπορούμε να το αγνοήσουμε. Αυτό το σημείο μπορεί να χρειαστεί πέντε λεπτά σκέψης για να κατανοηθεί, δεν έχει νόημα να προχωρήσουμε αν δεν το καταλάβουμε καλά.

Από εδώ και πέρα το σκεπτικό είναι απλό. Κρατούμε σε μια stack (ταξινομημένα) όλα τα \(j\) που δεν είναι άχρηστα. Με τον συμβολισμό \([a,b,c]\) θα εννοούμε ένα στοιχείο που έχει \(j=a, Y_j=b, \texttt{ans'}(j)=c\). Έτσι η stack μας μπορεί κάποια στιγμή να μοιάζει κάπως έτσι.

\[[1, 10, 4], [3, 20, 9], [10, 30, 17]\]

Προσέξτε ότι δεν είναι ταξινομημένα μόνο το \(j\), αλλά και τα \(Y_j\). Αυτό προκύπτει απλά από την ταξινόμηση που κάναμε ως προεργασία. Επιπλέον, και τα \(\texttt{ans'}(j)\) είναι ταξινομημένα. Αν δεν ήταν (πχ το τελευταίο στοιχείο ήταν \([10,30,8]\)) τότε κάποιο προηγούμενο στοιχείο θα ήταν άχρηστο (εν προκειμένω το \([3, 20, 9]\)).

Όταν επεξεργαζόμαστε ένα καινούργιο διάστημα, αρκεί να βρούμε το έγκυρο \(j\) με την μικρότερη \(\texttt{ans'}(j)\). Αφού καταλήξαμε ότι αυτή η stack είναι ταξινομημένη ως προς όλα τα στοιχεία της, στην ουσία αρκεί να βρούμε το αριστερότερο χρήσιμο \(j\) για το οποίο \(Y_j\ge X_i\). Μπορούμε να το εντοπίσουμε με μία δυαδική αναζήτηση σε \(\mathcal{O}(\log{N})\) χρόνο.

Κατόπιν πρέπει να εισάγουμε το καινούργιο μας διάστημα μέσα στη stack, αφού είναι πλέον χρήσιμο, και τα μελλοντικά ερωτήματα πρέπει να είναι ενήμερα για την ύπαρξή του. Το νέο μας διάστημα έχει μεγαλύτερο \(j\) και \(Y_j\) από όλα όσα υπάρχουν στην stack, απλώς λόγω της αρχικής ταξινόμησης. Μπορεί όμως να έχει μικρότερο \(\texttt{ans'}(j)\). Επομένως πρέπει να πετάξουμε έξω από την stack όσα στοιχεία έχουν μεγαλύτερο ή ίσο \(\texttt{ans'}\). Εφόσον η stack είναι ταξινομημένη, όλα αυτά τα στοιχεία βρίσκονται στο τέλος της, και τα πετάμε ένα-ένα (πράγμα που εξηγεί γιατί θέλουμε stack). Η εισαγωγή του νέου διαστήματος διατηρεί την ταξινομημένη φύση της stack, ακριβώς λόγω των διαγραφών που προηγήθηκαν.

Εδώ να τονίσουμε ότι η εισαγωγή ενός διαστήματος μπορεί να χρειαστεί χρόνο \(\Omega(N)\). Όμως κατά μέσο όρο (amortized) ο χρόνος για την κάθε εισαγωγή είναι \(\mathcal{O}(1)\). Ο λόγος είναι ότι ο χρόνος για την εισαγωγή ενός στοιχείου είναι ανάλογος με το πλήθος διαγραφών που θα προκαλέσει. Άρα ο συνολικός χρόνος εισαγωγών είναι ίσος με τον συνολικό χρόνο διαγραφών. Κάθε στοιχείο διαγράφεται το πολύ μία φορά, άρα ο συνολικός χρόνος διαγραφών είναι \(\mathcal{O}(N)\).

Παρακάτω δίνουμε κώδικα για αυτή τη λύση.

#include <cstdio>
#include <algorithm>
using namespace std;

const size_t MAXN = 10000;
const long INF = 0x3f3f3f3f;

long N, M, qX, qY, ans[MAXN+1], nPQA, pqa[MAXN+1];
struct segment{
  long X, Y, C;
} seg[MAXN+1];

bool comp(segment A, segment B) {
  return A.Y < B.Y;
}

int main() {
   FILE *fi = fopen("roadfix.in", "r");
   fscanf(fi, "%ld %ld", &N, &M);
   for (long i = 1; i <= N; ++i) {
     fscanf(fi, "%ld %ld %ld", &seg[i].X, &seg[i].Y, &seg[i].C);
     seg[i].Y += seg[i].X; //convert length to right-end-point
   }

   sort(seg+1, seg+N+1, comp);

   FILE *fo = fopen("roadfix.out", "w");
   long sol;
   for(long q = 1; q <= M; ++q) {
     fscanf(fi, "%ld %ld", &qX, &qY);
     qY += qX; //convert length to right-end-point
     sol = INF;

     nPQA = 0;
     pqa[0] = 0;
     seg[0].Y = 0;
     for(long i=1; i<=N; ++i) {
       //Find best j that finishes after (or exactly at) i's start
       long best = (seg[i].X <= qX && qX <= seg[i].Y ) ? 0 : INF, lo=1, hi=nPQA, mid;
       while (lo<hi) {
	 mid = (lo+hi)/2;
	 if (seg[ pqa[mid] ].Y < seg[i].X) lo=mid+1;
	 else hi=mid;
       }
       if(nPQA>0 && seg[ pqa[hi] ].Y >= seg[i].X) best=min(best, ans[ pqa[hi] ]);

       if (best==INF) { //if no previous segment finishes before i's start
	 if (seg[i].Y <= qX) ans[i] = 0; // [qX,seg[i].Y] is trivially satisfied
	 else if (seg[i].X <= qX) ans[i] = seg[i].C; //i is enough to satisfy it
	 else ans[i] = INF; //i is not enough and no-one else can help
       }
       else ans[i] = seg[i].C + best; //recursive relation

       //Remove elements from the top if they are worse than i, and add i
       while(nPQA && ans[pqa[nPQA]] >= ans[i]) --nPQA;
       pqa[++nPQA] = i;
	 
       if (seg[i].Y >= qY) sol = min(sol, ans[i]);
     }

     if (sol < INF) fprintf(fo, "%ld\n", sol);
     else fprintf(fo, "-1\n");
   }
   fclose(fi), fclose(fo);
   return 0;
}

Λύση 3 - Fusion Trees \(\mathcal{O}(MN\log{N}/\log{\log{N}})\)

Αν χρησιμοποιήσουμε αποδοτικότερες λύσεις για το RMQ πρόβλημα, παίρνουμε καλύτερη συνολική πολυπλοκότητα. Μία τέτοια λύση χρησιμοποιεί Fusion Trees. Στην ουσία τα Fusion Trees είναι παρόμοια με τα κλασικά δυαδικά δέντρα, αλλά έχουν περίπου \(\log{N}\) παιδιά ανά κόμβο. Αυτό που πετυχαίνουν είναι ο χρόνος να γίνεται (θεωρητικά) καλύτερος κατά ένα πολλαπλασιαστικό παράγοντα \(\log{\log{N}}\). Δυστυχώς η κατανόηση της λειτουργίας τους ξεφεύγει από τα όρια των διαγωνισμών, και ο κώδικάς τους είναι πολύ πιο περίπλοκος. Το πιο αστείο είναι ότι στην πράξη ούτε ο χρόνος που δίνουν είναι καλύτερος, γιατί κρύβουν μεγαλύτερους σταθερούς παράγοντες μέσα στο \(\mathcal{O}(\log{N}/\log{\log{N}})\). Επομένως δεν θα δώσουμε κώδικα για αυτή τη λύση.

Γενικά το RMQ δεν μπορεί να λυθεί σε χρόνο καλύτερο από \(\mathcal{O}(\log{N}/\log{\log{N}})\), όταν δεν έχουμε καμμία γνώση για τα επερχόμενα ερωτήματα/ανανεώσεις, και μπορεί να έρθει οποιοδήποτε ερώτημα/ανανέωση. Στη συγκεκριμένη περίπτωση όμως μπορούμε να αξιοποιήσουμε ότι τα επερχόμενα ερωτήματα/ανανεώσεις δεν μας είναι παντελώς άγνωστα, αλλά σχετίζονται με την είσοδο την οποία έχουμε διαβάσει ολόκληρη από την αρχή. Επιπλέον τα ερωτήματα/ανανεώσεις δεν μπορούν να είναι εντελώς αυθαίρετα (πχ στα ερωτήματα που καλούμαστε να λύσουμε εν προκειμένω, το δεξί άκρο είναι πάντα απεριόριστο). Παρότι δεν γνωρίζουμε κάποια τέτοια λύση, δε θα ήταν απίθανο στο συγκεκριμένο πρόβλημα το RMQ να μπορεί να υλοποιηθεί και σε \(\mathcal{O}(1)\) χρόνο, και να παίρναμε συνολική πολυπλοκότητα \(\mathcal{O}(MN)\).

Δεδομένου ότι δεν γνωρίζουμε τέτοια λύση πολυπλοκότητας \(\mathcal{O}(MN)\), δίνουμε το πλησιέστερο που γνωρίζουμε: μια λύση πολυπλοκότητας \(\mathcal{O}(MN\alpha(N))\).

Λύση 4 - Βελτίωση της 2B \(\mathcal{O}(N\log{N}+MN\alpha(N))\)

Σημειώνουμε ότι \(\alpha(N)\) είναι η αντίστροφη Ackermann συνάρτηση. Για όποιον δεν την γνωρίζει, προκύπτει απ’ την δομή δεδομένων Union-Find και είναι δραματικά μικρή (πολύυυυ μικρότερη από τον λογάριθμο). Ενδεικτικά να πούμε ότι αν το \(N\) είναι ίσο με το πλήθος ατόμων στο σύμπαν, τότε η \(\alpha(N)\) είναι ακριβώς \(4\). Εφόσον ο χρόνος απάντησης στα ερωτήματα είναι πλέον τόσο αποδοτικός, γίνεται μη-συγκρίσιμος με το χρόνο προεργασίας (ταξινόμηση). Για αυτό αναφέρουμε και τους δύο χρόνους στην πολυπλοκότητα.

Πώς βελτιώνουμε την λύση 2Β λοιπόν; Θυμίζουμε ότι διατηρούσαμε μια Priority Queue with Attrition (κατά τους competitive programmers: Monotonic Stack). Συνεχίζουμε να διατηρούμε αυτή τη δομή με τον ίδιο ακριβώς τρόπο. Επιπλέον, ρωτούσαμε ερωτήματα σχετικά με τον successor των \(X_i\) μέσα στη δομή μας (δηλαδή το πρώτο στοιχείο που είναι μεγαλύτερο ή ίσο). Εδώ πέρα έμπαινε ο λογάριθμος, επειδή κάναμε δυαδική αναζήτηση.

Αντί για δυαδική αναζήτηση, τώρα θα κάνουμε το εξής. Κάθε στοιχείο της δομής μας θα κρατάει και μία λίστα αριθμών, τα ενεργά \(X_i\) των οποίον αυτό το στοιχείο είναι προς το παρόν ο successor. Επομένως όταν επεξεργάζομαι ένα δεξί άκρο, αρκεί να βρω (Find) σε ποια λίστα ανήκει το αντίστοιχο αριστερό άκρο.

Πώς ανανεώνουμε την δομή μας όταν προσθέτουμε ένα στοιχείο; Αν το νέο στοιχείο διώξει κάποιο παλιό στοιχείο της δομής, τότε θα τσιμπήσει και την λίστα του. Γίνεται δηλαδή ο νέος successor όσων είχαν successor το (άχρηστο πλέον) παλιό στοιχείο. Επομένως χρειάζεται να συγχωνεύουμε (Union) λίστες.

Καταλήγουμε ότι το μόνο που ζητάμε από αυτές τις λίστες είναι να υποστηρίζουν Union-Find. Χρησιμοποιώντας την κλασική Union-Find δομή δεδομένων (πολυπλοκότητας \(\mathcal{O}(\alpha(N))\) ανά ερώτημα/ανανέωση), παίρνουμε τον ζητούμενο χρόνο.

Παρακάτω δίνεται κώδικας για αυτή τη λύση:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const size_t MAXN = 10000;
const long INF = 0x3f3f3f3f;

long N, M, qX, qY, ans[2*MAXN+1], nPQA, pqa[MAXN+1], root[2*MAXN+1], par[2*MAXN+1], r[2*MAXN+1];

struct segment{
  long X, Y, C;
} seg[MAXN+1];

struct event{
  bool type;
  long id;
} events[2*MAXN+1];

long getCoord(event A) {
  return A.type ? seg[ A.id ].Y : seg[ A.id ].X;
}

bool compEv(event A, event B) {
  if (getCoord(A) != getCoord(B)) return getCoord(A) < getCoord(B);
  return A.type < B.type;
}

long Find(long u) {
  if (u!=par[u]) par[u] = Find(par[u]);
  return par[u];
}

void Union(long u, long v) {
  u = Find(u);
  v = Find(v);
  if(r[u] > r[v]) swap(u,v);
  if(r[u] == r[v]) ++r[u];
  par[v] = u;
}

int main() {
   FILE *fi = fopen("roadfix.in", "r");
   fscanf(fi, "%ld %ld", &N, &M);
   for (long i = 1; i <= N; ++i) {
     fscanf(fi, "%ld %ld %ld", &seg[i].X, &seg[i].Y, &seg[i].C);
     seg[i].Y += seg[i].X; //convert length to right-end-point     
     events[i].type = 0, events[i].id=i;
     events[i+N].type = 1, events[i+N].id=i;
   }

   sort(events+1, events+2*N+1, compEv);

   FILE *fo = fopen("roadfix.out", "w");
   long sol, start;
   for(long q = 1; q <= M; ++q) {
     fscanf(fi, "%ld %ld", &qX, &qY);
     qY += qX; //convert length to right-end-point
     sol = INF;
     memset(r, 0, sizeof(r));
     memset(root, 0, sizeof(root));

     nPQA = 0;
     pqa[0] = 0;
     start = 1;
     for(long i=1; i<=2*N; ++i) {
       if (events[i].type==0) {
	 if (events[i-1].type==1) start = i;
	 par[ events[i].id ] = events[i].id;
	 continue;
       }

       //else: we have the right endpoint of an interval
       //first we find the successor of its starting point
       long evPos = Find(events[i].id);
       long successor = root[evPos];
       long best = (seg[ events[i].id ].X <= qX) ? 0 : INF;
       if(seg[ events[successor].id ].Y >= seg[ events[i].id ].X) best=min(best, ans[ successor ]);       

       //then we use it to compute ans[i] using the recursive relation
       if (best==INF) { //if no previous segment finishes before i's start
	 if (seg[events[i].id].Y <= qX) ans[i] = 0; // [qX,seg[i].Y] is trivially satisfied
	 else if (seg[events[i].id].X <= qX) ans[i] = seg[events[i].id].C; //i is enough to satisfy it
	 else ans[i] = INF; //i is not enough and no-one else can help
       }
       else ans[i] = seg[events[i].id].C + best; //recursive relation
       if (seg[events[i].id].Y >= qY) sol = min(sol, ans[i]);

       //now we update our structure using ans[i]
       //let everything from start till i-1 know that its successor is i
       par[ events[i].id+N ] = events[i].id+N;
       root[ events[i].id+N ] = i;
       if (events[start].type==0) {
	 for(long j=start; j<i; ++j) {
	   root[Find(events[j].id)] = i;
	   Union( events[j].id, events[i].id+N);
	 }
       }
       start = i;
       //Remove elements from the top if they are worse than i, and add i
       //if an element A was the successor of an element B and A is removed, then B has i as the new successor
       while(nPQA && ans[pqa[nPQA]] >= ans[i]) {
	 root[Find(events[pqa[nPQA]].id+N)] = i;
	 Union(events[ pqa[nPQA] ].id+N, events[i].id+N);
	 --nPQA;
       }
       pqa[++nPQA] = i;
     }

     if (sol < INF) fprintf(fo, "%ld\n", sol);
     else fprintf(fo, "-1\n");
   }
   fclose(fi), fclose(fo);
   return 0;
}

Ανοιχτό ερώτημα - Υπάρχει καλύτερη λύση;

Μπορούμε να απαντήσουμε ακόμα πιο γρήγορα σε αυτά τα RMQ ερωτήματα; Ώστε να πάρουμε μια πολυπλοκότητα της τάξης του \(\mathcal{O}(N\log{N} + MN)\);

Επιπλέον, ίσως να υπάρχουν και ακόμα καλύτερες λύσεις, που να ακολουθούν εντελώς διαφορετική προσέγγιση. Το πιο ενδιαφέρον θα ήταν να καταφέρναμε με κάποια προεργασία να λύσουμε το πρόβλημα σε χρόνο ταχύτερο από γραμμικό ανά ερώτημα, πχ σε συνολικό χρόνο \(\mathcal{O}(N\log{N}+M\log{N})\).