Editorial for CCC '21 S4 - Daily Commute
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Every possible path is a prefix of the permutation of integers , so trying all permutations each day suffices.
Time Complexity:
Subtask 2
If a DFS algorithm is used to compute the shortest distance from to
on each day, we can prove that the algorithm has a complexity of
per day.
The DFS implementation being discussed is something similar to the following (though more code is needed to account for the subway).
vector<int> g[200005];
int dist[200005];
void dfs(int u) {
int d = dist[u] + 1;
for (int v: g[u]) {
if (dist[v] > d) {
dist[v] = d;
dfs(v);
}
}
}
// DFS call. Run once per day
memset(dist, 0x3f, sizeof dist); // set all distances to "infinity" value
dist[n] = 0;
dfs(n);
Code credit:
We can prove this by considering the amount of times DFS is called for each node in the graph. From the implementation, it's evident that dfs
is called every time the shortest distance to a node "improves", and as the shortest distance to a node in the graph is bounded by , its distance can improve at most
times. This means that
dfs
will be called at most times for each node and each edge will be checked at most
times.
Time Complexity:
Subtask 3
For each day, run a weighted SSSP algorithm such as Dijkstra's. Note that the subway has to be treated differently from the walkways as waiting for the subway needs to be accounted for.
Time Complexity:
Subtask 4
We can prove that an optimal answer always exists with the following constraints:
- Take some prefix of the subway
- Exit the subway and walk to node
using exclusively walkways
Assume that the only optimal trips do not respect the above constraints. Let be the node where we leave the subway for the final time on the trip. If we simply take the subway from
to
instead and then take walkways from
to
, it will be at least as good as the optimal trip, because the subway always arrives at
at the same time no matter what path we take.
Thus, on each day, we simply have to check these candidate solutions for an optimal answer. And as only two stations will change positions each day, we just need a data structure that supports efficient point updates and minimum queries to maintain the solution. Examples include
std::multiset
in C++, TreeSet
in Java, and the heapq
package in Python (a bit more effort is needed for a priority queue to work though).
Time Complexity:
Comments
recursive dfs faced TLE :(
I tried BFS here, but I'm getting TLE on batch 4. I think I have to also store the steps it took to reach a station to speed up my solution?
Look at your time complexity. Looks something like
.
Is my approach in the right direction though? Or do I have to use another algorithm?
Try to find a method that doesn't perform a complete search of the graph each query, such as the editorial above.
I tried something similar to that, but I started from
and went to
. I passed #4 but I got TLE on #5: https://dmoj.ca/submission/3633167
Do I have to start at
and go to
?
Changes in trains can be treated as qurries. Instead of computing them again and again(in ur case the BFS) for each qurry(change), you should avoid doing repetitive work.
I'm not sure how to treat the trains as queries though in my current solution?
see the editorial above.
Would BFS work as well?
Yes, BFS works too