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