C - Camels and Bridge Editorial by evima


The collapse of the bridge is unavoidable only if \(\max(w) > \min(v)\). From now on, we assume \(\max(w) \leq \min(v)\).

Let us consider the case in which the camels must be in the order Camel \(1\), \(2\), \(\ldots\), \(N\). Then, we will have \(N(N-1)/2\) restrictions in this form: for \(i\) and \(j\) such that \(1 \leq i < j \leq N\), the distance between Camel \(i\) and \(j\) must be at least \(x_{i,j}\). \(x_{i,j}\) can be found in \(O(\log M)\) after precomputation. Here, the answer (for the fixed order of camels) corresponds to the length of the longest path from Vertex \(1\) \(N\) in the graph where there are directed edges of length \(x_{i,j}\) from Vertex \(i\) to \(j\). This graph does not have cycles, so we can find the length of the longest path in \(O(N^2)\) with dynamic programming.

We can try all possible orders of camels and find the length of the longest path in each case to find the final answer. This can be done in \(O(N! N^2 \log M)\) time, which is fast enough.

posted:
last update: