Trains

Author: cfalas

Problem

Το πρόβλημα μας δίνει ένα γράφο, στον οποίο πρέπει να βρούμε το shortest path από τον κόμβο \(1\) στον κόμβο \(N\).

Το δύσκολο κομμάτι, όμως είναι το ότι ο γράφος δεν έχει απλές ακμές από τον κόμβο \(u\) στον κόμβο \(v\) όπως σε "κανονικούς" γράφους. Αντί αυτού, o κάθε κόμβος στο εύρος \([Ls_i, Rs_i]\) είναι ενωμένος με κάθε κόμβο στο εύρος \([Lf_i, Rf_i]\).

Solution

Subtask 1 (15 points)

\(Ls_i=Rs_i\), \(Lf_i=Rf_i\)
\(1 \leq N, M \leq 10000\)

Αφού \(Ls_i=Rs_i\) και \(Lf_i=Rf_i\), η κάθε γραμμή του τραίνου πάει από ένα σταθμό σε έναν άλλο. Δηλαδή, το σιδηροδρομικό σύστημα μπορεί να αντιπροσωπευθεί από έναν γράφο, όπου ο κάθε σταθμός είναι ένας κόμβος, και η κάθε γραμμή είναι μια ακμή στον γράφο.

Αφού δημιουργήσουμε τον γράφο, μπορούμε να βρούμε το συντομότερο μονοπάτι χρησιμοποιώντας τον αλγόριθμο του Dijkstra, με συνολική χρονική πολυπλοκότητα \(O(N+M\log N)\)

Subtask 2 (18 points)

\(1 \leq N, M \leq 500\)

Στο δεύτερο subtask, δεν έχουμε τον ίδιο περιορισμό που μας επέτρεψε στο πρώτο subtask να χρησιμοποιήσουμε ο σιδηροδρομικό δίκτυο ως γράφο.

Σε αυτό το subtask, το \(N\) και το \(M\) είναι αρκετά μικρά όμως, το οποίο μας επιτρέπει να δημιουργήσουμε ένα γράφο που να μπορεί να χρησιμοποιηθεί με τον ίδιο τρόπο όμως. Η εκφώνηση μας περιγράφει πως η κάθε γραμμή ενώνει όλους τους κόμβους στο εύρος \([Ls_i, Rs_i]\), με όλους τους κόμβους στο εύρος \([Lf_i, Rf_i]\).

Δηλαδή, ο κόμβος \(Ls_i\) είναι ενωμένος με όλους τους κόμβους \({Lf_i, Lf_i+1, Lf_i+2, \ldots, Rf_i-1, Rf_i}\). Παρομοίως, ο κόμβος \(Ls_i+1\) είναι ενωμένος (με διαφορετικό βάρος) στους κόμβους \({Lf_i, Lf_i+1, Lf_i+2, \ldots, Rf_i-1, Rf_i}\).

Παράδειγμα

Για παράδειγμα, για την γραμμή 1 3 7 9 8 που εμφανίζεται στο παράδειγμα στην εκφώνηση, θα προσθέσουμε τις ακόλουθες ακμές:

graph LR
    g1[1 2 3] -->|8| g2[7 8 9]


graph TD
    1 -->|10| 7
    1 -->|11| 8
    1 -->|12| 9
    2 -->|9| 7
    2 -->|10| 8
    2 -->|11| 9
    3 -->|8| 7
    3 -->|9| 8
    3 -->|10| 9

Μπορούμε να δημιουργήσουμε ξεχωριστά την κάθε ακμή στον γράφο μας για κάθε γραμμή στον σιδηροδρομικό σταθμό. Στην χειρότερη περίπτωση, θα υπάρχουν \(\frac{N}{2} \cdot \frac{N}{2}\) ακμές για κάθε γραμμή, δηλαδή θα έχουμε συνολικά \(Ο(MN^2)\) ακμές, και έτσι η συνολική πολυπλοκότητα μας θα είναι \(O(NM^2\log N)\).

Subtask 3 (27 points)

Για το 3ο subtask, υπάρχουν 2 ξεχωριστές λύσεις. Θα χρειαστούμε κομμάτι και από τις 2 για το επόμενο subtask.

