100 - Lumber Jack and Grammar
Python 3
1 print(input().replace('-', '').replace(',', ' ,').replace('.', ''))
300 - Lumber Jack and Sick Leaves
Solution by Inelus Gabriel Robert
There are solutions of varied complexities. An O(N2) algorithm will build a graph and do a Breadth-First Search.
The O(N) solution uses a dynamic programming approach. Let dp[i] = the least number of sick leaves needed for days i, i+1, …, D, D+1.
Initialisation
- dp[i] = infinity, ∀ i ∈ [1, D]
- dp[D+1] = 0
Recurrence relation
- dp[i] = min(dp[i], dp[i+1]), provided that Lumber Jack did not skip the ith day.
- dp[i] = min(dp[i], dp[next] + 1), provided that we have a sick leave on interval [i, next).
The dp[] table can be computed from high indices to low.
Hence, we can build a graph with an edge (i) → (next+1) in linear time using linked lists (or STL vectors) and then apply the above recurrence relation.
The final complexity is O(N) both time and space.
Note that given the low score of the problem, we accept slightly worse complexity solutions, however exponential complexities are not acceptable.
1000 - Lumber Jack and Cycles
Solution by Gabriel-Robert Inelus
We have to make a couple important trivial notes which count towards solving the problem:
- any cycle lies entirely inside a strongly connected component;
- given a strongly connected component, we can detect whether it contains a negative cycle using the Bellman-Ford algorithm.
Hence, we can solve the problem by following the steps:
- decompose the graph into strongly connected components and build the SCC graph the same time (for example using the Kosaraju-Sharir algorithm)
- apply the Bellman-Ford shortest path algorithm on each SCC and keep track of the components which have a negative cycle
- having the DAG of the SCC's, we can run a modified topological sort using a queue. Instead of the classic algorithm (pushing into the queue all the nodes with OUT degree 0 and removing them along with any edge that is incident to them and then repeating the process while possible), we add the condition that we push into the queue only the nodes which represent a strongly connected component (nodes of SCC Graph) that have no negative cycles inside.
The worst case time complexity is:
- O(N+M) - SCC
- O(N*M) - Bellman-Ford
- O(N+M) - the modified topological sort.
Thus, the final complexity is O(N*M) due to Bellman-Ford. However, we all know that Bellman-Ford is a probabilistic algorithm; Hence, in general, it performs better than O(N * log N).
I leave as homework to the curious reader the following claims:
By using the fact that Bellman-Ford (probabilistic algorithm) usually runs faster then Dijkstra's algorithm, I claim that if there are no negative cycles in a strongly connected component of size S, each node will be pushed into the queue at most log S times. This imposes the expected O(S * log S) time complexity.
We can pick a constant c, such that log |maxS| < c = 60 and claim with a very high success rate that if a node is pushed into the queue for more than 60 times, then it is a member of a negative cycle. Even though this runs fast (less than half a second per testcase on an average computer for 105 vertices and 2.5 * 105 edges), this solution is non-deterministic and may fail on a smart particular test. The success rate increases as the constant gets larger and hits certainty when c = S, considering that a node that is pushed into the queue S times must be a member of a negative cycle.
