agc076b: Built?

A naive MST approach is too slow, namely, there are too many potential edges. Now that we are interested in an optimal solution, can we use some greedy insight to eliminate edges that are not actually required? This is where I got stuck!!!

What I should have done is to experiment simpler cases, and see if there is any edge that I know will never appear in the final solution.

Consider 3 points, a, b, c, with xa < xb < xc, we know the edge from xa to xc will never appear in the final solution, because we can just keep xa-xb, and xb-xc in the final MST anyway. Therefore, we just need to the add the edge between its immediate neighbors, and reduce number of edges to O(n)

821D: Okabe and City

Easy to see that we can model it as a shortest path problem. But the problem is how to reduce the number of edges in the naive approach. Similar to the atCoder problem, I am stuck proving/reducing number of edges!!!

Insights

  1. In the final solution, we know we will light each row and column at most once. Otherwise, there is cycle in our path

  2. This means we will visit each node in 3 ways ``` a. by adjacent cells

b. by lighting the row above or below or same

c. by lighting the col above or below or same

```

  1. Therefore, during BFS traversal, we need to update all 3 cases, because of insight 1), in case b and c , each cell gets updates once max each (If we use a pq to dequeue next to visit, we know the first time we light the row/column we absolutely need it, and this by 1, is the first and only time we light it in the solution) . Overall cost linear to k

  2. To detect if we can reach the destination, we need to check if the node itself is reachable, or anything from the last and second last row/col is reachable!!!