Solution 1

Το πρόβλημα με την προηγούμενη μας λύση είναι ότι είναι αργή, λόγω του ότι έχει πολλές ακμές. Θα ήταν καλό, αν μπορούσαμε μα κάποιο τρόπο να "ανταλλάξουμε" κάποιες ακμές για κόμβους, αφού ο αριθμός τον κόμβων έχουν μόνο λογαριθμικό κόστος στην πολυπλοκότητα μας.

Για να το κάνουμε αυτό, μπορούμε να "μαζέψουμε" όλες τις outgoing ακμές, και να τις ενώσουμε μαζικά στις incoming ακμές. Δηλαδή, για κάθε ακμή θα δημιουργήσουμε δύο νέους κόμβους, τους οποίους θα ονομάσουμε \(u_i\) και \(v_i\). Θα ενώσουμε όλους τους κόμβους στο εύρος \([Ls_i, Rs_i]\) με τον \(u_i\), και τον \(v_i\) με όλους τους κόμβους στο εύρος \([Lf_i, Rf_i]\).

Παράδειγμα

Για παράδειγμα, για την γραμμή 1 3 7 9 8 που εμφανίζεται στο παράδειγμα στην εκφώνηση, θα έχουμε τον ακόλουθο γράφο:

graph LR
    g1[1 2 3] -->|8| g2[7 8 9]


graph LR
    1 -->|2| u
    2 -->|1| u
    3 -->|0| u

    u -->|8| v

    v -->|0| 7
    v -->|1| 8
    v -->|2| 9

Σημείωση

