Editorial for CCC '21 S4 - Daily Commute - Olympiads Online Judge

Editorial for CCC '21 S4 - Daily Commute

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

Every possible path is a prefix of the permutation of integers $1, 2, \dots, N$ ~1, 2, \dots, N~, so trying all permutations each day suffices.

Time Complexity: $\mathcal{O}(DN!)$ ~\mathcal{O}(DN!)~

Subtask 2

If a DFS algorithm is used to compute the shortest distance from $1$ ~1~ to $N$ ~N~ on each day, we can prove that the algorithm has a complexity of $\mathcal{O}(N(N+M))$ ~\mathcal{O}(N(N+M))~ 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: d

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 $N$ ~N~, its distance can improve at most $N$ ~N~ times. This means that dfs will be called at most $N$ ~N~ times for each node and each edge will be checked at most $N$ ~N~ times.

Time Complexity: $\mathcal{O}(DN(N+M))$ ~\mathcal{O}(DN(N+M))~

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: $\mathcal{O}(D (M+N) \log N)$ ~\mathcal{O}(D (M+N) \log N)~

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 $N$ ~N~ using exclusively walkways

Assume that the only optimal trips do not respect the above constraints. Let $d$ ~d~ be the node where we leave the subway for the final time on the trip. If we simply take the subway from $1$ ~1~ to $d$ ~d~ instead and then take walkways from $d$ ~d~ to $N$ ~N~, it will be at least as good as the optimal trip, because the subway always arrives at $d$ ~d~ at the same time no matter what path we take.

Thus, on each day, we simply have to check these $N$ ~N~ 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: $\mathcal{O}(D \log N + M + N)$ ~\mathcal{O}(D \log N + M + N)~

Comments

0

c_zqz commented on May 17, 2021, 1:05 a.m.

recursive dfs faced TLE :(

0

DynamicSquid commented on May 16, 2021, 8:37 p.m.

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?

3

dxke02 commented on May 16, 2021, 8:46 p.m.

Look at your time complexity. Looks something like $\mathcal{O}(DN^2)$ ~\mathcal{O}(DN^2)~.

0

DynamicSquid commented on May 17, 2021, 5:24 p.m.

Is my approach in the right direction though? Or do I have to use another algorithm?

2

Plasmatic commented on May 17, 2021, 11:40 p.m. ← edited →

Try to find a method that doesn't perform a complete search of the graph each query, such as the editorial above.

0

DynamicSquid commented on May 19, 2021, 2:39 a.m. ← edited →

I tried something similar to that, but I started from $N$ ~N~ and went to $1$ ~1~. I passed #4 but I got TLE on #5: https://dmoj.ca/submission/3633167

Do I have to start at $1$ ~1~ and go to $N$ ~N~?

0

c_zqz commented on May 19, 2021, 8:40 a.m.

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.

0

DynamicSquid commented on May 19, 2021, 4:27 p.m.

I'm not sure how to treat the trains as queries though in my current solution?

0

c_zqz commented on May 19, 2021, 8:40 p.m.

see the editorial above.

2

DynamicSquid commented on May 9, 2021, 6:02 p.m.

Would BFS work as well?

3

vishnus commented on May 9, 2021, 8:21 p.m.

Yes, BFS works too