675: ShortestPathWithMagic(!!!)

Hint

Naive way would be to use the city graph as is. However, the potion makes the graph variable, but most graph algo we know requires constant graph. This suggests we should transform the problem so that the existing graph algorithm can handle it. Note that all common graph algorithm we know does not handle varaible length of edge

Algorithm

Instead of using city as node, we use (city, number of potions left), and construct graph. (c, n) to (c, n) keeps the same length, and (c, n) to (c, n-1) uses the half size.

Finally we run dijkstra from (0, k), and find the best by scanning all (1, i)

675: TreeAndPathLength3

Note that s can be 10000, but node can be no more than 500. So what is the construction that gives most 3-simple path?

So x * y + y + z - 1 is the max construct, so we set x, y both to floor(sqrt(s)) - 1, and append the remaining nodes as a single line to node 1

676: BoardEscapeDiv2

good(r, c, s) = false if any of the following is true

	1. s = 0
	
	2. grid(r, c) is an exit

	3. all of good(r+ i, c + j, s -1) is true, |i| + |j| = 1

Otherwise, good(r, c, s) = true

676: WaterTank

Just bsearch R, and make sure with R set, the residual never exceeds C