Competitive Programming Editorials

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