Competitive Programming Editorials

  Problem Link Time Complexity: O(N + M log M) Algorithm used: Dijkstra, DP (partly) The problem statement is quite straightforward: a series of M one-way flight routes are described, each connecting one city to another city and having a cost. You want to travel from city 1 to city N. Find: minimum price of such a route the number of minimum-price routes maximum number of flights in a minimum-price route minimum number of flights in a maximum-price route It is guaranteed that at least 1 path exists from city 1 to city N This can be modelled as a graph problem, where the cities are the nodes and the flights are the edges. Each flight has a cost and only travels in one direction, so the graph is weighted and directed. A minimum price route to node N means the shortest path to node N. Since the route must start from city 1 and the edges are weighted, some form of Dijkstra's algorithm must be applied. The key point is to collect the data for the 4 answers while running the Dijkstra...

  Problem Link Time Complexity: O(N log N + M log N) Algorithm Used: Dynamic Range Maximum Queries, Segment Tree In this problem, a list of hotels is given, each having Hᵢ rooms. Then a list of people are given, each wanting Pᵢ rooms. Then people must be processed in the order given and for each group, the first available hotel must be assigned. Then the number of rooms available in that hotel decreases by the number of rooms taken. This problem uses Dynamic Range Maximum Queries. A segment tree can be used for this purpose. For each group of people, we walk down the segment tree, starting from the top node. Each node in the tree will have 2 children except for the leaves. We check both the children and choose the first of the two children (the first hotel) which has at least the number of rooms required by the group. This continues until a leaf is found.  If neither of the children have enough rooms for the group, then none of the hotels will have enough rooms, so the program...

  Problem Link Tags: BFS Time Complexity: O(N²) In this problem, an undirected unweighted graph is given, and we are asked to find the length of the shortest cycle, if any. Since the graph edges are unweighted, BFS can be used to find the shortest path from the starting node to all other nodes. But, we do not know which nodes are part of the cycle, so where do we start the BFS? Since N ≤ 2500, we can run BFS from every node and keep track of the shortest cycle length. For each BFS-run, we keep track of the number of edges traversed (aka distance) to reach the current node from the starting node. If we visit a node that has already been visited, then it means the shortest cycle that includes the starting node has been found. Let's call this node y and call the node which visited node y for a second time,  x . To find the length of this cycle, simply add the distance travelled by the x , to the distance travelled by node y and one to include the edge between x and y . The ans...

Problem Link (Click here) Tags: Directed Graph, Bellman Ford The problem statement is quite clear: find a negative cycle in a directed graph. Use the Bellman-Ford algorithm. In this problem, the goal is not to find the shortest path from one node to all others, so there is no need to set the distance of the starting node to 0 (as described in the original algorithm). Instead, set the initial distances of all nodes to the same value (I have set them all to 0 for sake of simplicity). Run the Bellman-Ford algorithm for  n  rounds, and whenever a distance gets reduced, keep track of the node's predecessor. In the nth round, if a node gets reduced, then the graph contains a negative cycle. Otherwise, the graph does not contain a negative cycle. Record the last node which gets reduced. To guarantee that a node which is part of the negative cycle is found, find the predecessor of the last node visited,  n  times. This works because by backtracking n times, we will visit al...