Editorial for GlobeX Cup '18 S4 - Reversed Dijkstra's

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

For the first subtask, note that $M=N-1$ $M = N - 1$ . This means that the graph is a tree, meaning that there is only one path from $A$ $A$ to $B$ $B$ . Thus we can just run a BFS or DFS from $A$ $A$ to $B$ $B$ , with the answer being $|V-d|$ $| V - d |$ .

Time Complexity: $\mathcal O(N)$ $O (N)$

For the second subtask, it suffices to simply check every possible path in the graph from $A$ $A$ to $B$ $B$ and then get the smallest $|V-d|$ $| V - d |$ of all those paths. One method of doing this is a DFS traversal of every path in the graph starting from $A$ $A$ .

Note that due to the number of edges ( $M=N-1$ $M = N - 1$ ) in the first subtask, this approach also works for it.

Time Complexity: $\mathcal O(N!)$ $O (N!)$

For the final subtask, note that we can use a visited array to skip redundant paths. Two paths from $A$ $A$ to a vertex $v$ $v$ are redundant if they both have visited the same nodes. The implementation is left as an exercise to the reader.

We can prove this by looking at any two paths from $A$ $A$ to any vertex $v$ $v$ that has visited the same vertices. We can make two observations about these paths.

Both paths have the same length, since it's not allowed to backtrack and they visited the same [amount of] vertices.
The vertices that both paths can visit from $v$ $v$ onward are the same, since they have already visited the same vertices and the paths cannot backtrack.

These observations show that both paths are functionally the same and thus it would be redundant to search onward from any more than one of the paths.

Time Complexity: $\mathcal O(N \cdot 2^N)$ $O (N \cdot 2^{N})$

Author's note: Note that this problem is extremely similar to CCO '15 P2 - Artskjid, hence the [very original] problem name.

Comments

-15

Plasmatic commented on Dec. 21, 2018, 2:53 a.m.

This was part of the original editorial xd

I got scammed so ******* hard

Are you kidding me

@Plasmatic#2741

~ Ninjaclasher attempting to systest my S4 solution

This comment is hidden due to too much negative feedback. Show it anyway.