Σημειώστε τι πρέπει να γίνει με το βάρος της κάθε ακμής. Το βάρος της ακμής \(u_i \rightarrow v_i\) θα έχει βάρος \(C_i\), ενώ οι ακμές \(x \rightarrow u_i\) θα έχουν διαφορετικό βάρος για κάθε ακμή, όπως φαίνεται στο παράδειγμα πιο πάνω (ξεκινώντας από το 0 και να αυξάνονται για κάθε κόμβο πιο μακριά από το \(Rs_i\) ή το \(Lf_i\).

Είναι αρκετά γρήγορο αυτό; Με αυτή την λύση, θα έχουμε \(V=N+2M = O(N+M)\) κόμβους στον γράφο μας, και \(E=M(2 \cdot \frac{N}{2}) = O(NM)\). Δηλαδή, ο αλγόριθμος του Dijkstra θα τρέχει σε \(O(NM\log(N+M))\), το οποίο είναι αρκετό για το συγκεκριμένο subtask.

Solution 2

Όπως και στην προηγούμενη λύση, θα προσπαθήσουμε να "ανταλλάξουμε" ακμές για κόμβους, για να μειώσουμε την συνολική μας πολυπλοκότητα.

Για να το πετύχουμε αυτό, θα πρέπει να θυμηθούμε κάτι που είναι αρκετά απλό, αλλά πολλές φορές δύσκολο να το σκεφτούμε: το γεγονός ότι \(N = \sqrt{N} \times \sqrt{N}\). Μπορούμε να χρησιμοποιήσουμε την τεχνική του square root decomposition για να πετύχουμε καλύτερη πολυπλοκότητα.

Συγκεκριμένα, θα χωρίσουμε τους κόμβους μας σε ομάδες μεγέθους \(\sqrt{N}\). Για κάθε ομάδα, θα δημιουργήσουμε 2 νέους κόμβους, τον \(S_i\) και τον \(T_i\). Ο κάθε κόμβος ανήκει ακριβώς σε κάθε ομάδα, και για κάθε κόμβο \(K\) που ανήκει στην \(i\)-οστή ομάδα, θα προσθέσουμε 2 ακμές: μια από τον κόμβο \(K\) στον κόμβο \(S_i\) και μία από τον κόμβο \(T_i\) στον κόμβο \(K\).

Παράδειγμα

Για παράδειγμα, για έναν γράφο με 9 κόμβους, θα έχουμε τον ακόλουθο γράφο πριν να προσθέσουμε οποιαδήποτε γραμμή:


graph TD
    1 -->|2| S1
    2 -->|1| S1
    3 -->|0| S1

    4 -->|2| S2
    5 -->|1| S2
    6 -->|0| S2

    7 -->|2| S3
    8 -->|1| S3
    9 -->|0| S3

    T1 -->|0| 1
    T1 -->|1| 2
    T1 -->|2| 3

    T2 -->|0| 4
    T2 -->|1| 5
    T2 -->|2| 6

    T3 -->|0| 7
    T3 -->|1| 8
    T3 -->|2| 9

Αν θέλουμε να προσθέσουμε την γραμμή 2 7 8 9 5, θα προσθέσουμε τις ακόλουθες ακμές στον γράφο μας:

graph LR
    g1[2 3 4 5 6 7] -->|5| g2[8 9]

Με αυτό τον τρόπο, το κάθε εύρος σταθμών θα αντιπροσωπεύεται από το πολύ \(O(\sqrt{N})\) κόμβους και ακμές. Συνεχίζουμε όμως να πρέπει να ενώσουμε τους κόμβους του outgoing εύρους με τους κόμβους του incoming σταθμού. Άρα συνολικά, θα έχουμε \(V=N+2\sqrt{N} = O(N)\) κόμβους και \(E=M \cdot \sqrt{N} \cdot \sqrt{N/2}=O(NM)\) ακμές. Έτσι, η συνολική μας πολυπλοκότητα κατέβηκε στο \(O(NM\log N)\)

Subtask 4 (24 points)

Για να λύσουμε το 4ο subtask, πρέπει να συνδυάσουμε τις ιδέες από τις 2 λύσεις που αναφέραμε στο subtask 3. Δηλαδή, θα πρέπει να χωρίσουμε τους κόμβους σε ομάδες, και για κάθε γραμμή, θα πρέπει να δημιουργούμε κόμβους, οι οποίοι θα ενώνουν \(O(\sqrt{N})\) κόμβους ο κάθε ένας.

Έτσι, συνολικά θα έχουμε \(V=N+2M+2\sqrt{N} = O(N+M)\) κόμβους, και \(E=6Msqrt{N}=O(M\sqrt{N})\). Άρα η συνολική πολυπλοκότητα είναι \(O(M\sqrt{N}\log (N+M))\)

Subtask 5 (16 points)

Για τους τελευταίους πόντους του προβλήματος, χρειάζεται να επεκτείνουμε το square root decomposition σε κάτι ακόμη πιο γρήγορο. Το μέγεθος του \(N\) μας παροτρείνει να ψάξουμε για κάτι λογαριθμικό, αλλά μπορούμε να χρησιμοποιήσουμε παρόμοιες ιδέες με το square root decomposition.

Το square root decomposition που χρησιμοποιήσαμε στο προηγούμενο subtask είναι μια τεχνική που συνήθως χρησιμοποιείται για προβλήματα με range queries. Μήπως μπορούμε να χρησιμοποιήσουμε και άλλες τεχνικές που χρησιμοποιούμε για range queries (π.χ. τα segment trees);

Μπορούμε να δημιουργήσουμε 2 segment trees, ένα από τους κόμβους προς τα έξω, και ακόμη ένα προς τους κόμβους, όπως πιο κάτω:

graph

Οι κόμβοι στην μέση του γράφου είναι οι σταθμοί του τρένου, με τον σταθμό 1 στα αριστερά και τον σταθμό \(N\) στα δεξιά. Για να αντιπροσωπέυσουμε ένα εύρος από σταθμούς, χρειαζόμαστε το πολύ \(O(\log N)\) ξεχωριστούς κόμβους, για τους ίδιους λόγους που ισχύει η συγκεκριμένη ιδιότητα στα segment trees.

Με αυτό τον γράφο, έχουμε συνολικά \(V=O(N+M)\) κόμβους και \(Ε=Ο(N+M\log N)\) ακμές, άρα η συνολική πολυπλοκότητα είναι \(O((N+M\log N)\log(N+M)) = O((N+M)\log^2 (N+M))\)