arc089_b: Checker

  1. Note that if (x, y) is B, then it is equivalent of asking if (x + K, y), or (x, y + K) is W!!!

  2. So for each cell we call categories it into one of the 2k * 2k cells, i.e., the 4 - grids form a cyclic pattern.

  3. Then we try all (k^2) possibilies of lower left corner, with the help of 2-D ps to calculate v’s inside the rectangles in O(1) in each try

arc090_b: People on a Line

  1. form two direct graph, one forward, and reverse

  2. while not all are visited, forward visit form each vs, and then for each node in the graph, reverse visit

  3. the moment we have current + edge != next, we know we have an inconsistency

Official solution

But directed graph with pos and neg weights, resepctively. Run DFS for each connected components, update dist (+ or -) as we go

arc090_c: Avoiding Collision

Consider the complement of the problem. Calculate how many ways A and B can collide?

Calculate wayS(v) = # of shortest paths from S to v, waysT(v) = # of shortest paths from T to v

So total possible choices to waysS(T) * waysS(T)

number of ways to meet in a node = for each node, if distS(v) = distT(v), then decrease by waysS(v) * waysT(v)

number of ways to meet in an edge = for each edge (u, v), if distS(u) + distT(v) + len(u, v) = distS(T), and distS(U) < D/2 and distT(v) < D/2 then decrease by waysS(v) * waysT(v)