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 Algorithm used: BFS Time Complexity: O(NM²) In this problem, M fields are described where each field is surround by some walls. A town is situated at the junction of two or more walls. A member from certain towns need at a common field, by crossing as few walls as possible. Members are not allowed to enter towns. Find the minimum number of walls that need to be crossed by the members, followed with the field number where all the members will meet. In the example below, there are 6 towns, and members in towns 1 and 6 need to find a meeting field. The two members can meet in field 1, with the member from 6 crossing one wall They could also meet in field 2, with the member from 1 crossing one wall This problem can be represented as a graph problem where the fields and walls are the nodes, and edges are drawn between fields and walls, depending on the input. Notice that all fields will only be adjacent to walls, and all walls will only be adjacent to fields. While readin...

  Problem Link Time Complexity: O(N²log(N²)) Algorithms used: Binary Search, BFS An N * N grid is given in which Mecho (a bear) needs to reach his cave before the bees get him. He wants to leave his position at the last possible moment. Mecho can move to the squares above, below, left and right of him, if it is a grassy patch. The bees follow the same rules. The bees spread from square to square, whereas Mecho moves from square to square. Mecho can enter his cave, but the bees cannot. This problem can be represented as a graph problem, where the squares are nodes in a graph, and edges are drawn between grassy patches.  Assuming that Mecho can reach his cave before the bees, it is guaranteed that Mecho can do this if he waits for any time between 0 and x. Here, the optimal answer would be x, since he wants to wait at the last possible moment. Any waiting time greater than x would allow the bees to catch Mecho. From this observation, we find out that we can binary search on the ...

  Problem Link Time Complexity: O(Nlog(KlogK)) Algorithm used: Dijkstra's algorithm, Binary Search This  is where I understood how to solve this problem in time. In this problem, the breeds of N cows are given, followed by a K by K matrix, describing whether or not a cow of breed i is willing to transmit a message to cow of breed j. The cost of sending a message from cow i to cow j is |i - j|. Find the minimum possible cost of transmitting a message from cow 1 to cow N. This problem can be represented as a graph problem, where the cows are the nodes and edges are drawn between the nodes depending on the compatibility of cow breeds, described in the matrix. While reading in the matrix, also create an adjacency list for every breed. Intuitively, we could run a standard  Dijkstra's algorithm  starting from cow 1 and loop over the adjacency list for every pass of the algorithm. Although this implementation would always produce the correct answer, the program would exceed...

  Problem Link Time Complexity: O(N) Algorithm used: BFS Official Editorial In this problem, the layout of a farm is given along with Bessie's initial barn number, where the barns are numbered from 1 to N. From there, Bessie will try to leave the farm from an exitpoint, which is a barn that is connected to exactly one other barn. Barns are connected to each other by roads. There is one path from one barn to another. To stop Bessie from escaping, farmers are initially located at the exitpoints. Bessie and the farmers can move from one barn to another in one unit of time. If a farmer and Bessie are located at the same barn at the same time or are located on the same road at the same time, then Bessie has successfully been caught. The goal of this problem is to successfully catch Bessie using as few farmers as possible. This problem can be represented as a graph problem, where the barns are nodes in a graph and the roads are the edges. In particular, this graph is a tree  because...

Problem Link Time complexity: O(N)  Algorithm used: BFS The x and y coordinates of the laser, barn and N mirrors are given. The mirrors can be tilted horizontally or vertically, depending on the direction of the incoming beam. The mirrors reflect the beam in the opposite direction of the incoming beam. The beam can be reflected over mirrors. The goal of the problem is to direct the beam from the laser to the barn, using as few mirrors as possible. This problem can be mirrored(get it?) as a graph problem, where the mirrors, barn and laser are the nodes in a graph. The distance between the nodes does not matter, so the edge weights are all 1. Edges are drawn between perpendicular nodes.  Since the number of nodes the beam traverses must be as small as possible, a shortest path algorithm can be applied. In particular, BFS can be applied because the graph is unweighted. Run BFS twice: once when the laser sends a beam horizontally and once when the beam sends a beam vertically. If ...