Competitive Programming Editorials

  Problem Link Algorithm used: Knapsack DP Time Complexity: O(N²) In this problem, you start out with  an array A of size N where all elements are initially 1  an array B of size N where all elements are in the range 1 - 10³ an array C of size N where all elements are in the range 1 - 10⁶.  In one operation, you may increase the value of A[i] by  ⌊A [i] / x ⌋ , where x is a non negative integer. You may do this at most K times. For each A[i] that you modify, such A[i] = B[i], you receive C[i] coins. Find the most number of coins that you may receive while not performing more than K operations. For each A[i], find the minimum num ber of operations needed to convert 1 to B[i]. This can be done using a simple BFS, where each node is the cur rent value of A[i], and the distance to this node is the number of operations needed to reach this value. For a distance x, we can increase it by x/1, x/2, x/3 ... x/x. It doesn't make sense to divide x by any number greater tha...

  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(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 ...

  Problem Link Tags: BFS Time Complexity: O(N + M) In this problem, Bessie the cow and Elsie the cow are located in field 1 and 2 respectively and want to reach field N. To do this, they must walk along a series of roads. When Bessie walks along a road, she spends B units of energy and when Elsie walks along a road, she spends E units of energy. But, if Bessie and Elsie walk together, then they spend P units of energy collectively. Find the least amount of energy Bessie and Elsie will have to spend to get to field N. The energy spent from travelling to node a to node b is the number of roads from a to b * amount of energy spent per road. This is a graph problem, since the fields can be represented as nodes, and the roads can be represented as edges. The edges are unweighted and bidirectional. There are 2 ways the cows can reach node N: Bessie and Elsie travel alone to node N, in which case the total energy spent is distance travelled by Bessie * B + distance travelled by Elsie * E,...

  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 Tags: USACO, BFS, graph Time Complexity: O(XY) I learnt the way to solve this problem using BFS from  here. In this problem, there is M (the order quantity), two pails X and Y, and K(the number of moves available). By using at most K moves, we need to find the minimum difference in M and the achievable milk quantity using pails X and Y, in the ways described in the problem. Even though this may not seem like a graph problem, guess what? It is. When pail X has x amount of milk and pail Y has y amount of milk, we call this situation a state. A state can be written as s[x][y]. For example, if pail X has 2 units of milk and pail Y has 5 units of milk, the state is s[2][5]. The first state is s[0][0], since we start out with both pails having 0 units of milk. From here, we can reach s[X][0] or s[0][Y] by filling either pail to the top. Treat the different states as nodes in a graph. Since the two states can be obtained from s[0][0], we can draw an edge between the tw...