Competitive Programming Editorials

  Problem Link Problem Summary You live at the start house \(X\), and you need to reach house \(Y\) only after completing \(K\) tasks, which are located at some houses. A task is completed once you visit the house where it's located. The houses are numbered from \(1\) to \(N\), and are connected by \(N-1\) roads. Traversing a road takes \(1\) second. Find the minimum time required to complete all the tasks and end at house \(Y\). Algorithm Used Tree, DFS Editorial The layout of the houses and roads can be modelled as a tree, where the houses are the nodes, the roads are the edges. There is only one path from one node to another, which is why the graph is a tree. Let's define a few variables; \(S\) - the node that we start from \(E\) - the node that we must end at \(T\) - a node that contains a task In the picture above, we see that an edge is only traversed if it leads to a \(T\) or and \(E\) node. More specifically, if an edge is on the simple path from the \(S\) node to the...

  Problem Link Problem Summary A tree with N nodes is provided, where all the nodes are initially healthy. In the end, all nodes must be infected. There are 2 ways to infect a node: inject it with the infection, or let the infection spread. The infection can only spread from one node to another if they have the same parent node. In one second, the infection spreads to all possible nodes, and then one node is injected. Find the minimum number of seconds required for all nodes to be infected. Algorithm Used Graph Theory, Greedy, Simulation Editorial If  node is injected, then the infection can only spread to nodes within it's group. If only one node in a group is injected, then the number of seconds the infection takes to spread is the number of nodes in that group. So, to reduce the number of seconds in total, we inject the nodes that are part of the biggest groups first and try to get at least one node from every group injected as quickly as possible, so that the infection spr...

Problem Link Algorithm Used: Connected Components (DFS), binary search, two pointer Time Complexity: O(T(N + M)) In this problem, T test cases are given. In each test case, there are N fields and M roads, which connect two fields. FJ can build at most 2 roads. The cost of building a new road between field i and field j is (i - j)². There is a barn located in field 1 and another in field N. Find the minimum cost to get from the first to the second barn. This problem can be modelled as a graph problem, where the fields are the node and the roads are the edges. Roads are bidirectional and have a weight of 0. Only the new roads will be weighted, depending on the nodes they connect. There are three possible cases: FJ may build 0, 1 or 2 roads. The only case where FJ can build no roads and still reach the second barn is when the two barns are already connected by existing roads, which means that they are in the same component.  The component containing the first barn will be called the s...

  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(M log N) Algorithm Used: Disjoint Union Set There are N barns, connected by M (1 ≤ N, M ≤ 2 * 10⁵) bidirectional roads. The barns will be closed one by one. Each time a barn is closed, all roads to and from that barn cannot be used. After each barn is closed, find out whether it is possible to reach every open barn from any other open barn. This is a graph problem, since the barns can be represented as nodes and the roads as edges. The graph is unweighted.  A naive solution to this problem would be to simulate the situation by closing a barn, then picking an arbitrary open barn and running a DFS to visited all barns possible. If all the barns supposed to be open were not visited (since they are not in the same component), then it is not possible to reach every open barn from any other open barn. This is a simple and straightforward solution that will all produce the correct output, but it would exceed the time limit with a time complexity of O...

  Problem Link Algorithm Used: Range Queries, Segment Tree Treat the cow entry and exit points as the beginning and ending of ranges. /*  1. for each cow, create a range, such that cow i enters at point a and exits         at point b the range for this cow will be (a, b)     2. sort the ranges based on starting point to make it easier to count number         of overlapping ranges     3. create a segment tree     4. iterate over the ranges, and create a difference array storing the ranges         since the ranges are added one by one, use a segment tree to store the         difference array so that it can be updated quickly and sum queries can         also be done quickly     5. For each range, figure out the number of ranges that it overlaps with         To do this, find out the number of ranges that start before the ...

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